逻辑与公理化集合论(04)：无穷公理与自然数的构造

为了在集合论中定义"函数", 上一节已经构造了序偶、直积与关系. 但到目前为止, 我们仍然没有回答一个更基础的问题: 数本身从哪里来?

在朴素数学里, 自然数似乎是不言自明的对象; 然而在公理化集合论中, 自然数也必须被构造出来. 本节的目标就是在 ZF 公理系统中引入无穷公理, 并据此构造自然数集.$\newcommand{\K}{\mathbb{K}}\newcommand{\R}{\mathbb{R}}\newcommand{\C}{\mathbb{C}}\newcommand{\N}{\mathbb{N}} \newcommand{\set}[1]{\{ #1 \}} \renewcommand{\exist}{\exists}\renewcommand{\and}{\land}\renewcommand{\or}{\lor} \renewcommand{\empty}{\varnothing}\renewcommand{\subset}{\subseteq}\renewcommand{\supset}{\supseteq}$

无穷公理与归纳集

仅靠前面介绍过的分离、并集、配对和幂集公理, 还不足以保证一个无限过程的结果能够作为集合存在. 例如, 我们当然希望存在这样一个集合 \[ \N=\set{0,1,2,3,\cdots}\ (\text{非正式记号}) \] 但在 ZF 公理系统中, 并不能仅凭直觉写下这种集合. "无限集合存在"本身必须由公理保证. 在介绍公理之前, 让我们先对集合定义一种新的运算: 后继运算.

Def 后继

若$x$是一个集合, 定义它的后继为集合$x^+$: \[ x^+:=x\cup\set{x} \]

根据配对公理, 无序偶$\set{x,x}$(i.e., $\set{x}$)存在; 根据并集公理, $x$和$\set{x}$的并集存在. 因此给定原集合, 后继运算的结果也是一个集合. 下面介绍 ZF 公理系统的第6条公理.

Axiomatic System ZF公理系统的第6条(无穷公理)

存在一个集合$X$, 满足

空集是其元素: $\empty\in X$;
对后继运算封闭: $\forall x(x\in X\Rightarrow x\cup\set{x}\in X)$.

这个公理断言: 至少存在一个集合, 它包含空集, 并且只要某个元素$x$已经在其中, 那么$x^+$也仍然在其中. 为了更好地描述这种对象, 将这两条性质总结成新的定义:

Def 归纳集

若一个集合$I$满足 \[ \varnothing\in I \] 并且 \[ \forall x(x\in I\Rightarrow x^+\in I) \] 则称$I$为一个 归纳集.

于是, 无穷公理也可以简洁地表述为: 归纳集存在. 从直观上看, 归纳集就是一种"能够不断对元素进行后继操作"的集合. 只要空集在里面, 空集的后继也在里面, 空集后继的后继也在里面, 如此无限延续.

自然数与最小归纳集

von Neumann 方案

既然空集总是最简单的集合, 最自然的做法就是把它当作“零”:

\[ 0:=\empty \] 于是可以逐步构造出 \[ \begin{aligned} 1&:=0^+=0\cup\set{0}=\set{0} \\ 2&:=1^+=1\cup\set{1}=\set{0,1} \\ 3&:=2^+=2\cup\set{2}=\set{0,1,2} \end{aligned} \] 依此类推.

这就是 von Neumann 自然数构造. 在这种构造下, 每一步出现的新自然数, 都被定义为已经定义过的自然数构成的集合.

最小归纳集的构造

无穷公理只告诉我们“至少存在一个归纳集”, 但任选的归纳集可能很大, 里面也许含有很多不是自然数构造本身所必需的元素. 我们真正想要的, 不是随便某个归纳集, 而是最小的那个归纳集.

设$A$是由无穷公理保证存在的某个归纳集. 考虑$A$的一切归纳子集的集合族: \[ \mathcal{I}:=\set{B\in\mathcal{P}(A)\mid B\text{是归纳集}} \] 由于$A$本身就是归纳集, 所以$\mathcal{I}$非空. 于是可以计算该集合族的交集:

Def 自然数集

集合 \[ \omega:=\bigcap \set{B\in\mathcal{P}(A)\mid B\text{是归纳集}} \] 称为 自然数集.

接下来将证明, $\omega$是归纳集, 并且恰好是最小归纳集, 即它是任何归纳集的归纳子集.

Lemma $\omega$本身是归纳集, 并且它包含于任意归纳集.

▶

Proof

证明$\omega$是归纳集:
1. 因为每个$A$的归纳子集$B$都包含$\varnothing$, 所以$\varnothing\in\omega$.
2. 若$x\in\omega$, 则$x$属于任意$A$的归纳子集$B$; 由于$B$是归纳集, 于是$x^+$也属于$B$, 所以$x^+\in\omega$.

可得$\omega$是归纳集.

证明$\omega$是$A$的任意归纳子集的子集:

因为$\omega$是$A$的全体归纳子集的交集, 因此对任意$A$的归纳子集$B$, 都有$\omega\subset B$
证明$\omega$是任意归纳集的子集:

任取归纳集$I$, 则$A\cap I$必然也是归纳的, 因为空集是其元素: \[ \empty\in I\and\empty\in A\Rightarrow\empty\in A\cap I \] $I$的任意元素后继仍是$I$的元素: $$
\[\begin{aligned} \forall x\in A\cap I\Rightarrow x\in A&\and x\in I \\&\Downarrow \\ x^+\in A\cap I \Leftarrow x^+\in A&\and x^+\in I \end{aligned}\]
$$ 于是可知: $A\cap I$是$A$的归纳子集. 又由于$\omega$是$A$的任意归纳子集的子集, 所以$\omega$是$A\cap I$的子集, 自然满足$\omega\subset I$.

这就证明了$\omega$是归纳集, 并且它包含于任意归纳集, 与最初定义时对$A$的选取无关. 得证.

自然数的序关系

序关系

在上一节中, 我们定义了等价关系, 等价关系的常见形式就是等于号. 现在, 基于朴素的不等号, 我们将它们的性质抽象出来定义序关系.

Def 严格序关系

设$\mathcal{R}$是$X$上的关系, $x,y,z$是$X$中的任意元素. 有如下性质:

反自反性: $\neg (x\mathcal{R}x)$
传递性: $(x\mathcal{R}y)\and(y\mathcal{R}z)\Rightarrow x\mathcal{R}z$
任两元素严格可比: $x\mathcal{R}y$, $x=y$和$y\mathcal{R}x$, 三者恰有一个为真

满足反自反性和传递性的关系, 称为 严格偏序关系; 满足任两元素严格可比的严格偏序关系, 称为 严格全序关系.

Def 非严格序关系

设$\mathcal{R}$是$X$上的关系, $x,y,z$是$X$中的任意元素. 有如下性质:

自反性: $x\mathcal{R}x$
反对称性: $(x\mathcal{R}y)\and(y\mathcal{R}x)\Rightarrow x=y$
传递性: $(x\mathcal{R}y)\and(y\mathcal{R}z)\Rightarrow x\mathcal{R}z$
任两元素可比: $(x\mathcal{R}y)\or(y\mathcal{R}x)$

满足自反性、反对称性和传递性的关系, 称为 (非严格)偏序关系; 满足任两元素可比的非严格偏序关系称为 (非严格)全序关系.

自然数的小于关系

von Neumann 构造利用集合的属于关系自动编码了自然数的大小关系. 观察前几个自然数: \[ \begin{aligned} 0\in 1\quad 1\in 2\quad 2\in 3 \end{aligned} \] 并且更一般地, \[ \begin{aligned} 0\in 3\quad 1\in 3\quad 2\in 3\quad 3\notin3 \end{aligned} \]

这提示我们定义:

Def 自然数集上的小于关系

$\omega$上的小于关系$<$是一种关系, 满足 \[ <:=\set{(m,n)\in\omega\times\omega|m\in n} \]

小于关系的严格全序性证明

为了证明小于关系是$\omega$上的严格全序关系, 需要一系列引理与定义. 先引入传递集的定义

Def 传递集

如果一个集合的任意元素都是该集合的子集, 则称这个集合是 传递集. 换言之, 称一个集合$A$为传递集, 若 \[ \forall x(x\in A\Rightarrow x\subset A) \]

现在引入第一个引理

Lemma$<_a$ 任意自然数都是传递集

▶

Proof

用$P(n):n\text{是传递集}$和分离公理来生成自然数集的子集 \[ T:=\set{n\in\omega|P(n)} \] 显然, $\empty$是传递集, $\empty\in T$. 现在任取$n\in T$和$y\in n^+$, 即$y\in n\cup\set{n}$. 分为两种情况:

$y\in n$, 因为$n$传递, 所以$y\subset n$. 又因为$n$是$n^+$的子集, 所以$y\subset n^+$;
$y\in \set{n}$(i.e., $y=n$), 直接可得$y\subset n^+$.

综上, 对于任意$T$的元素$n$, 其后继集$n^+$的任意元素都是$n^+$的子集, 即$n^+$传递, $n^+\in T$.

现在, 我们证明了$\empty\in T$, 也证明了$\forall n(n\in T\Rightarrow n^+\in T)$, 因此$T$是$\omega$的归纳子集, $\omega$已经是最小归纳集, 所以$T$就是$\omega$, $\omega$的全体元素满足传递集的性质. 得证.

证明传递集后, 就可以直接证明反自反性和传递性.

Theorem$<_1$ 自然数集上的小于关系满足反自反性

▶

Proof

反自反性要求$\forall n(n\in\omega\Rightarrow n\notin n)$. 用$P(n):n\notin n$和分离公理来生成自然数集的子集 \[ T:=\set{n\in\omega|P(n)} \] 显然, 任何元素不属于空集, 因此$0\notin 0$, 符合性质, 因此$0\in T$. 现在任取$n\in T$, 使用反证法, 假设$n^+\notin T$(i.e., $\neg P(n^+)$; 等价地, $n^+\in n^+$). 分两种情况:

$n^+\in n$. 考虑引理$<_a$, $n$是传递的, 所以$n$的元素$n^+$是$n$的子集, 即$n^+\subset n$. 又$n\in n^+$, 所以$n\in n$, 与前提$n\notin n$矛盾.
$n^+= n$, 又$n\in n^+$, 所以$n\in n$, 与前提$n\notin n$矛盾.

综上, 对任意$n\in T$, $n^+\notin T$不成立, 即$n^+\in T$. 结合$\empty\in T$, 因此$T$是归纳集. 又$T$是$\omega$的子集, $\omega$已经是最小归纳集, 所以$T$就是$\omega$, $\omega$的全体元素满足$n\notin n$, 即$(n,n)\notin <$, 得证.

Theorem$<_2$ 自然数集上的小于关系满足传递性

▶

Proof

对于定理$<_2$, 任取自然数$p\in\omega$, $n\in p$, $m\in n$. 由于$p$是传递集, 因此$n\subset p$. 又$m\in n$, 所以$m\in p$. 传递性得证.

Lemma$<_b$ 任意非零自然数$n$总含有元素$0$

▶

Proof

用性质$P(n):0=n\or0\in n$和分离公理来生成自然数集的子集 \[ T:=\set{n\in\omega|P(n)} \] 显然, $0$满足这一性质. 现在任取$n\in T$, 分为两种情况

$n=0$, 则$n^+=1$, $n^+$显然满足$0\in n^+$的性质, 也就属于$T$;
$0\in n$. 考虑到$n\subset n^+$, 则$0\in n^+$, 因此$n^+$属于$T$.

综上, $T$是归纳集. 又$T$是$\omega$的子集, $\omega$已经是最小归纳集, 所以$T$就是$\omega$, $\omega$的全体元素满足性质$P(n)$. 得证.

Lemma$<_c$ 对任意自然数$n$, 若$m\in n$, 则$m^+=n$或$m^+\in n$

▶

Proof

用性质$P(n):\forall m\in n\Rightarrow m^+=n\or m^+\in n$和分离公理来生成自然数集的子集 \[ T:=\set{n\in\omega|P(n)} \] 显然, $0$因为空真满足这一性质. 现在任取$n\in T$, $\forall y\in n^+$有两种情况:

$y\in n$, 则$y^+=n$或$y^+\in n$. 若$y^+=n$, 由$n\in n^+$得$y^+\in n^+$; 若$y^+\in n$, 由$n\subset n^+$得$y^+\in n^+$.
$y=n$. 则$y^+=n^+$.

综上, $\forall y\in n^+$, $y^+\in n^+\or y^+=n^+$, 即$n^+$满足性质$P(n)$. 从而$T$是归纳集. 又$T$是$\omega$的子集, $\omega$已经是最小归纳集, 所以$T$就是$\omega$, $\omega$的全体元素满足性质$P(n)$. 得证.

现在可以证明任两元素严格可比了. 因为有三个条件, 其中有且仅有一个成立, 所以需要证明三个条件两两不相容(至多一个成立), 还要证明三个条件中总存在成立的条件(至少一个成立).

Lemma$<_d$ 对于任意两个自然数, 任两元素严格可比的三个条件两两不相容

▶

Proof

任取自然数$m,n$

证明$m=n\Rightarrow \neg(m\in n)$:

由于小于关系(属于关系)在自然数集上具有反自反性, 因此$m=n$时, $\neg(m\in n)$.

同理, 基于等式的对称性可以证明$m=n\Rightarrow\neg(n\in m)$.
证明$m\in n\Rightarrow n\notin m$:

在$m\in n$的前提下, 假设$n\in m$成立, 因为$m$是传递集, 所以$n\in\ m\Rightarrow n\subset m$. 又$m\in n$, 故$m\in m$, 与反自反性矛盾.

Lemma$<_e$ 对于任意两个自然数, 任两元素严格可比的三种情形至少有一个成立

▶

Proof

将$m\in n\or m=n\or n\in m$记作$P_m(n)$, 三个条件至少有一个成立, 等价于性质$P_m(n)$成立, 对于固定的$m$, 可以分离出自然数集的一个子集 \[ T_m:=\set{n\in\omega|P_m(n)} \] 由引理$<_b$, $0$总满足$0=m\or0\in m$, 符合性质. 现在任取$n\in T_m$. 有三种情况

$m\in n$, 由于$n$是其后继的子集, 得$m\in n^+$;
$m=n$, 由于$n$是其后继的元素, 仍得到$m\in n^+$;
$n\in m$, 考虑引理$<_c$, 推出$n^+\in m\or n^+=m$.

综上, $n^+$总满足性质$P_m(n^+)$. 因此对任意自然数$m$, $T_m$都是$\omega$的归纳子集, 也就是$\omega$自身. 得证.

基于引理$<_d$和$<_e$, 可以证明定义小于关系后, 自然数集上的任两元素严格可比.

Theorem$<_3$ 自然数集上的小于关系满足任两元素严格可比

▶

Proof

引理$<_d$说明三个条件两两不相容, 至多有一个成立; $<_e$说明三个条件至少有一个成立. 综合可得恰有一个成立, 即小于关系使得自然数集上的任两元素严格可比, 得证.

高等微积分 > 逻辑与公理化集合论

#集合论 #ZF 公理系统 #无穷公理 #自然数集 #von Neumann 方案 #归纳集 #序关系

逻辑与公理化集合论(04)：无穷公理与自然数的构造

https://notes.rainchan.me/posts/逻辑与公理化集合论(04)：无穷公理与自然数的集合论构造/

作者

Rain Chan

发布于

2026年3月8日

许可协议

逻辑与公理化集合论(03)：序偶、直积、关系和函数下一篇

逻辑与公理化集合论(04)：无穷公理与自然数的构造

无穷公理与归纳集

Def 后继

Axiomatic System ZF公理系统的第6条(无穷公理)

Def 归纳集

自然数与最小归纳集

von Neumann 方案

最小归纳集的构造

Def 自然数集

Lemma \(\omega\)本身是归纳集, 并且它包含于任意归纳集.

自然数的序关系

序关系

Def 严格序关系

Def 非严格序关系

自然数的小于关系

Def 自然数集上的小于关系

小于关系的严格全序性证明

Def 传递集

Lemma\(<_a\) 任意自然数都是传递集

Theorem\(<_1\) 自然数集上的小于关系满足反自反性

Theorem\(<_2\) 自然数集上的小于关系满足传递性

Lemma\(<_b\) 任意非零自然数\(n\)总含有元素\(0\)

Lemma\(<_c\) 对任意自然数\(n\), 若\(m\in n\), 则\(m^+=n\)或\(m^+\in n\)

Lemma\(<_d\) 对于任意两个自然数, 任两元素严格可比的三个条件两两不相容

Lemma\(<_e\) 对于任意两个自然数, 任两元素严格可比的三种情形至少有一个成立

Theorem\(<_3\) 自然数集上的小于关系满足任两元素严格可比