最后更新: 2025-01-22 08:41 查看: 215 次纠错评论(0) 课件开VIP

集合的递归定义

数学归纳法
首先通过讨论自然数的有序性和最小性，来说明数学归纳法的合理性。
在讲到关系时，我们知道＂小于等于关系＂是自然数集 $N$ 上的全序关系，即对任意两个自然数 $n_1, ~ n_2$ ，或者 $n_1 \leqslant n_2$ ，或者 $n_2 \leqslant n_1$ 。依据该全序关系，自然数集 $N$ 可排成这样一个序列： $0,1,2,3,4, \cdots$ ，这一特性称为自然数的有序性。

自然数的另一基本性质是自然数的最小性。
定理 4.1 在自然数集 $N$ 的任一非空子集 $S$ 中，必存在一个最小数（即在 $S$ 中有不大于其他任意数的数）。

定理 4.2 设 $S$ 是自然数集 $N$ 的非空子集，如果 $0 \in S$ ，并且当 $n \in S$ 时，必有 $n+1 \in S$ ，则 $S=N$ 。

定理 4.3 设 $S$ 是自然数集 $N$ 的非空子集，如果 $0 \in S$ ，并且当 $1,2, \cdots, n \in S$ 时，必有 $n+1 \in S$ ，则 $S=N$ 。

上述 3 个定理是数学归纳法的基础。证明留作作业。
对于数学归纳法，有第一数学归纳法和第二数学归纳法两种形式。
采用第一数学归纳法证明一个结论对所有自然数都为真，要做如下两件事。
（1）当 $n=0$ 时，证明结论成立。
（2）若当 $n=k$ 时结论成立，证明当 $n=k+1$ 时结论也成立。
采用第二数学归纳法证明一个结论对所有自然数都真，则要做如下两件事。
（1）当 $n=0$ 时，证明结论成立。
（2）若当 $n \leqslant k$ 时结论成立，证明当 $n=k+1$ 时结论也成立。
例4．1 用第一归纳法来证明：当 $n \in N$ ，则 $4^{n+1}-3 n-4$ 是 9 的倍数。
证明：当 $n=0$ 时，因为 $4^{0+1}-3 \times 0-4=0$ 是 9 的倍数，所以命题为真。对于任意的 $k \in N$ ，假定当 $n=k$ 时命题为真，即 $4^{n+1}-3 k-4$ 是 9 的倍数。因为 $4^{k+1+1}-3(k+1)-4=4 \times 4^{k+1}-3 k-3$ $-4=4\left(4^{k+1}-3 k-4\right)+9(k+1)$ ，由归纳假设， $4^{k+1}-3 k-4$ 是 9 的倍数，所以， $4^{(k+1)+1}-3(k+1)-4$ 也是 9 的倍数，即当 $n=k+1$ 时命题也真。

例 4.2 设有两个口袋，一个口袋装有 $m$ 个球，另一个口袋装有 $n$ 个球，并且 $m>n$ 。今有两人进行取球比赛，其比赛规则如下。
（1）二人轮流从口袋里取球，每次只准一人取球。
（2）每人每次只能从一个口袋里取，每次至少得取出一个，多取不限。
（3）最后取完口袋里的球者为胜利者。
用第二归纳法证明先取者总能取胜。
证明：当 $n=0$ 时，仅一个口袋里有球，先取者全部取出即胜。设对任意自然数 $k>0$ ，假定对任意自然数 $n \leqslant k$ 时命题为真。设 $n=k+1$ ，因为 $m>n$ ，所以先取者可以从有 $m$ 个球的口袋里取出 $(m-k-1)$ 个球。因为两个口袋都剩下有 $k+1$ 个球，且后取者还必须从一个口袋里取出至少一个球。所以先取者再取时，一个口袋里有 $k+1$ 个球，而另一个口袋里有小于等于 $k$ 个球，根据归纳假定，先取者必能取胜。这表明当 $n=k+1$ 时命题为真。

下面说明这两种形式的数学归纳法的合理性。
定理4．4 设 $P(n)$ 是一个与自然数 $n$ 有关的结论。若对于自然数 0 ，结论成立；并且当对自然数 $k$ 结论成立时，对于自然数 $k+1$ 结论也成立，则该结论对所有自然数都成立。

定理4．5 设 $P(n)$ 是一个与自然数 $n$ 有关的结论。若对于自然数 0 ，结论成立；并且当对自然数 $1,2, \cdots, k$ 结论成立时，对于自然数 $k+1$ 结论也成立，则该结论对所有自然数都成立。

证明留作作业。
下面讨论集合的另一种表示方法——集合的递归（归纳）定义。

例 4.3 下面的定义给出的是怎样的集合？
（1） $3 \in S$ 。
（2）如果 $x, y \in S$ ，则 $x+y \in S$ 。
（3）除有限次应用（1）和（2）产生的整数外，再没有其他的整数在 $S$ 中。
解：显然，集合 $S$ 给出 3 的正整数倍的全体。
例 4.3 给出的是集合的又一种表示方法，这种方法称为集合的递归（归纳）定义。
定义4．1 集合 $A$ 的递归（归纳）定义由 3 部分组成。
（1）基础：某些元素属于我们正在定义的集合 $A$ 中，说明集合 $A$ 是非空的。
（2）归纳（递归）：使用当前在集合 $A$ 中的现有元素来产生包含在此集合中的更多元素，即建立产生 $A$ 中新元素的一种方法。
（3）闭合：除了有限次应用（1）和（2）产生集合 $A$ 的元素外，$A$ 中再没有其他元素。关于闭合还有其他的叙述方式。
（1）只有在集合 $A$ 中的元素是通过有限次应用（1）和（2）得到的。
（2）集合 $A$ 是满足（1）和（2）的最小集合。
（3）集合 $A$ 是满足（1）和（2），但不存在 $A$ 的真子集满足（1）和（2），即若存在 $S \subseteq A$ ，且 $S$ 满足（1）和（2），则 $S=A$ 。
（4）集合 $A$ 是满足（1）和（2）给定性质的所有集合之交。
以上 4 种闭合的叙述方式虽然形式上不同，但它们是等价的。证明从略。
下面我们再给出几个集合递归定义的例子。

例4．4 设整数集 $Z$ 是全集，非负偶整数集 $E^{+}=\{x \mid x \geqslant 0$ ，且 $x=2 y, y \in Z\}$ ，它可以递归定义如下。
（1）（基础） $0 \in E^{+}$。
（2）（归纳）如果 $n \in E^{+}$，则 $n+2 \in E^{+}$。
（3）（闭合）除有限次应用（1）和（2）产生的整数外，再没有其他的整数在 $E^{+}$中。
下面引进字符串及字符串集合的定义，它们在计算机科学中是常用的。
设 $\Sigma$ 是一个有限非空字符集，称为字母表。从 $\Sigma$ 中选取有限个字符组成的串称为 $\Sigma$ 上的字符串或字。设 $x$ 是 $\Sigma$ 上的一个字，$x=a_1 a_2 \cdots a_n$ ，其中 $a_i \in \Sigma, 1 \leqslant i \leqslant n, n$ 是正整数，表示字的长度。长度为 0 的字称为空串，记为 $\wedge$ 。若 $x, y$ 是 $\Sigma$ 上的两个字，$x=a_1 a_2 \cdots a_n, y=b_1 b_2 \cdots b_m$ ，其中 $a_i, b_j \in \Sigma(1 \leqslant i \leqslant n, 1 \leqslant j \leqslant m)$ ，则由 $x$ 和 $y$ 毗连得到新的字记为 $x y$ 。即 $x y=a_1 a_2 \cdots a_n b_1 b_2 \cdots b_m$ 。

现在来定义字符串集合 $\Sigma^{+}$和 $\Sigma^*$ 。
例4．5 设 $\Sigma$ 是一个字母表，$\Sigma$ 上所有的有限非空字符串集合记为 $\Sigma^{+}$，递归定义如下。
（1）（基础）如果 $a \in \Sigma$ ，则 $a \in \Sigma^{+}$。
（2）（归纳）如果 $x \in \Sigma^{+}$，且 $a \in \Sigma$ ，则 $a x \in \Sigma^{+}$（ $a x$ 表示字符 $a$ 与字 $x$ 毗连得到的新的字）。
（3）（闭合）除有限次应用（1）和（2）产生 $\Sigma^{+}$中的字外，$\Sigma^{+}$中再没有其他字。
集合 $\Sigma^{+}$包含长度为 $1, ~ 2, ~ 3, ~ \cdots$ 的字，即 $\Sigma^{+}$包含无限个字，但每个字的字符个数是有限的。例如，若 $\Sigma=\{0,1\}$ ，则 $\Sigma^{+}=\{0,1,00,01,10,11,000,001, \cdots\}$ 。

例4．6 设 $\Sigma$ 是一个字母表，$\Sigma$ 上所有的有限字符串集合记为 $\Sigma^*, \Sigma^*$ 包含空串，即 $\Sigma^*=$ $\Sigma^{+} \cup\{\wedge\}$ ，可递归定义如下。
（1）（基础）$\wedge \in \Sigma^*$ 。
（2）（归纳）如果 $x \in \Sigma^*$ ，且 $a \in \Sigma$ ，则 $a x \in \Sigma^*$ 。
（3）（闭合）除有限次应用（1）和（2）产生 $\Sigma^*$ 中的字外，$\Sigma^*$ 中再没有其他字。
例如，若 $\Sigma=\{0,1\}$ ，则 $\Sigma^*=\{\wedge, 0,1,00,01,10,11,000,001 \cdots\}$ ，是有限二进制序列的集合，其中包含空序列。

在一些数学论述中，常用递归定义来刻划表达式或公式的集合。在程序设计语言中有许多使用递归定义的例子。例如，用递归定义能描述赋值语句中出现的代数表达式类或条件语句中出现的逻辑表达式类。

算术表达式集合是包含整数，一元运算符,+- ，以及二元运算符,,$+- *$ ，／的符号序列所组成的集合，其中包含如＂$((3+5) / 4) ", ~ "(((-5)+6) * 3) "$ 等算术表达式。下面用递归定义的方法来描述算术表达式集合。

例4．7 算术表达式集合的递归定义如下。
（1）（基础）如果 $D=\{0,1,2,3,4,5,6,7,8,9\}$ 和 $x \in D^{+}$，则 $x$ 是算术表达式。其中 $D^{+}$是 $D$ 上所有非空数字串的集合。
（2）（归纳）如果 $x$ 和 $y$ 都是算术表达式，则
$(+x)$ 是算术表达式；
（ $-x$ ）是算术表达式；
$(x+y)$ 是算术表达式；
$(x-y)$ 是算术表达式；
$\left(x^* y\right)$ 是算术表达式；

（ $x / y$ ）是算术表达式。
（3）（闭合）一个符号序列是一个算术表达式当且仅当它能通过有限次应用（1）和（2）而得到。

用这一定义给出的算术表达式，如 $4589, ~(-368), ~((-93) *(172 / 5))$ 以及 $(+(-305))$ 等。自然数集合
前面用到过自然数，但究竟什么是自然数和自然数集呢？由于自然数的加法定义必须建立在自然数集 $N$ 上，所以不能用加法运算来形式地定义自然数集 $N$ ，否则将会产生循环。为了避免这种定义上的循环，我们引进后继集合的概念：设 $A$ 是任一给定集合，$A \cup\{A\}$ 称为 $A$ 的后继集合，简称后继，记为 $A^{+}$。于是自然数集 $N$ 定义如下。

定义4．2 设 $N$ 为自然数集，它的递归定义如下。
（1）（基础）$\varnothing \in N$ 。
（2）（归纳）如果 $n \in N$ ，则 $n^{+} \in N$（这里 $\left.n^{+}=n \cup\{n\}\right)$ 。
（3）（闭合）如果 $S \subseteq N$ ，且 $S$ 满足（1），（2），则 $S=N$ 。
按照这个定义，自然数集的元素为：$\varnothing, \varnothing^{+},\left(\varnothing^{+}\right)^{+},\left(\left(\varnothing^{+}\right)^{+}\right)^{+}, \cdots$ ，即为 $\varnothing, ~ \varnothing \cup\{\varnothing\}$ ， $\varnothing \cup\{\varnothing\} \cup\{\varnothing \cup\{\varnothing\}\} \cdots$ 可以简化为 $\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\}, \cdots$

这里用记号：＝给这些集合命名，例如 $\varnothing$ 命名为数 0 ，记为 $0:=\varnothing$ 。于是，

$$
\begin{aligned}
& 0:=\varnothing ; \\
& 1:=0^{+}=\{\varnothing\}=\{0\} ; \\
& 2:=1^{+}=\{\varnothing, \quad\{\varnothing\}\}=\{0,1\} ; \\
& 3:=2^{+}=\{\varnothing, \quad\{\varnothing\}, \quad\{\varnothing,\{\varnothing\}\}\}=\{0,1,2\} ;
\end{aligned}
$$

一般地，若已给出 $n$ ，则 $n+1:=n^{+}=\{0,1,2, \cdots, n\}$ 。于是得到自然数集 $N=\{0,1,2$ ，
$3, \cdots\}$ ，其中除 0 外每一个自然数是它前一个自然数的后继。
这样，可以得到自然数 $n$ 的许多性质，包括下面的定理。
定理4．6（1） 0 不是任何自然数的后继。
（2）任何自然数的后继是唯一的。
（3）如果 $n^{+}=m^{+}$，则 $n=m$ 。
证明从略。
从以上叙述可以得到著名的关于自然数的贝安诺（Peano）公理。
贝安诺（Peano）公理
（1） $0 \in N_{\text {。 }}$
（2）对每一个 $n \in N$ ，恰存在一个 $n^{+} \in N$（称 $n^{+}$为 $n$ 的后继）。
（3）不存在一个 $n \in N$ ，使 $n^{+}=0$ 。
（4）如果 $n^{+}=m^{+}$，则 $n=m$ 。
（5）如果 $S \subseteq N$ ，且（1） $0 \in S$ ，（2）如果 $n \in S$ ，那么 $n^{+} \in S$ ，则 $S=N$ 。
贝安诺公理可以不用集合来刻划自然数，而给出自然数集的定义。
贝安诺公理（5）称为极小性，表示：如果自然数集 $N$ 的子集 $S$ 包含数 0 ，并且 $S$ 中每一个数 $n$ 都有它的后继 $n^{+}$，则 $S$ 就是自然数全体。公理中 $n^{+}$可理解为 $n+1$ ，但是我们不一定要把＂+ ＂作为 $N$ 上的一个运算。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：集合的特征函数

下一篇：贝安诺公理

本文对您是否有用？有用 (0) 无用 (0)