使用归纳定义,可以给出自然数的加法,乘法和幂的定义,减法和除法在自然数并不总是可行的,可以定义为加法和乘法的逆运算.

加法:$s_m(0)=m$,$s_m(n^+)=(s_m(n))^+$;也就是$s_M(n)=m+n$.

乘法:$p_m(0)=0$,$p_m(n^+)=p_m(n)+m$;也就是$p_M(n)=m \cdot n$.

幂次:$e_m(0)=1$,$e_m(n^+)=e_m(n) \cdot m$;也就是$e_M(n)=m^n$.

书中给出了加法结合律的证明,作为数学归纳法的典型应用,这里也记录之:

要证明

\[(k+m)+n=k+(m+n).\]

对$n$作归纳.

(i)$(k+m)+0=k+m=k+(m+0)$;

(ii)假设对于$n$成立,对于$n^+$来说,

\[(k+m)+n^+ = ((k+m)+n)^+=(k+(m+N))^+=k+(m+n)^+=k+(m+n^+).\]

对于交换律:$m+n=n+m$,在使用归纳法的时候,需要一些技巧.直接对$m$或者$n$做归纳,都不容易成功,因为$m+0=0+m$这一步本身就很麻烦,于是我们分两步走:

(1)$0+n=n+0$.

(i)$n=0$显然成立:$0+0=0$.

(ii)$0+n^+=(0+n)^+=(n+0)^+=n^+=n^++0$.最后一步自然数加法的定义.

(2)$m^++n=(m+n)^+$.

仍然是对$n$归纳:

(i)$m^++0=m^+=(m+0)^+$;

(ii)假设对$n$成立,$m^++n^+=(m^++n)^+=((m+n)^+)^+=(m+n^+)^+$.

接下来证明交换律,对$m$进行归纳.(i)$m=0$已经成立,(ii)假设交换律对于$m$成立,对于$m^+$来说,$m^++n=(m+n)^+=(n+m)^+=n+m^+$.

乘法的交换律和结合律可以用同样的方法证明.

两个自然数$m$和$n$是可比较的(comparable),若$m \in n$,或$m=n$,或$n \in m$.我们有结论:任意两个自然数是可比较的.这个结论比较重要,书中给出了详细证明.令

\[S(n)=\{m \in \omega: m \text{与} n\text{是可比较的}\},\]

以及$S = \{n \in \omega:S(n)=\omega\}$.我们需要证明$S=\omega$,这里同样应用数学归纳法.

(i)$0 \in S$,或者$S(0)=\omega$,使用归纳法:(a)$0 \in S(0)$,(b)$m \in S(0)$,则$m^+ \in S(0)$.

(ii)若$n \in S$,则$n^+ \in S$,首先$0 \in S(n^+)$,因为$n^+ \in S(0)$.接下来需要从$m \in S(n^+)$出发推导出$m^+ \in S(n^+)$.$m \in S(n^+)$,意味着$m \in n^+$,或者$m=n^+$,或者$n^+ \in m$,后两者立即可以得到$n^+ \in m$,故只要讨论$m \in n^+=n \cup \{n\}$情形.于是$m=n$或$m \in n$,从$m=n$可以得到$m^+=n^+$.于是接下来讨论$m \in n$这一情形,从$S(n)=\omega$可知$m^+ \in S(n)$,于是$m^+ \in n$,或者$m^+=n$,或者$n \in m^+$.前面两个可以得到$m^+ \in n^+$,这就讨论一个情形:$n \in m^+$,但是它不能和$m \in n$同时成立.因为$n \in m^+$会得到$n=m$,或者$n \in m$,都有$n \subset m$,这与$m \in n$不能同时成立(前一节的结论).

$m \in n$,$m=n$和$n \in m$有且仅有一个成立.

若$m \in n$和$m=n$同时成立,$m=n$$\Rightarrow$$n \subset m$,不可能;若$m \in n$和$n \in m$$\Rightarrow$$m \in m$(transitive),$m \subset m$不可能.若$m=n$,$n \in m$,$\Rightarrow$$m \subset n$,同样不成立.

任一自然数不可能是它的元素的子集,另一个结论是不相同的$m$,$n$满足$m \in n$的充要条件是$m \subset n$.$m \in n \Rightarrow m \subset n$可以同$n$的transitive性质得到;$m \subset n$,$n \in m$不可能,否则$m$是它的某个元素$m$的子集.

$m \in n$定义为$m \subset n$,$m \in n$或者$m=n$定义为$m \le n$.

习题:若$m<n$,则$m+k<n+k$,若$m<n$,$k \neq 0$,则$m \cdot k < n \cdot k$,若$E$是非空的自然数集,则存在$k \in E$,使得$k \le m$对所有的$m \in E$成立.

(i)对$k$施加归纳法,(a)$k=0$时,就是题设本身,结论成立;(b)假设结论对于$k$成立,对于$k^+$来说,$m+k^+=(m+k)^+<(n+k)^+=n+k^+$.我们需要证明若$m<n$,则$m^+<n^+$,这里一点可以这样得到:$m<n$,可以得到$m \in n$$\Rightarrow$$m \subset n$$\Rightarrow$$m \subset n^+$,$m \in n$$\Rightarrow$$m \in n^+$$m \subset n^+$,因此$m^+ \in n^+$,$m^+ < n^+$.

(ii)似乎不是很容易,我们换一个思路,我们证明,对于任意自然数$k$,有$mk^+<nk^+$.使用归纳法以及刚刚证明的关于加法的结论即可.

(a)$k=0$,$mk^+=m<n=nk^+$;(b)$m(k^+)^+=mk^++m<nk^++m<nk^++n=n(k^+)^+$.

(iii)这实际上是前一节已经出现过的题目.

我们称集合$E$和$F$是对等(equivalent)的,如果存在一个$E$和$F$之间的一一对应,这是一个等价关系.

自然数$n$的每一个真子集对等于某个比$n$小的自然数,或者说$n$的元素.证明使用归纳法.$n=0$是平凡的,如果对于$n$成立,那么对于$n^+$来说,对于$n^+$的真子集$E$,可能出现这样几个情形:$E$是$n$的真子集,此时根据归纳假设,结论成立;若$E=n$,那结论自然成立,$n$中恒等映射;最后一个情形是$n \in E$,此时,存在$k \in n$,但是$k \notin E$,定义$E$上的映射$f$如下:当$i \neq n$时,$f(i)=i$,否则$f(n)=k$,这个$f$是$E$到$n$的一一对应.再使用归纳假设,以及一一对应关系的传递性,可以知道结论成立.

一个多少令人有些意味的事实是:一个集合可以和它的真子集对等.一个最好的例子就是$f(n)=n^+$,自然数集与非零自然数集之间的一个一一对应关系.但是对于自然数$n$,它不能和$n$的任一真子集对等.同样可以使用归纳法证明.从$n$到$n^+$这一步,分$n \in E$和$n \notin E$来讨论,$n \in E$时,取$E-\{n\}$.

集合$E$称为有限(finite)的,如果它与某个自然数对等,否则就称为无限的(infinite),

习题:用这个定义证明自然数集$\omega$是无限的.

我们使用反证法,通过构造出一个自然数$n$和它的真子集之间的一一对应来得到矛盾.首先$\omega$显然不可能和$0$对等,于是假设$\omega \sim n$,那么$n \neq 0$,前面已经证明过,此时存在自然数$m$,$n=m^+$.

假设$f$是$\omega$和$n$之间一一对应,设$f(0)=k$,则$k \le n$,我们构造$\omega-\{0\}$到$m$之间的映射$g$如下:若$x<k$,令$g(x)=f(x)$,当$x \ge m$时,$g(x)=f(x^+)$,那么这个$g$是一一的,于是我们有了$n \sim \omega \sim \omega-\{0\} \sim m$,于是自然数集和它的一个真子集对等了,发生矛盾.

一个集合最多与一个自然数对等.

任何两个不同的自然数$m$,$n$,必有$m \in n$或$n \in m$,无论如何其中一个是另一个的真子集,而自然数不可能与其真子集对等.由此可知有限集不可能和它的真子集对等,即对于有限集来说,整体大于部分成立.

习题:使用有限的定义的这个推论证明$\omega$是无限的.

因为$\omega$可以与$\omega-\{0\}$对等,从而不是有限的.

一个自然数的每一个子集与某个自然数对等,自然说明有限集的每一个子集是有限的.

有限集$E$的元素个数定义为与$E$对等的那个自然数,记为$\#E$,这个自然数是唯一的,$\#E$是$P(X)$到$\omega$的一个映射.

(1)$E \subset F$,则$\#E \le \#F$,$E$,$F$都是有限集.

$E \sim \#E$,$F \sim \#F$,$\#E$对等于$F$的某个子集,$\#E \le \#F$.

(2)$E$,$F$为有限集,则$E \cup F$也是有限的,而且当$E$与$F$不相交时:$\#(E \cup F) = \#(E) + \#(F)$.

若$m$与$n$为自然数,则$m$在$m+n$中的补集与$n$对等.对$n$使用归纳法.

(3)$E$,$F$为有限集,则$E \times F$与$E^F$均为有限集,且$\#(E \times F) – \#(E) \cdot \#(F)$,$\#(E^F)=(\#(E))^{(\#(F))}$.

习题:有限个有限集的并集是有限的,若$E$是有限的,则$P(E)$是有限的,$\#(P(E))=2^{\#(E)}$,若$E$是非空的自然数的有限集,则存在$k \in E$,使得$m \le k$,$\forall m \in E$.