集合及其运算

集合的直观概念

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

集合的性质

确定性. 对于任意给定的集合 `A` 和 `a`, 一定有 `a` 属于 `A` 和 `a` 不属于 `A` 之一成立, 分别记为 `a in A`, `a !in A`. 当 `a in A` 时, 称 `a` 是 `A` 的元素或成员或点. 常用大写字母 `A, B, C` 等表示集合, 小写字母 `a, b, c` 等表示元素. 注意集合的元素也是集合, 因而它们没有本质区别.
互异性. 集合中没有两个相同的元素, 或者说, 任意元素在集合中都只出现一次. 在形式上, 有时我们会把一个集合写成 `{x, y, x}`, `{x, x, y, y}`, 等. 它们和 `{x, y}` 是相同的集合.
无序性. 元素在集合中的出现次序是无关紧要的, 比如 `{1, 2, 3}` 和 `{2, 3, 1}` 是同一个集合.

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

集合的表示

列举法. 如 `A = {a, b, c}`, `B = {1, 2, cdots, 10}`, `C = {{a}, {b}, {c}}`. 这里 `C` 是集合的集合, 与 `A` 不同. 同理单元素集合 `{a}` 与元素 `a` 不同, 应区分对待.
描述法. 用谓词描述集合元素的公共特征. `S = {x: P(x)}` 表示 `x in S` 当且仅当命题 `P(x)` 成立.

集合论的 ZFC 公理系统

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

论述域

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

语法符号

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

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

造句规则

对论述域中的任意集合 `x, y`, 规定 `x = y`, `x in y` 都是合法语句, 称为原子语句;
若 `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)` 都是合法语句.
若 `varphi` 是合法语句, 则 `(AA x) varphi`, `(EE x) varphi` 是合法语句;
有限次运用上面的规则所得的句子都是合法语句.

由于 `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`

公理组

存在公理 (existence axiom) 或空集公理 (empty axiom);
外延公理 (extensionality axiom);
配对公理 (pair axiom);
并公理 (union axiom);
幂集公理 (power set axiom);
子集公理图式 (subset axiom schema), 又称分离公理图式 (separation axiom schema) 或概括公理图式 (comrehension axiom schema);
无限公理 (infinity axiom);
取代公理图式 (replacement axiom schema);
选择公理 (choice axiom);
基础公理 (foundation axiom) 又称正则公理 (regularity axiom).

集合的基本关系

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

集合的基本关系

包含 `A sube B iff (a in A rArr a in B) iff AA a (a in A rarr a in B)`. 此时称 `A` 含于 `B`, 或 `B` 包含 `A`, 或 `A` 是 `B` 的子集;
相等由外延公理知道. `A = B iff A sube B ^^ B sube A`. 依上述定义, 两个集合相等当且仅当它们所含的元素相同, 而与元素的次序和重复次数无关, 如 `{a, b, c} = {a, c, b} = {a, b, c, b}`. 此即集合元素的互异性与无序性.
真包含 `A subne B iff A sub B iff A sube B ^^ A != B`. 此时称 `A` 真包含于 `B`, 或 `B` 真包含 `A`, 或 `A` 是 `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)`.

`B = {x in A: x !in x}`,

如果 `B in B` 真, 由 `B` 定义, `(B in A) ^^ (B !in B)` 真, 于是 `B !in B` 真, 矛盾;
如果 `B in B` 假, 由 `B` 定义, `(B in A) ^^ (B !in B)` 假, 由于 `B in A` 真, 所以 `B !in B` 假, 矛盾.

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

全体集合不构成集, 而是一个真类.

集合族的交与并

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

对任意非空集合 `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/` 有意义, 从逻辑上可以证明任意集合都是它的元素, 从而引出 Russell 悖论: `x in nnn O/` `iff AA A in O/ (x in A)`, 然而 `A in O/` 为假, 所以上式恒为真. 但不存在包含任意元素的集合. 矛盾.

并公理 对任意集合 `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`.

交换律 `A nn B = B nn A`, `quad A uu B = B uu A`.
结合律 `(A nn B) nn C = A nn (B nn C)`, `quad (A uu B) uu C = A uu (B uu C)`.
分配律 `(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)`.
对偶律 `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`.
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`.