數學證明與數學原理/集合/自然數

無窮大

到目前為止，所陳述的策梅洛-弗蘭克爾公理中沒有一個斷言存在無窮集。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$