这一节继续自然数的讨论.从上一节关于自然数的定义,可以得到如下结论:
(I)$0 \in \omega$;
(II)如果$n \in \omega$,则$n^+ \in \omega$;这里$n^+= n \cup \{n\}$.
(III)(数学归纳原理)设$S \subset \omega$,若$0 \in \S$,并且当$n \in S$时必有$n^+ \in S$,则$S=\omega$;
(IV)$n^+ \neq 0$,对所有$n \in \omega$成立;因为$n^+$包含$n$,非空,自然有$n^+ \neq 0$.
(V)若$n,m \in \omega$,且$n^+=m^+$,则$n=m$.
这一个结论的证明比较费劲,书中给出了详细的过程,由于这个过程是归纳法,反证法相关方法的典型应用,这里给出详细过程.它的证明需要两个辅助命题:(i)不存在自然数,它是其元素的子集,由此可以得到$n \notin n$.(ii)一个自然数的每一个元素都是它的子集.对于(ii),引入一个概念:transitive set.集合$E$称为transitive set,如果集合$E$包含所有它的元素,或者说:$x \in y$,$y \in E$,必有$x \in E$,也就是$y \subset E$.于是(ii)实际上是说每一个自然数都是transitive set.
(i)我们实际上需要证明:对于每一个自然数$n$,$x \in n$,那么$n$不可能是$x$的子集.如果令$S=\{n \in \omega| \forall x\in n, n \subset x \text{不成立}\}$,我们需要证明$S = \omega$.使用归纳法:
(a)$0 \in S$成立,因为不存在$x \in 0$,也就无所谓$0 \subset x$问题了.
(b)若$n \in S$,要证明$n^+ \in S$.
首先$n$本身是$n$的子集,这也就意味着不可能有$n \in n$,即$n \notin n$,于是$n^+$不是$n$的子集,因为$n \in n^+=n \cup \{n\}$.若$n^+ \subset x$,则$n \subset x$,而$n \in S$,故$x \notin n$,也就是说$n^+$也不可能是$n$的任一元素的子集,有了这两点,说明$n^+$不是$n^+$的元素的子集,$n^+ \in S$.获证.
(ii)令$S = \{n \in \omega| n\text{为transitive set}\}$.需要证明$S = \omega$,同样使用归纳法.
(a)首先$0 \in S$成立,否则意味着存在$y \in 0$,使得$y$不是$0$的子集,这是不可能的.
(b)若$n \in S$,要证明$n^+ \in S$;要时刻注意$n^+ = n \cup \{n\}$,若$x \in n^+$,则或者$x \in n$,或者$x = n$,若$x \in n$,而$n \in S$,于是$x \subset n \subset n^+$,若$x=n$,则$x \subset n^+$也成立,这意味着$x$是$n^+$的子集.$n^+ \in S$.获证.
有了这两个辅助命题的帮助,可以来证明(V)了.$n^+=m^+$,而$n \in n^+$,于是$n \in m^+$,于是$n \in m$或者$n=m$,由对称性,从另一方面推导将有$m \in n$或$m=n$,若$m \neq n$,则有$n \in m$和$m \in n$同时成立,根据(ii)每一个自然数满足transitive,有$n \in n$,注意到$n \subset n$总是成立,又和(i)发生矛盾.
上述五条也常被称为Peano公理,这可能是用的最多的自然数的公理体系.德国数学家E.Landau写了一本《分析基础》(Foundations of Analysis),其中从Peano公理出发,完整推导了自然数到整数,到有理数,实数,复数的整个过程.
数学归纳法不仅仅可以用于证明,还可以用作定义.
设$f$是$X$到$X$的映射,$a \in X$,一个比较自然的想法是按如下方式定义一个序列$\{u(n)\}$(从$\omega$到$X$的映射):$u(0)=a$,$u(1)=f(u(0))$,$u(2)=f(u(1))$,…使用数学归纳法可以证明只要存在这样的$u(n)$,它就是唯一的,接下来还需要证明存在性,这就是下面的定理:
定理[归纳定理(Recursion Theorem)] 若$a$是$X$中的元素,$f$是$X$到$X$的映射,那么存在一个$\omega$到$X$的映射$u$,使得$u(0)=a$,且对所有$n \in \omega$,有$u(n^+)=f(n(n))$.
这个定理的应用就是所谓的递归定义,书中给出了详细的证明.这里复述如下:证明的总的思路是构造一个$u$,然后证明$u$是一个映射,并且满足条件.
首先注意到$\omega$到$X$的映射是$\omega \times X$的一个特殊子集,令$\mathscr{C}$为所有满足如下条件的$A$的集合:$A$是有序对的集合,也就是$A \subset \omega \times X$,且$(0,a) \in A$,对于任意的$(n,x) \in A$,必有$(n^+,f(x)) \in A$.
这个$\mathscr{C}$是非空的,因为$\omega \times X$本身满足条件,令$u$为所有$\mathscr{C}$中元素的交集,
\[u = \bigcap_{A \in \mathscr{C}}{A}.\]
下面证明$u \in \mathscr{C}$,首先$(0,a) \in A$,$\forall A \in \mathscr{C}$,故$(0,a) \in u$,其次,若$(n,x) \in u$,则$(n,x) \in A$,$\forall A \in \mathscr{C}$,故$(n^+,f(x)) \in A$,$\forall A \in \mathscr{C}$,于是$(n^+,f(x)) \in u$.
接下来若能证明$u$是一个映射,那么$u$就是满足条件的,也就是说对于每一个自然数$n \in \omega$,都有一个唯一的$x \in X$,使得$(n,x) \in u$.从$u$的构造可以知道,$x$的存在是成立的,接下来只要证明唯一性,也就是如果$(n,x) \in u$,$(n,y) \in u$,那么必有$x=y$.同样使用归纳法来证明,先构造集合$S = \{n \in \omega : (n,x) \in u, (n,y) \in u \Rightarrow x=y\}$.证明中要使用$u$的一个在包含关系下的极小性质,需要一些反证技巧.
(a)$0 \in S$,如果不成立,在存在$b$使得$(0,b) \in u$,于是考虑$u – \{(0,b)\}$,它同样是$\mathscr{C}$中的元素,这与$u$的定义矛盾.
(b)设$n \in S$,欲证$n^+ \in S$.$n \in S$$\Rightarrow$$(n,x) \in u$,$x$是唯一的,于是$(n^+,f(x)) \in u$,(这是$u$的定义),若$n^+ \notin S$,$\exists y \neq f(x)$,$(n^+,y) \in u$,考虑$u-\{(n^+,y)\}$,此时再次得到一个$u$的真子集同样属于$\mathscr{C}$,从而引发矛盾.
习题:(1)若$n$为自然数,则$n \neq n^+$;(2)若$n \neq 0$,则存在$m$使得$n=m^+$;(3)证明$\omega$是reansitive set.(4)若$E$是某个自然数的非空子集,则存在$k \in E$,使得对于任意的异于$k$的$m \in E$,有$k \in m$.
(1)令$S = \{n \in \omega:n \neq n^+\}$,证明$S=\omega$.
首先$0 \in S$,因为$0 \neq o^+$.
其次,若$n \in S$,要证明$n^+ \in S$,否则,意味着$n^+=(n^+)^+$,于是$n=n^+$,与假设矛盾.
(2)结论很明显,问题在于我们如何表示出这个$m$,$n \neq 0$,说明存在$x \in n$.我们令
\[m = \bigcup_{A \in n}{A}.\]
下面证明$n=m^+$.
$\forall x \in n$$\Rightarrow$$x \subset m$$\Rightarrow$$x \in m^+$.
$\forall x \in m^+$,意味着$x=m$或$x \in m$,若$x \in m$,$\exists A_0, x \in A_0$,$A_0 \in n$,$A_0 \subset n$(前面的辅助命题(ii)),于是$x \in n$.获证.
这里似乎有问题:第一部分$x \subset m$$\Rightarrow$$x \in m^+$恐怕不严密,因为对于一般集合不成立,只是自然数满足,第二部分缺少$x=m$的情形.$m \in n$的证明并不轻松.
(3)它实际上是要证明每一个自然数是$\omega$的子集.使用归纳法.$0$显然是$\omega$的子集;假设$n$是$\omega$的子集,欲证$n^+$是$\omega$的子集,$\forall \in n^+$,应该证明$x \in \omega$,此时$x=n$或者$x \in n$,$x=n \in \omega$;$x \in n \subset \omega$,同样有$x \in \omega$.获证.
(4)实际上是寻找集合$E$中的最小自然数.令$k=\bigcap_{A \in E}{A}$即可.因为$E$非空,$k$的存在性不是问题.但是需要证明$k \in E$,以及$k \in m$,$m \in E$,且$m \neq k$.
(2)和(4)的构造我觉得是没有问题的,可是严密的证明总是没有得到,想了几天没有太好的思路.