集合与公理化

数理逻辑的最基础部分就是命题逻辑和谓词逻辑。这一部分介绍数理逻辑中用到的集合与公理化的知识。

集合的定义

对象：人们感觉和思维中确定的某些事物。

集合：具有某种性质的、确定的、互异的对象所组成的整体。

集合的表示可以使用外延表示方法（即列举法）和内涵表示方法（通过某一性质 $\phi$）。

罗素悖论

罗素悖论指出，并不是具有性质 $P$ 的元素所构成的就是集合，即概括原则是有问题的。我们通常只能把它称为类。

概括原则

如果 $\phi$ 是一个性质，那么存在一个集合 $A$，它的元素是所有具有性质 $\phi$ 的元素。由德国数学家弗雷格（$\mathrm{Frege}$）提出。

公理化方法

我们把公理看成正确的命题，然后通过这些公理通过纯粹的逻辑证明，就可以推演出其他定理。

$\mathrm{ZFC}$ 公理简述

外延公理 $\mathrm{Extensionality}$

如果 $X$ 和 $Y$ 有相同元素，则 $X=Y$。即

$$A=B\mathrm{iff}\mathrm{\forall }x\{x\in A\mathrm{iff}x\in B\}$$

由于仅靠外延公理并不能推出存在一个集合，那么就还需要集合存在公理。

在集合中加入新元素可以用以下的方式表示：对于集合 $A$，$A;t$ 表示了 $A\cup \{t\}$。

空集公理

存在一个集合，它不含任何元素。通常记为 $\mathrm{\varnothing }$。即： $\{x|x\ne x\}$ 是集合，我们把它定义为空集。

分离公理 $\mathrm{Separation}$

如果 $\phi$ 是一个性质，则对于任何集合 $A$ 和参数 $p$，存在一个集合 $B=\{u\in A:\phi (u,p)\}$，它包含所有有此性质的 $A$ 中的元素 $u$​。

无序对定理 $\mathrm{Pairing}$

对于任何 $a,b$，存在一个集合$\{a,b\}$，恰好含有元素 $a,b$。

幂集、交集和并集

幂集 $\mathcal{P}A$ ： 其元素是 $A$ 的所有子集。即 $\mathcal{P}A=\{x|x\subseteq A\}$。

并集和交集符号：

一般的并集和交集符号与中学阶段所学相同，下面的全并集和交集符号可以类比求和符号理解。

• $\bigcup A=\{x|x\mathrm{属}\mathrm{于}A\mathrm{中}\mathrm{的}\mathrm{某}\mathrm{个}\mathrm{元}\mathrm{素}\}$
• $\bigcap A=\{x|x\mathrm{属}\mathrm{于}A\mathrm{中}\mathrm{的}\mathrm{所}\mathrm{有}\mathrm{元}\mathrm{素}\}$

有序对

定义：元素 $x$ 和 $y$ 的有序对定义如下

$$⟨x,y⟩=⟨u,v⟩\mathrm{iff}x=u\mathrm{且}y=v$$

因此，所有具有上述性质的定义即可作为有序对定义。例如，$⟨x,y⟩=\{\{x\},\{x,y\}\}$ 就满足原则。那么 $n$ 元组就可以递归定义为 $⟨x_1,x_2,\cdots ,x_n⟩=⟨⟨x_1,x_2,\cdots ,x_{n-1}⟩,x_n⟩$。

笛卡尔积定义：$A\times B=\{⟨x,y⟩|x\in A,y\in B\}$​

关系与函数

关系 $\mathrm{R}$ 是有序对的集合。其定义域和值域如下所示：

• $\mathrm{dom}\mathrm{R}=\{x|⟨x,y⟩\in \mathrm{R}\}$
• $\mathrm{ran}\mathrm{R}=\{y|⟨x,y⟩\in \mathrm{R}\}$​
• $\mathrm{fld}\mathrm{R}=\mathrm{dom}\mathrm{R}\cup \mathrm{ran}\mathrm{R}$

如果 $⟨x,y⟩\in R$，那么我们称 $x$ 和 $y$ 有关系 $R$，记作 $xRy$。$R$ 的逆关系 $R^{-1}$ 定义为 $\{⟨y,x⟩|⟨x,y⟩\in R\}$。

如果一个关系 $R$ 满足自反性、对称性和传递性，那么我们称 $R$ 为等价关系。

函数的定义：给定定义在 $A\times B$ 上的二元关系 $F$，对于 $\mathrm{dom}\mathrm{F}$ 中的每一个 $x$，都有唯一的 $y$ 满足 $⟨x,y⟩\in F$。那么我们称 $F$ 为一个函数，$F$ 将 $A$ 映射到 $B$ 上，即 $F:A\to B$。对于 $F$ 中的元素，我们常常把 $xFy$ 记作 $F(x)=y$。

一般规定$\mathrm{dom}\mathrm{F}=A$。显然，$\mathrm{ran}\mathrm{F}\subseteq B$。

单射、满射和双射

• 单射（即一 $x$ 对应一 $y$）：对于 $x_1\ne x_2$，有 $f(x_1)\ne f(x_2)$。
• 满射（即 $\mathrm{ran}F\subseteq B$）：对于任意 $y$，都存在 $x$，使得 $f(x)=y$。
• 双射：即单射又满射。

这种记法可以推广到更高维度的函数，例如 $F:A\times B\times C\to D$。

偏序和良序关系

偏序（类比小于等于）：自反性、反对称性和传递性；

严格偏序（类比小于）：禁自反性、禁对称性和传递性；

线序：任意两个元素均可被比较；

良序：在线序的基础上，存在极小（极大）元，则称为良序。若不要求线序，则称为良基偏序。

自然数的集合

我们可以用集合论的方式来等价表示自然数。

设 $A$ 为任意的集合，我们称集合 $A\cup \{A\}$ 为 $A$ 的后继集合，简称 $A$ 的后继，记为 $A^{+}$。我们可以用空集来表示 $0$​​，这样就可以把每一个自然数，通过不断进行后继运算，表示成集合的形式。

例如：

• $0=\mathrm{\varnothing }$
• $1=\{\mathrm{\varnothing }\}$
• $2=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}=\{0,1\}$
• $n=\{0,1,2,\cdots ,n-1\}$

我们用所有自然数组成的集合的整体的集合记为 $\omega$。

数学归纳法

集合形式的数学归纳法 设 $S$ 是一个集合，如果 $S$ 满足如下两个条件，那么有

1. $0\in S$
2. 对于任何自然数 $n$，如果 $n\in S$，那么 $n+1\in S$ 那么 $\omega \in S$​。

数学归纳法需要使用正则公理来证明。数学归纳法是建立在公理体系上的。

正则公理

在每个非空集合 $A$ 中，必然存在一个元素 $x$，使得 $x\cap A=\mathrm{\varnothing }$。此时，我们称 $x$ 为 $A$ 的 $\in$-极小元。

例如，在集合 $\{0,1,2,3\}$ 中，我们可以找到 $0$，使得 $0\cap \{0,1,2,3\}=\mathrm{\varnothing }$。而其他的元素则不满足这个条件，如$1\cap \{0,1,2,3\}=\{0\}$。

根据正则公理，我们可以推出：不存在集合 $A$，使得 $A\in A$。

证明的主要思路是通过反证法，假设 $\omega$ 不是 $S$ 的子集，那么根据正则公理，我们可以在集合 $\omega -S$ 中找到一个 $\in$-极小元 $m$，这个极小元就是 $\omega -S$ 的最小元素，而这与数学归纳法的条件矛盾。首先，这个极小元不为 $0$，因为 $0\in S$，进而我们就可以找到 $m$ 的前驱 $m-1$。如果 $m$ 是极小元，那么 $m-1$ 就一定是 $S$ 的元素，这又根据假设推出 $m$ 也是$S$ 的元素，矛盾。$◻$

传递集合

定义 对于任意 $x,y$，当 $x\in A$ 并且 $y\in x$ 时，有 $y\in A$，那么称 $A$ 为传递集合。

简单结论（必须会用数学归纳法证明）：每个自然数都是传递集合；若 $\omega$ 是传递集合，即对任意自然数 $n$ 都有，$n$ 是 $\omega$ 的子集合；对于任意自然数 $n,m$，如果 $n\subseteq m$，那么 $n=m$ 或者 $n\in m$。

三歧性（大于小于等于）：称集合 A 具有 $\in -\mathrm{三}\mathrm{歧}\mathrm{性}$，如果对于任意 $x,y\in A$ 都有集合 $x\in y\mathrm{或}x=y\mathrm{或}y\in x$。那么 $\omega$ 具有 $\in -\mathrm{三}\mathrm{歧}\mathrm{性}$。

等势集合

设 $A,B$ 为两个集合，如果存在 $A$ 到 $B$ 上的双射，则称 $A$ 和 $B$ 等势，记作 $A\sim B$。等势关系显然是等价关系。

设 $A,B$ 为两个集合，如果存在 $A$ 到 $B$ 上的单射，那么称 $A$ 的势不大于 $B$ 的势，记作 $A⪯B$。如在此基础上还有 $A$ 和 $B$ 不等势，那么称 $A$ 的势小于 $B$ 的势，记作 $A\prec B$。

常见的等势关系

• ${\omega }^{+}\sim \omega$
• $\mathbb{Z}\sim \omega$
• $\omega \times \omega \sim \omega$ ，这是因为有配对函数 $\pi$$$\pi (m,n)=\frac{(m+n{)}^2+m+3n}{2}$$

康托尔-伯恩斯坦定理

设 $A$ 和 $B$ 是两个集合，若 $A⪯B$ 且 $B⪯A$，那么 $A\sim B$​。

证明 不妨设 $f:A\to B$ 和 $g:B\to A$ 是两个单射，那么我们令 $A_0=A-g(B),B_0=f(A_0)$，然后构造 $A_{n+1}=g(B_n),B_n=f(A_n)$，令 $M=\bigcup _{n\in \omega }{A}_n$，$N=\bigcup _{n\in \omega }{B}_n$。显然，$M$ 和 $N$ 分别是 $A$ 和 $B$ 的子集。

下面我们定义映射 $h:A\to B$。

$$h(x)=\{\begin{array}{ll}f(x)& x\in M\\ g^{-1}(x)& x\in A-M\end{array}$$

下面证明 $h$ 是一个双射。

1. $h$ 是一个单射：即对于 $x_1,x_2\in A$，如果 $x_1\ne x_2$，那么 $f(x_1)\ne f(x_2)$。
   i. 若 $x_1,x_2\in M$，那么由 $f$ 是单射， 得$f(x_1)\ne f(x_2)$；
   ii. 若 $x_1,x2\in A-M$，那么 $x_1,x_2\in \mathrm{ran}g$（因为，$x\notin M$ 且 $A_0=A-g(B)=A-\mathrm{ran}g\subseteq M$，那么 $x\notin A-\mathrm{ran}g$，即 $x\in \mathrm{ran}g$）。由于 $g$ 是单射，则 $g^{-1}$ 也是单射，同理可证；
   iii. 若 $x_1\in M$，$x_2\in A-M$，那么 $h(x_1)=f(x_1),h(x_2)=g^{-1}(x_2)$。假设 $h(x_1)=h(x_2)$。由于 $x_1\in M$ 那么必然存在 $n\in \omega$ 使得 $x_1\in A_n$，则 $f(x_1)=g^{-1}(x_2)\in B_{n+1}\subseteq N$。此时，由于 $g^{-1}(x_2)\in B_{n+1}$，由定义我们可以推出 $x_2=g(g^{-1}(x_2))\in A_{n+2}\subseteq M$，但这与 $x_2\in A-M$ 矛盾。因此，$h(x_1)\ne h(x_2)$。$x_1\in A-M$，$x_2\in M$ 的情况同理可证。

2. $h$ 是一个满射：即对于任意的 $y\in B$，都存在 $x\in A$，使得 $h(x)=y$。我们也分两种情况说明。
   i. 假设 $y\in N$，那么由定义显然存在 $n\in \omega$ 使得 $y\in B_n$，那么由于 $B_n=f(A_n)$，则必然存在 $x\in A_n\subseteq M$ 使得 $f(x)=y$，即 $h(x)=y$；
   ii. 假设 $y\in B-N$，那么 $g(y)$ 是 $A-M$ 的元素（考虑反证法），故 $h(g(y))=g^{-1}(g(y))=y$。

因此，$h$ 是一个双射，即 $A\sim B$。$◻$