自然数

前置

• naive-set-theory-1

自然数

皮亚诺公理

• $0$ is a natural number.
• If $n$ is a natural number, then $n++$ is also a natural number.
• $0$ is not the successor of any natural number; i.e., we have $n++\ne 0$ for every natural number $n$.
• Different natural numbers must have different successors; i.e., if $n,m$ are natural numbers and $n\ne m$, then $n++\ne m++$. Equivalently, if $n++=m++$ then we must have $n=m$.
• Principle of mathematical induction. Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n++)$ is also true. Then $P(n)$ is true for every natural number $n$.

自然数集$\mathbb{N}=\{n\mid n\text{ is a natural number}\}$

$\text{Recursive definitions}$. Suppose for each natural number $n$, we have some function $f_n:\mathbb{N}\to \mathbb{N}$ from the natural numbers to the natural numbers. Let $c$ be a natural number. Then we can assign a unique natural number $a_n$ to each natural number $n$, such that $a_0=c$ and $a_{n++}=f_n(a_n)$ for each natural number $n$.

证明：

首先，对于$n\ne 0$,根据 Peano 公理有$n++\ne 0$,所以$a_0$没有被重新定义，即$a_0$唯一

其次，设$a_n$唯一，若$a_{n++}$不唯一，即$m++=n++$,根据 Peano 公理有$m=n$，所以$a_{n++}$唯一

最后，根据数学归纳法，对所有的自然数$n$，$a_n$唯一

自然数加法

自然数加法$f(n,m):\mathbb{N}\times \mathbb{N}\to \mathbb{N}$,将$f(n,m)$记作$n+m$

• $\text{Addition of natural numbers}$. Let $m$ be a natural number. To add
  zero to $m$, we define $0+m:=m$. Now suppose inductively that we have defined how
  to add $n$ to $m$. Then we can add $n++$ to $m$ by defining $(n++)+m:=(n+m)++$.

说明:

对与任意一个自然数 $m$

首先，我们定义了 $f(0,m)=m$,根据 Peano 公理有$n++\ne 0$，所以$f(0,m)$唯一

其次假设我们已经唯一定义了$f(n,m)$,那么我们定义$f(n++,m)=(f(n,m))++$，假设定义不唯一，根据 Peano 公理有$n++=m++$，所以$n=m$，所以$f(n++,m)$被唯一定义

最后，根据数学归纳法，对所有的自然数 $n$，$f(n,m)$被唯一定义。

$\text{Lemma}$. For any natural number $n$, $n+0=n$. 可对$n$使用数学归纳法证明。

$\text{Lemma}$. For any natural numbers $n$ and $m$, $n+(m++)=(n+m)++$.
证明：

对$n$使用数学归纳法

$n=0$,$f(0,m++)=m++=f(0,m)++$

假设$f(n,m++)=f(n,m)++$成立

那么$f(n++,m++)=f(n,m++)++=(f(n,m)++)++=f(n++,m)++$

根据数学归纳法，对所有的自然数都有$f(n,m++)=f(n,m)++$成立

$\text{Lemma}$. For any natural numbers $n$ and $m$, $n+m=m+n$. 可固定其中一个数，对另一个数使用数学归纳法。

$\text{Lemma}$. For any natural numbers $a$, $b$, $c$, we have $(a+b)+c=a+(b+c)$. 可对$c$使用数学归纳法证明。

$\text{Lemma}$. Let $a$, $b$, $c$ be natural numbers such that $a+b=a+c$. Then we have $b=c$. 可对$a$使用数学归纳法证明。

$\text{Definition}$. A natural number $n$ is said to be positive iff it is not equal to 0.

$\text{Proposition}$. If $a$ is a positive natural number, and $b$ is a natural number, then $a+b$ is positive. 对$b$使用数学归纳法证明。

$\text{Corollary}$. If $a$ and $b$ are natural numbers such that $a+b=0$, then $a=0$ and $b=0$.

$\text{Lemma}$. Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b++=a$.

令$P(n):(n\ne 0)\to (\text{存在唯一的自然数}b\text{使得}b++=a)$

$n=0$ 时， $P(0)$空真

假设 $P(n)$成立，即存在唯一的自然数$b$使得$b++=a$

那么$n++$时，假设$c++=a++$（$c$的存在性显然，因为$a++=a++$）,则有$a++=c++=(b++)++$,根据 Peano 公理有$c=b++$，所以存在唯一的自然数$b++$使得$b++=a++$

根据数学归纳法，P(n)对所有自然数 n 成立

自然数的上的偏序关系

$\text{Ordering of the natural numbers}$. Let $n$ and $m$ be natural numbers. We say that $n$ is greater than or equal to $m$, and write $n\ge m$ or $m\le n$, iff we have $n=m+a$ for some natural number $a$. We say that $n$ is strictly greater than $m$, and write $n>m$ or $m<n$, iff $n\ge m$ and $n\ne m$.

$\text{Proposition}$. Let $a,b,c$ be natural numbers. Then

• (Order is reflexive) $a\ge a$.
• (Order is transitive) If $a\ge b$ and $b\ge c$, then $a\ge c$.
• (Order is antisymmetric) If $a\ge b$ and $b\ge a$, then $a=b$.
• (Addition preserves order) $a\ge b$ if and only if $a+c\ge b+c$.
• $a<b$ if and only if $a++\le b$.
• $a<b$ if and only if $b=a+d$ for some positive number $d$.
• $a<=b$ and $c<d$ $\Rightarrow$ $a+c<b+d$

可以根据定义和上面已有的性质证明。

$\text{Proposition}$. Let $a$ and $b$ be natural numbers. Then exactly one of the following statements is true: $a<b$, $a=b$, or $a>b$.

证明：对$b$使用数学归纳法 $P(b):$假设$a<b$和$a=b$都不成立，我们证明一定有$a>b$

$b=0$时，$a=a+0$，所以$a\ge 0$,根据假设$a\ne 0$，所以$a>0$

假设$b=n$时,$P(b)$成立

$b=n++$时，因为$a>b$,所以$a\ge n++$,根据假设有$a\ne n$，所以$a>n$

根据数学归纳法，对所有的自然数$b$，$P(b)$成立

强归纳法

$\text{Lemma}$.$n++>n$. 因为 $n++=n+++0=(n+0)++=n+(0++)$

$\text{Lemma}$ 不存在自然数 m 和 n，使得$n<m<n++$

反证，若$n<m$,则$m=n+d=(n++)+e$,其中 $d>0$,$e\le 0$,所以$m>n++$

与自然数上的偏序关系的三分性矛盾

$\text{Strong principle of induction}$. Let $m_0$ be a natural number, and let $P(m)$ be a property pertaining to an arbitrary natural number $m$. Suppose that for each $m\ge m_0$, we have the following implication: if $P(m^{\prime })$ is true for all natural numbers $m_0\le m^{\prime }<m$, then $P(m)$ is also true. (In particular, this means that $P(m_0)$ is true, since in this case the hypothesis is vacuous.) Then we can conclude that $P(m)$ is true for all natural numbers $m\ge m_0$.

定义 $Q(n)$：$P(m)$ is true for all $m_0\le m<n$

当$n\le m_0$是，Q(n)空真，因此 Q(0)成立

假设$Q(n)$成立，即$P(m)$对所有$m_0\le m<n$成立

根据强归纳法的条件（if $P(m^{\prime })$ is true for all natural numbers $m_0\le m^{\prime }<m$, then $P(m)$ is also true.）有$P(n)$成立

集合$A=\{m\in \mathbb{N}\mid m_0\le m<n++\}=\{m\in \mathbb{N}\mid m_0\le m<n\}\cup \{n\}$

根据强归纳法的条件，P(m)对所有$m\in A$成立

根据数学归纳法，Q(n)对所有自然数$n$成立

自然数乘法

$g(n,m):\mathbb{N}\times \mathbb{N}\to \mathbb{N}$，将$g(n,m)$记作$n\times m$或$nm$或$n\cdot m$

$\text{Multiplication of natural numbers}$. Let $m$ be a natural number. To multiply zero to $m$, we define $0\times m:=0$. Now suppose inductively that we have defined how to multiply $n$ to $m$. Then we can multiply $n++$ to $m$ by defining $(n++)\times m:=(n\times m)+m$

$\text{Lemma}$. For any natural number $n$, $n\times 0=0$. 可对$n$使用数学归纳法证明。

$\text{Lemma}$. For any natural numbers $n$ and $m$, $n\times (m++)=(n\times m)+n$. 可对$n$使用数学归纳法证明。

$\text{Lemma}$. Let $n,m$ be natural numbers. Then $n\times m=m\times n$. 可固定$m$对$n$使用数学归纳法证明。

$\text{Lemma}$. Let $n,m$ be natural numbers. Then $n\times m=0$ if and only if at least one of $n,m$ is equal to zero. In particular, if $n$ and $m$ are both positive, then $nm$ is also positive.

$\Rightarrow$使用反证法

$\Leftarrow$使用定义

$\text{Proposition}$. For any natural numbers $a,b,c$, we have $a(b+c)=ab+ac$ and $(b+c)a=ba+ca$. 可对$a$使用数学归纳法证明。

$\text{Proposition}$. For any natural numbers $a,b,c$, we have $(a\times b)\times c=a\times (b\times c)$. 可对$c$使用数学归纳法证明。

$\text{Proposition}$. If $a,b$ are natural numbers such that $a<b$, and $c$ is positive, then $ac<bc$. 使用定义证明。

$\text{Corollary}$. Let $a,b,c$ be natural numbers such that $ac=bc$ and $c$ is non-zero. Then $a=b$. 使用上面的命题证明。

$\text{Proposition}$. Let $n$ be a natural number, and let $q$ be a positive number. Then there exist natural numbers $m,r$ such that $0\le r<q$ and $n=mq+r$. 并且$m$和$r$唯一。

存在性对$n$使用数学归纳法

唯一性的证明,设$n=m_{1}q+r_1=m_{2}q+r_2$,对$r_1$和$r_2$分类讨论

若$r_1=r_2$,则根据加法消去律，有$m_{1}q=m_{2}q$，$q\ne 0$，根据乘法消去律有$m_1=m_2$

若$r_1=r_2$,不妨设$r_1<r_2$，则$r_2=r_1+d$,其中$d\ne 0$，则有$m_{1}q+r_1=m_{2}q+r_1+d$，根据加法消去律有$m_{1}q=m_{2}q+d$，所以$m_{1}q>m_{2}q$，因为$q\ne 0$，根据乘法消去律有$m_1>m_2\Leftarrow$ $m_1\ge (m_2++)$

$n=m_{1}q+r_1>(m_2++)q+r_1=m_{2}q+r_1+q>m_{2}q+r_2=n$,矛盾

自然数整数次幂

$\text{Definition}$. Let $m$ be a natural number. To raise $m$ to the power $0$, we define $m^0:=1$; in particular, we define $0^0:=1$. Now suppose recursively that $m^n$ has been defined for some natural number $n$, then we define $m^{n++}:=m^n\times m$.

总结

由以上讨论知：

• 自然数加法有结合律,交换律
• 自然数乘法有结合律,交换律
• 自然数乘法对加法有分配律
• 自然数加法有单位元$0$，乘法有单位元$1=(0++)$

自然数是一个良序集

$\text{Lemma}$. 对于任意$n\in \mathbb{N},S=\{m\in \mathbb{N}|m\le n\}$，$S$为有限集

$n=0$时，$S=\{0\}$，是有限集

假设$n=k$时，$S$为有限集

则$n=k++$时，$S=\{m\in \mathbb{N}|m\le k\}\cup \{k++\}$，是有限集

根据数学归纳法，对于任意$n\in \mathbb{N},S=\{m\in \mathbb{N}|m\le n\}$，$S$为有限集

$\text{Lemma}$. $\mathbb{N}$中不存在无穷严格递减序列。由$S=\{m\in \mathbb{N}|m\le n\}$为有限集易得。

$\text{Lemma}$. $\mathbb{N}$为良序集。

由$<$的三分性可得$\mathbb{N}$是全序集

假设$\mathbb{N}$不是良序集，则$\mathbb{N}$中存在无穷严格递减序列，矛盾。