第八课：集合论、集合运算¶
Page 2 — 集合论概念¶
- 集合论以集合概念为基础，研究集合的一般性质
- "集合"是比"数"更简单的概念——用集合定义"数"和"运算"
- 集合是不定义的基本概念——一些确定的、相异的事物的总体
- 有限集合 vs 无限集合
Page 3-8 — 集合论与无限¶
- 康托尔（G.Cantor, 1845-1918）：1873年创立集合论
- 潜无限：作为过程的无限（如自然数列1,2,3...永远写不完）
- 实无限：作为已完成整体的无限（如自然数全体{1,2,3,...}）
- 亚里士多德只承认潜无限，不承认实无限
- 伽利略发现不等长线段上的点可以一一对应
- 康托尔区分了两种无限：
- 可数集：与自然数一一对应
- 连续统的势：与实数区间[0,1]一一对应
- 朴素集合论 → 罗素悖论 → 第三次数学危机 → 公理化集合论
Page 9-11 — 集合的基本概念¶
- 元素：集合中的对象，记作a∈A / a∉A
- 空集∅：不含任何元素的集合（唯一！）
- 子集A⊆B：A中每个元素都是B的元素
- 真子集A⊂B：A⊆B且A≠B
- 全集U：所讨论的全部对象
- 集合的表示：
- 列举法：{1,2,3}
- 描述法：{x|x的性质}
- 归纳定义：基础条款+归纳条款+终极条款
Page 12-13 — 集合相等¶
- A=B ⟺ A⊆B 且 B⊆A
- 空集唯一性：∅是唯一的空集
- ∈与⊆的区别：a∈A（a是A的元素），B⊆A（B的每个元素都是A的元素）
Page 14-17 — 集合运算¶
| 运算 | 记法 | 定义 |
|---|---|---|
| 并 | A∪B | {x |
| 交 | A∩B | {x |
| 差 | A−B | {x |
| 补 | ~A | {x |
| 对称差 | A⊕B | (A−B)∪(B−A) |
Page 18-27 — 集合运算性质¶
- 交换律：A∪B=B∪A, A∩B=B∩A
- 结合律：(A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C)
- 分配律：A∩(B∪C) = (A∩B)∪(A∩C)
- 德摩根律：
- ~(A∪B) = A∩B
- ~(A∩B) = A∪B
- A−B = A∩~B
- ~~A = A, ~U = ∅, ~∅ = U
- A∪~A = U, A∩~A = ∅
Page 27 — 子集与运算的关系¶
- A ⊆ A∪B
- A∩B ⊆ A
- A−B ⊆ A
- (A⊆B) ≡ (A−B=∅) ≡ (A∪B=B) ≡ (A∩B=A)
- 若A⊆B，则B⊆A
Page 28 — 利用运算性质证明¶
例：若A∪B=U且A∩B=∅，则A=~B 证明：A = A∩U = A∩(B∪~B) = (A∩B)∪(A∩~B) = ∅∪(A∩~B) = A∩~B = (A∩B)∪(B∩B) —— 加上B∩~B=∅ = (A∪B)∩~B = U∩~B = ~B ✓
Page 29-31 — 幂集 ⭐考试重点¶
- 幂集ρ(A) = {x | x⊆A}（A的所有子集作为元素）
- 由于∅⊆A且A⊆A，必有∅∈ρ(A)且A∈ρ(A)
- 例：ρ({1,2}) = {∅, {1}, {2}, {1,2}}
- |ρ(A)| = 2ⁿ（n=|A|）
- ⭐ A⊆B ⟺ ρ(A)⊆ρ(B)
- 必要性：若A⊆B，对任意X∈ρ(A)有X⊆A⊆B → X∈ρ(B)
- 充分性：ρ(A)⊆ρ(B)，假设A⊈B则存在a∈A但a∉B → {a}∈ρ(A)但{a}∉ρ(B)，矛盾
💡 人话：幂集就是"所有子集的集合"。集合有n个元素，它的子集就有2ⁿ个（每个元素选或不选）。幂集保持子集关系——A是B的子集当且仅当A的幂集是B的幂集的子集。
Page 32-35 — 集合族¶
- 集合族：元素都是集合的集合
- 标志集：用下标标记集合族中的元素 C={Sd | d∈D}
- 广义并：∪C = {x | ∃S(S∈C ∧ x∈S)}（所有集合的元素的并）
- 广义交：∩C = {x | ∀S(S∈C → x∈S)}（所有集合的共同元素）
- 例：C={{0},{0,1},{0,1,2},...}
- ∪C = N（所有自然数）
- ∩C = {0}（都含有0）
Page 36-39 — 归纳定义 ⭐¶
三步走： 1. 基础条款：规定某些初始元素属于该集合 2. 归纳条款：如何从已有元素生成新元素 3. 终极条款：只有这样才能生成（排除其他）
例子1：偶数集E - 基础：0∈E - 归纳：若x∈E，则x+2∈E - 终极：略
例子2：命题公式 - 基础：命题变元是公式 - 归纳：若A,B是公式，则(¬A),(A∧B),...也是公式 - 终极：只有有限次使用上述两条才是公式
例子3：程序 - 基础：v:=e 是程序 - 归纳：p₁;p₂、if c then p₁ else p₂、while c do p 都是程序 - 终极：略