数学证明与数学原理/集合/自然数

无穷大

到目前为止，所陈述的策梅洛-弗兰克尔公理中没有一个断言存在无穷集。ZF 集合论的下一个公理就是为了做到这一点。

首先我们需要归纳集的概念。

定义 若$\emptyset \in S$ 且$n\cup \{n\}\in S$ 对所有$n\in S$ 成立，则称集合$S$ 为归纳集。对于给定的集合$n$，我们称$n\cup \{n\}$ 为$n$ 的后继者，并将其记为$n^{+}$。

公理（无穷大公理）

存在一个归纳集。

虽然存在许多归纳集，但我们可以证明以下结论。

定理 存在一个唯一的归纳集，它是所有归纳集的子集。

证明 设$S$ 为任何归纳集。根据无穷大公理，这样的集合是存在的。

现在让我们定义$W=\{x\in S\;|\;x\in A\;{\mbox{for all inductive sets}}\;A\}$。请注意，根据理解公理模式，$W$ 是一个集合。

如果$x\in W$，则$x$ 存在于每个归纳集中。因此，$W$ 是每个归纳集的子集。

由于 $\emptyset$ 属于每个归纳集，因此 $\emptyset \in W$。此外，如果 $x\in W$，那么 $x$ 属于每个归纳集，因此 $x\cup \{x\}$ 属于每个归纳集。因此 $x\cup \{x\}\in W$。因此，$W$ 是归纳的。

为了证明 $W$ 是唯一的，假设 $W_{1}$ 和 $W_{2}$ 都是归纳集，并且都是所有归纳集的子集。特别地，我们有 $W_{1}\subseteq W_{2}$ 和 $W_{2}\subseteq W_{1}$。然后根据外延公理， $W_{1}=W_{2}$。 $\square$

定义 我们用 $0$ 表示 $\emptyset$，用 $1$ 表示 $0^{+}$，用 $2$ 表示 $1^{+}$，等等。唯一一个作为所有归纳集子集的归纳集记作 $\omega$。

请注意，$0=\{\}$，$1=\{0\}$，$2=\{0,1\}$，$3=\{0,1,2\}$。

一般来说，$n=\{0,1,2,\ldots ,n-1\}$，所以$n^{+}=n\cup \{n\}=\{0,1,2,\ldots ,n\}$。

自然数

我们已经看到$\omega$包含$0,1,2,\ldots$。我们称之为自然数。请注意，在数学的其他领域，自然数不包括$0$，但在集合论中，将它包括进来很方便。

定义 对于自然数$n$，我们将使用$n+1$来代替$n^{+}=n\cup \{n\}$。

关于自然数最有用定理之一如下所示。

定理 (归纳法) 假设 $P(x)$ 是自然数的一个性质，对于它 $P(0)$ 成立，并且对于所有自然数 $n$ ，当 $P(n)$ 成立时，我们有 $P(n+1)$ 也成立。那么 $P(n)$ 对于所有自然数 $n$ 成立。

这是一个可以使用归纳法证明的简单结果。

定理 如果 $m,n,k\in \omega$ 并且 $m\in n$ 并且 $n\in k$ 那么 $m\in k$.

证明 我们用关于 $k$ 的归纳法来证明这一点。换句话说，我们令 $P(k)$ 为性质：如果 $m\in n$ 并且 $n\in k$ 那么 $m\in k$.

$P(0)$ 成立，因为在这种情况下 $k$ 为空，没有需要证明的。

现在假设 $P(k)$ 对某个 $k\in \omega$ 成立。换句话说，对于 $k$ 的那个值，我们有，如果 $m\in n$ 且 $n\in k$，那么 $m\in k$。

我们想证明 $P(k+1)$ 成立。因此假设 $m\in n$ 且 $n\in k^{+}$。有两种情况。

因为 $k^{+}=k\cup \{k\}$ 有两种情况。第一种情况是 $n\in k$。根据归纳假设，$m\in k\subset k^{+}=k\cup \{k\}$。因此 $m\in k$。

另一种情况是 $n\in \{k\}$。在这种情况下，$n=k$。因此，由于 $m\in n$，我们有 $m\in k$。因此我们已经证明，在这两种情况下，$P(k+1)$ 成立。

因此，根据归纳法，$P(k)$ 对所有自然数 $k$ 成立。 $\square$

下面是另一个简单的结果，它也通过归纳法得出。

定理 $\omega$ 中的每个元素要么是 $0$，要么是 $\omega$ 中某个元素的后继。

证明 我们用关于 $k$ 的归纳法证明这一点，其中 $P(k)$ 是 $k$ 要么是 $0$，要么是某个 $m\in \omega$ 的后继。

显然 $P(0)$ 成立。现在假设对于某个 $k\in \omega$， $P(k)$ 成立。因此，要么 $k=0$，要么 $k=m^{+}$ 对于某个 $m\in \omega$。在这两种情况下， $k^{+}$ 是 $k$ 的后继，因此 $P(k+1)$ 成立。因此，根据归纳法， $P(k)$ 对于所有 $k\in \omega$ 都成立。 $\square$

归纳法的一个有用变体如下所示。

定理（强归纳法） 设 $P(n)$ 是自然数的一个性质，如果 $P(m)$ 对所有 $m\in n$ 成立，则 $P(n)$ 成立。那么，这样的性质 $P(n)$ 对所有自然数 $n$ 成立。

证明 我们用普通归纳法来证明这个结果。设 $Q(n)$ 表示性质 $P(m)$ 对每个 $m\in n$ 成立。显然，$Q(0)$ 成立，因为 $0$ 没有元素需要证明。

现在假设 $Q(n)$ 对某个 $n\in \omega$ 成立。换句话说，$P(m)$ 对所有 $m\in n$ 成立。

但根据假设，这意味着 $P(n)$ 成立。因此，$P(m)$ 对所有 $m\in n\cup \{n\}$ 成立。换句话说，$Q(n+1)$ 成立。

因此，根据普通的归纳法，$Q(n)$ 对所有自然数 $n$ 成立。

但是如果 $n\in \omega$，那么 $n^{+}\in \omega$，因此对所有自然数 $n$，我们有 $Q(n^{+})$ 成立。但是 $n\in n^{+}$，因此特别地我们有 $P(n)$ 成立。换句话说，我们已经证明了 $P(n)$ 对所有自然数 $n$ 成立。 $\square$