集合的直观概念

集合, 又叫做集或搜集, 是数学中极少数不加定义的 "元概念" 之一. 一般把集合理解为具备某个性质的对象的全体. 注意这里的性质并不是随意指定的, 否则会引出矛盾 (称为悖论, 我们在下文讨论它).

集合的性质

取消集合的互异性, 允许同一元素在集合中出现多次, 得到的概念称为多重集, 类或族.

集合的表示

    由集合的确定性知, 只要能够确定集合中的元素, 也就确定了这个集合. 一个集合可以有多种表示方式.
  1. 列举法. 如 `A = {a, b, c}`, `B = {1, 2, cdots, 10}`, `C = {{a}, {b}, {c}}`. 这里 `C` 是集合的集合, 与 `A` 不同. 同理单元素集合 `{a}` 与元素 `a` 不同, 应区分对待.
  2. 描述法. 用谓词描述集合元素的公共特征. `S = {x: P(x)}` 表示 `x in S` 当且仅当命题 `P(x)` 成立.

集合论的 ZFC 公理系统

由 E.Zermelo (1908) 首次提出公理系统的框架, A. Fraenkel (1922) 补充了一条替换公理模式, 再加上 Zermelo 提出的选择公理 (choice axiom), 组成今天通用的 ZFC 公理系统. 这一公理系统包括论述域、语法符号、造句规则与公理组.

ZFC 并不是唯一的公理集合论系统. 比较出名的公理系统还有 NBG (von Neumann-Bernays-Gödel)、类型论 (type theory) 等.

论述域

我们的公理涉及的对象称为集合 (set), 一般用拉丁字母 `A, B, C, cdots`; `a, b, c, cdots` 等来表示. 在集合论的各种场合下, 往往有一个集合 `Omega` 包含了我们讨论的所有集合. 称 `Omega` 为全集或论述域.

语法符号

逻辑等号 `=`
从属符号 `in`
逻辑连词符号 `not, vv, ^^, rarr, harr`
量词符号 `EE, AA`
分界符 `(,)`

为书写清晰起见, 引入更多的的分界符 `[], {}`. 在命题公式中, 它们与 `()` 视为同一种符号.

造句规则

    合式公式 我们来规定什么样的命题 `P(x)` 才是合法的.
  1. 对论述域中的任意集合 `x, y`, 规定 `x = y`, `x in y` 都是合式公式, 称为原子语句;
  2. 若 `varphi, psi` 是合式公式, 则 `not varphi`, `varphi ^^ psi`, `varphi vv psi` 都是合式公式; 由此定义, `varphi rarr psi iff not varphi vv psi` 和 `varphi harr psi iff (varphi rarr psi) ^^ (psi rarr varphi)` 都是合式公式.
  3. 若 `varphi` 是合式公式, 则 `(AA x) varphi`, `(EE x) varphi` 是合式公式;
  4. 有限次运用上面的规则所得的句子都是合式公式.

由于 `x in y` 恒为合式公式, 所以一切集合间都可以判断从属关系. 这就是集合的确定性.

语句 简写
`not(x in S)` `x !in S`
`x in S ^^ y in S` `x, y in S`
`x !in S ^^ y !in S` `x, y !in S`
`EE x (x in S rarr varphi)` `EE x in S, varphi`
`AA x (x in S rarr varphi)` `AA x in S, varphi`

公理组

  1. 外延公理 (extensionality axiom);
  2. 空集公理 (empty axiom), 或存在公理 (existence axiom);
  3. 子集公理模式 (subset axiom schema), 又称分离公理模式 (separation axiom schema) 或概括公理模式 (comrehension axiom schema);
  4. 替换公理模式 (replacement axiom schema);
  5. 并公理 (union axiom);
  6. 配对公理 (pair axiom);
  7. 幂集公理 (power set axiom);
  8. 正则公理 (regularity axiom), 又称基础公理 (foundation axiom).
  9. 无限公理 (infinity axiom);
  10. 选择公理 (choice axiom);

集合的基本关系

外延公理 两集合 `A, B` 相等当且仅当对任意 `a`, `a in A` 等价于 `a in B`: `A = B iff AA a(a in A harr a in B)`.

以下几条公理肯定了几类集合的存在性, 再由外延公理, 可保证它们的惟一性.

空集公理

空集公理 存在一个不含任何元素的集合: `EE E AA x (x !in E)`. 应用外延公理可证明这个集合 `E` 惟一, 称为空集 (empty set), 记为 `O/`.

设 `EE O/' AA x (x !in O/')`. 从而 `AA x`, `x in O/` 和 `x in O/'` 都为假, 于是 `AA x(x in O/ harr x in O/')`, 即 `O/ = O/'`.

子集公理模式、替换公理模式

之所以叫做公理模式, 是因为它们是公理的模板, 每输入一个合式公式, 就有一条相应的公理.

子集公理模式 设 `varphi` 是一个语句, 其中 `x` 是 `varphi` 的自由变元 (即 `x` 没有被量词 `EE`, `AA` 所约束), 且 `A` 不在 `varphi` 中出现. 则存在 `A` 的子集 `S`, 使得 `S` 包含所有使 `varphi(x)` 成立的 `A` 的元素 `x`: `AA A EE S AA x (x in S harr x in A ^^ varphi(x))`. 应用外延公理可证这个集合 `S` 是惟一的, 因此定义 `S := {x: x in A ^^ varphi(x)} = {x in A: varphi(x)}`.

子集公理模式允许我们用任何一个特征描述 (即命题) 从一个给定集合中得到一个子集.

不存在一个包含任意元素的集合: `AA A EE B (B !in A)`.

    令 `varphi(x) := x !in x`. 应用子集公理, 记 `B = {x in A: x !in x}`, 下证 `B !in A`. 我们反设 `B in A`, 则
  1. 如果 `B in B` 真, 由 `B` 定义, `(B in A) ^^ (B !in B)` 真, 于是 `B !in B` 真, 矛盾;
  2. 如果 `B in B` 假, 由 `B` 定义, `(B in A) ^^ (B !in B)` 假, 由于 `B in A` 真, 所以 `B !in B` 假, 矛盾.
    3. 综上有 `B !in A`.

此定理的证明可以看出, 如果假定存在一个 "包罗万象" 的集合, 亦即假定可以用任何一个特定描述来定义一个集合, 而不指定其范围的话, 就会引出两难的矛盾, 这就是著名的 Russell 悖论 (1902). Russell 悖论的一个流行的说法是: 有一理发师, 声称自己只给那些不给自己理发的人理发. 那么他给不给自己理发呢? 假如他给自己理发, 按规定他应该属于那些不给自己理发的人, 一个矛盾; 假如他不给自己理发, 则按规定, 他应该给自己理发!

全体集合不构成集合, 这意味着 "全体集合" 的概念已是一个超越了集合的概念, 不在 ZFC 集合论的体系内. 我们暂时把这种不构成集合的一些集合的全体称为真类, 而把集合与真类统称为类. 后面还会遇到一些真类的例子, 如全体归纳集、全体序数等.

替换公理模式 设 `F` 是一个以集合 `X` 为定义域的函数, 则存在集合 `F(X) = {F(x): x in X}`.

这里的函数并不是集合论中通常定义的函数, 而是由合式公式定义的. 例如, 函数 `x mapsto y` 可以用带有两个自由变元的合式公式 `varphi(x, y)` 解释为 `AA x EE! y varphi(x, y)`.

集合族的交与并

习惯上称集合的集合为集合族.

对任意非空集合 `cc A`, 存在集合 `I`, 使得 `x in I` 当且仅当对任意 `cc A` 的元素 `A` 都有 `x in A`: `AA cc A (cc A != O/ rarr EE I AA x(x in I harr AA A(A in cc A rarr x in A)))`. 由外延公理可证集合 `I` 惟一, 称为 `cc A` 的交 (intersection), 记为 `I = nnn cc A` `:= {x: AA A in cc A, x in A}`.

由 `cc A != O/`, 所以 `EE A_1 in cc A`. 令 `varphi(x) := AA A (A in cc A rarr x in A)`. 由子集公理, 记 `I := {x in A_1: varphi(x)}` `= {x in A_1: AA A(A in cc A rarr x in A)}`. 于是 `x in I` 当且仅当 `x in A_1 ^^ AA A(A in cc A rarr x in A)`. 由于 `A_1 in cc A`, 这又当且仅当 `AA A(A in cc A rarr x in A)`, 即为所求的集合.

这里我们没有单独设一条公理, 而是从子集公理, 直接推出交集的存在性. 毕竟, 交集是一种特殊的子集.

注意 `A = O/` 时, 无法使用子集公理. 所以 `nnn O/` 无意义. 事实上如果 `nnn O/` 有意义, 从逻辑上可以证明任意集合都是它的元素: `x in nnn O/` `iff AA A in O/ (x in A)`, 然而 `A in O/` 为假, 所以 `x in A` 恒为真. 因而 `nnn O/` 包含了所有集合的全体, 它是一个真类, 这在 ZFC 中是犯规的.

并公理 对任意集合 `cc A`, 存在集合 `U`, 使得 `x in U` 当且仅当存在 `cc A` 的元素 `A`, 使得 `x in A`: `AA cc A EE U AA x` `(x in U harr EE A(A in cc A ^^ x in A))`. 应用外延公理可证集合 `U` 惟一, 称为 `cc A` 的并 (union), 记为 `U = uuu cc A` `:= {x: EE A in cc A, x in A}`.

集合的代数运算

集合代数运算的定义

配对公理 对任意集合 `A, B`, 存在集合 `C`, 使得 `x in C` 当且仅当 `x = A` 或 `x = B`: `AA A AA B EE C` `(x in C harr x = A vv x = B)`. 由外延公理可证 `C` 惟一. 称 `C` 为 `A, B` 的无序对 (unordered pair). 记为 `C = {A, B}`.
特别, `AA x, {x, x} = {x}` 称为单点集 (singleton).

两集合的交与并 对任意集合 `A, B`, 由配对公理, 存在 `C = {A, B}`, 再定义 `A nn B := nnn C`, `A uu B := uuu C`. 于是 `A nn B`, `A uu B` 都是惟一确定的. 可以验证, `A nn B = {x: x in A ^^ x in B}`,
`A uu B = {x: x in A vv x in B}`.

集合的差与补 对任意集合 `A, B`, 令 `varphi(x) := x !in B`, 对 `A` 应用子集公理知, 存在惟一的集合 `A\\B = A-B := {x: x in A ^^ x !in B}`, 称为 `A, B` 的差 (difference).
设 `X` 为全集, 对任意 `A sube X`, 称 `X\\A` 为 `A` 的补集 (或余集, complement), 记为 `A^c = bar A = complement_X A := X \\ A = {x in X: x !in A}`. 定义集合 `A, B` 的对称差: `A triangle B := (A \\ B) uu (B \\ A) = (A uu B) \\ (A nn B)`.

幂集公理 对任意集合 `X`, 都存在集合 `P`, 使得 `S in P` 当且仅当 `S sube X`: `AA X EE P AA S(S in P harr S sube X)`. 由外延公理可证 `P` 惟一, 称为 `X` 的幂集 (power set), 记为 `2^X = cc P(X) := {S: S sube X}`. 采用 `2^X` 这样的记号是因为, 若 `|X| = n`, 则 `|2^X| = 2^n`, 其中 `|X|` 表示集合 `X` 的基数. 对有限集而言, 就是 `X` 中元素的个数. 无限集的基数将在后面讨论. 注意区分幂集与集合族的并这两个概念.
把 `2^X` 的子集称为 `X` 的子集族. 如果 `tau` 是 `X` 的子集族, 那么 `tau sube 2^X`, 即 `tau in 2^(2^X)`.

`P = 2^X rArr X = uuu P`.

集合的运算律

`AA A in cc A, A sube B iff uuu cc A sube B`,
`AA A in cc A, B sube A iff B sube nnn cc A`.

`(A^c)^c = A`, `quad` `A \\ B = A nn B^c`, `quad` `A = (A nn B) uu (A \\ B)`,
`A sube B rArr B^c sube A^c`, `quad` `A nn B = O/ iff A sube B^c`, `quad` `A \\ B = O/ iff A sube B`,
`(EE C) A triangle C = B triangle C iff A = B`,
`(EE C) A nn C = B nn C and A uu C = B uu C iff A = B`.

一个记号 设 `f(A)` 是关于集合 `A` 的某种运算 (交, 并, 差, 补等), 简记 `nnn_(A in cc A) f(A) = nnn{f(A): A in cc A}` `:= nnn{F: EE A in cc A, F = f(A)}`,
`uuu_(A in cc A) f(A) = uuu{f(A): A in cc A}` `:= uuu{F: EE A in cc A, F = f(A)}`. 因此 `nnn cc A = nnn_(A in cc A) A`, `quad uuu cc A = uuu_(A in cc A) A`.

  1. 交换律 `A nn B = B nn A`, `quad A uu B = B uu A`.
  2. 结合律 `(A nn B) nn C = A nn (B nn C)`, `quad (A uu B) uu C = A uu (B uu C)`.
  3. 分配律 `(A nn B) uu C = (A uu C) nn (B uu C)`, `quad (A uu B) nn C = (A nn C) uu (B nn C)`,
    `(nnn cc A) uu B = nnn_(A in cc A) A uu B`, `quad (uuu cc A) nn B = uuu_(A in cc A) A nn B`,
    `(nnn cc A) uu (nnn cc B) = nnn_(A in cc A, B in cc B) A uu B`, `quad (uuu cc A) nn (uuu cc B) = uuu_(A in cc A, B in cc B) A nn B`.     但一般不成立 `uuu_(i in I) nnn_(j in J) A_(i, j)` `= nnn_(j in J) uuu_(i in I) A_(i, j)`.
  4. 对偶律 `X\\(A nn B) = (X\\A) uu (X\\B)`, `quad X\\(A uu B) = (X\\A) nn (X\\B)`,
    `X\\nnn cc A = uuu_(A in cc A) X\\A`, `quad X\\uuu cc A = nnn_(A in cc A) X\\A`.
  5. De Morgan 公式 `(A nn B)^c = A^c uu B^c`, `quad (A uu B)^c = A^c nn B^c`,
    `(nnn cc A)^c = uuu_(A in cc A) A^c`, `quad (uuu cc A)^c = nnn_(A in cc A) A^c`.

正则公理

正则公理 对任意非空集合 `A`, 存在 `a in A` 满足 `a nn A = O/`: `AA A(A != O/ rarr EE a(a in A ^^ a nn A = O/))`. 正则公理保证了不存在无穷的从属链 `x_1 ∋ x_2 ∋ cdots`, 特别地, 不会有 `x in x`, `x in y in x` 的情况. 因为正则公理排除了 `x in x` 的情况, 所以 Russel 悖论不会出现.

  1. 我们来证明 `x in x` 是不成立的. 只需考虑单点集 `{x}`, 由正则公理知存在 `a in {x}` 满足 `a nn {x} = O/`. 这里 `a = x`, 于是 `x nn {x} = O/`, 即 `x !in x`.
  2. 我们证明 `x in y`, `y in x` 是不可能同时成立的. 否则考虑集合 `{x, y}`, 由正则公理知存在 `a in {x, y}` 满足 `a nn {x, y} = O/`. 但不论 `a = x` 或 `y`, 这个交集都不可能为空, 得到矛盾.
  3. 我们证明无穷的从属链 `x_1 ∋ x_2 ∋ cdots` 是不可能成立的. 否则考虑集合 `X = {x_1, x_2, cdots}`. 由正则公理知存在 `x_n in X` 满足 `x_n nn X = O/`. 然而这与 `x_(n+1) in x_n` 矛盾.