逻辑与公理化集合论(02)：从朴素集合论到 ZF 公理系统下的集合论

在上一篇文章中, 我们建立了精确的逻辑语法, 然而, 为了辅助说明一些概念, 实数集和属于关系在未定义的情况下被使用, 现在是时候偿还这笔逻辑债务了. \(\newcommand{\set}[1]{\left\{ #1 \right\}}\newcommand{\abs}[1]{\left| #1 \right|}\newcommand{\tr}[1]{\text{tr}\left( #1 \right)}\renewcommand{\R}{\mathbb{R}}\renewcommand{\K}{\mathbb{K}}\renewcommand{\exist}{\exists}\renewcommand{\and}{\land}\renewcommand{\or}{\lor}\renewcommand{\empty}{\varnothing}\renewcommand{\subset}{\subseteq}\renewcommand{\supset}{\supseteq}\)

朴素集合论与 Russell 悖论

朴素的集合定义非常自由, 任何可以通过语言或性质描述的对象的全体, 都可以构成一个集合. 对于任意性质\(P(x)\), 都存在一个集合\(A\), \(A\)囊括了所有满足性质\(P(x)\)的\(x\). 即 \[ \forall x(x\in A\Leftrightarrow P(x)) \] 这里的\(x\)通常称为 元素, 元素本身也可以是另一些元素的集合, 这有点类似于编程领域的嵌套列表, 区别是列表是有序结构, 并且允许重复枚举已出现的元素.

Russell 悖论

1901年, Russell 提出了一个性质\(R(x)\), 其指代"对任意\(x\), \(x\)不属于\(x\)"的性质 \[ R(x): x\notin x \] 下面我们证明, 这条性质与朴素集合论冲突.

▶

Proof

按照朴素集合论的精神, 必然存在一个集合\(R\)对应于性质\(R(x)\). 根据排中律, \(R\in R\)要么是真命题, 要么是假命题(即\(R\notin R\)).

1. 若\(R\in R\)

   既然\(R\)也是\(R\)中的元素, 其必然满足性质\(R(x)\), 即\(R(R):R\notin R\), 与\(R\in R\)矛盾.

2. 若\(R\notin R\)

   这个情形的条件刚好符合性质\(R(x)\), 由集合\(R\)的构造性质, 直接导出\(R\in R\), 矛盾.

   综上所述, 该性质\(R(x)\)不存在(朴素意义上的)集合与之对应.

Remark

Russell 悖论的一个通俗诠释是所谓的"理发师悖论": 一个村子里有位理发师, 他宣称自己"给且只给所有不自己理发的人理发", 那么无论他给自己理发还是不理发, 都与宣称相矛盾.

ZFC 公理系统

为了解决 Russell 悖论, 需要节制构造集合的方法. 为此, Zermelo 和 Fraenkel 提出了 ZF 公理系统. 这里介绍其前3条公理.

集合的构造, 并集与交集运算

Axiomatic System ZF公理系统的1~3条

1. 外延公理: 集合\(A\)和集合\(B\)相等当且仅当元素相同 \[ \forall A\forall B(A=B\Leftrightarrow\forall x(x\in A\Leftrightarrow x\in B)) \]

2. 分离公理: 任何集合\(A\)和性质\(P(x)\)都对应一个集合\(B\), 其中元素是且仅是\(A\)中具有性质\(P(x)\)的元素 \[ \forall A\forall P\exist B(\forall x (x\in B\Leftrightarrow(x\in A\and P(x)))) \]

3. 并集公理: 对于任何"集合之集合"\(\mathcal{M}\), 存在集合被称作"\(\mathcal{M}\)的并集", 记作\(\cup\mathcal{M}\), 其元素是且仅是\(\mathcal{M}\)中所有元素的元素 \[ \forall\mathcal{M}\exist\cup\mathcal{M}(\forall x(x\in\cup\mathcal{M}\Rightarrow\exist X(x\in X\and X\in\mathcal{M}))) \]

外延公理的作用是定义集合的相等. 分离公理取代了朴素集合论的构造方法, 要求不能根据任意性质\(P\)就构造新集合, 而是只能从已有集合\(A\)中挑选出符合性质\(P\)的全体元素组成新集合. 并集公理主要是定义了并集运算的存在性.

利用分离公理可以定义交集. 考虑原集合为\(\cup\mathcal{M}\), 性质\(P(x)\)是\(x\)属于\(\mathcal{M}\)的每个元素即可.

Def 交集

集合族\(\mathcal{M}\)的 交集 是如下记作\(\cap\mathcal{M}\)的集合 \[ \cap\mathcal{M}:=\set{x\in \cup\mathcal{M}|\forall X(X\in\mathcal{M}\Rightarrow x\in X)} \]

空集, 子集, 差集运算

利用分离公理可以定义空集, 外延公理可以证明空集的唯一性(略).

Def 空集

基于任意集合\(A\)和性质\(P(x): x\neq x\)生成的集合, 叫做 空集, 符号为\(\empty\). \[ \empty:=\set{x\in A|x\neq x} \]

子集的定义并不依赖于分离公理(当然分离公理产生的一定是子集), 只需要集合和逻辑符号即可.

Def 子集和真子集

称一个集合\(X\)是集合\(Y\)的 子集, 若\(X\)中的任何元素一定在\(Y\)中, 记作\(X\subset Y\) \[ X\subset Y\Leftrightarrow \forall x (x\in X\Rightarrow x\in Y) \] 如果\(Y\)的子集\(X\)与\(Y\)不等, 称\(X\)是\(Y\)的 真子集, 记作\(X\subsetneq Y\) \[ X\subsetneq Y \Leftrightarrow X\subset Y\and X\neq Y \]

如果把\(x\in A\)和\(x\in B\)看成两条开语句, 则并集和交集有点像转化为命题后的或运算和与运算. 我们可能还需要一种"非"运算, 但对于集合而言, \(x\notin A\)只是一条性质, 不足以构成新集合, 也就是无法找到"万物之集合", 在上面定义绝对的补集运算; 取而代之的是, 对于\(A\), 如果它具有超集\(U\), 就可以定义(相对的)补运算

Def 补集运算

设\(A\)是\(U\)的子集, 称一个集合\(\complement_U A\)是\(A\)在\(U\)中的 补集, 若 \[ \complement_U A=\set{x\in U|x\notin A} \]

更普遍地, 如果把子集关系推广为任意情形, 可以定义差集运算

Def 差集运算

设\(A\), \(B\)是两个集合, 称一个集合\(A\backslash B\)是\(A\)与\(B\)的 差集, 若 \[ A\backslash B=\set{x\in A|x\notin B} \]

集合运算的性质

现在我们有了三种运算: 并集, 交集和差集. 理解了前述的公理化定义后, 给定三个合法的集合\(A,B,C\), 则三种运算的二元情形可以被逻辑语句简单地表示:

• \(\forall x(x\in (A\cup B)\Leftrightarrow x\in A \or x\in B)\)
• \(\forall x(x\in (A\cap B)\Leftrightarrow x\in A \and x\in B)\)
• \(\forall x(x\in A\backslash B\Leftrightarrow x\in A\and x\notin B)\)

它们具有下列运算性质

三种集合运算的性质

1. 并集运算具有交换律和结合律

   1. 交换律: \(A\cup B=B\cup A\)
   2. 结合律: \((A\cup B)\cup C=A\cup (B\cup C)\)

2. 交集运算具有交换律和结合律

3. 并集、交集的混合运算具有分配律 \[ \begin{aligned} (A\cap B)\cup C&=(A\cup C)\cap (B\cup C) \\ (A\cup B)\cap C&=(A\cap C)\cup (B\cap C) \end{aligned} \]

4. 并集或交集与第三集的差集具有 De Morgan 律

\[ \begin{aligned} C\backslash (A\cap B)&=(C\backslash A)\cup (C\backslash B) \\ C\backslash (A\cup B)&=(C\backslash A)\cap (C\backslash B) \end{aligned} \]