集合
Sets集合（set）就是一堆对象（元素）的聚会：写在大括号里，不管顺序、不看重复——{x, y} 与 {y, x} 是同一个集合，{x, x} 就是 {x}。常用符号：∅（空集）、ℕ、ℤ、ℚ、ℝ、ℂ，上标 + / − 表示正 / 负部分。
运算三件套（X ::= {1,2,3}，Y ::= {2,3,4}）：X ∪ Y 并（或）、X ∩ Y 交（且）、X − Y 差（在 X 不在 Y）。在论域 D 上还有补集 Ā ::= D − A。集合相等 = 互相包含，所以集合等式都能按"iff 链"证明——书里用这招证了分配律 A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)，每一步"iff"恰好对应一条命题逻辑定律（3.4 节的 De Morgan、分配律在这里全部 reincarnate）。
X AND Y 是类型错误（AND 只作用于真假值），正确写法是 X ∩ Y。你的编译器/阅读者会因此感谢你。4.1.3幂集：集合的发电站
幂集 pow(A) = A 的全部子集之集。n 个元素的集合恰有 2ⁿ 个子集——因为每个子集与一个 n 位 0/1 串一一对应（第 i 位 = 1 当且仅当第 i 个元素入选）。
序列与笛卡尔积
Sequences序列（sequence）是有序、可重复的列表 (a, b, c)，空序列记 λ。与集合的三条分界线：可重复（(a,b,a) 合法，{a,b,a} 是两个元素的集合）、讲顺序（(a,b,c) ≠ (a,c,b)，但对应集合相同）、记号（圆括号 vs 花括号）。
笛卡尔积 S₁ × S₂ × ⋯ × Sₙ 是"依次从每个集合取一个"的所有序列之集；两个集合的积叫配对（pair）。Sⁿ 表示 n 份 S 的积：{0,1}³ 恰是全部 3-bit 串的 8 个成员——又见 2ⁿ。
函数
Functions函数 f : A → B 给定义域 A 中每个元素指派陪域 B 中的一个值。关键冷知识：函数可以是部分的（partial）——不必对每个元素都有定义；处处有定义的才叫全函数（total）。书里的例子：f₅(y) = "从左到右搜索位串 y 直到遇到 1 的位置"，于是 f₅(0010) = 3、f₅(100) = 1，而 f₅(0000) = undefined。
f(S) ::= 把 f 逐点作用于集合 S 得到的像（image）；range(f) ::= f(定义域)。注意 range ≠ codomain——陪域是"允许的落点"，range 是"实际打中的落点"。
二元关系
Binary Relations二元关系 R : A → B 就是 A × B 的一个子集（它的 graph）——比函数更松：一个点可以连出任意多条箭头。用箭头图（左列定义域、右列陪域）看，五个标准性质全部是"数箭头"：
function：每点 ≤1 条箭头出；total：每点 ≥1 条箭头出；
surjective：右侧每点 ≥1 条箭头入；injective：右侧每点 ≤1 条箭头入；
bijective：恰好 =1 出 且 =1 入。
函数 = ≤1 出；全函数 = ≤1 出 且 ≥1 出。
别看定义干巴巴——亲手连几条箭头，五盏灯会替你记住它们：
有限基数
Finite Cardinality有限集合的大小 |A| 可以用箭头计数compare：函数每点至多一出 ⇒ 箭头数 ≤ |A|；满射要求右侧每点至少一入 ⇒ 箭头数 ≥ |B|。合起来就是映射规则（定理 4.5.4）：
它的首个战果：|pow(A)| = 2ⁿ（子集 ↔ n 位串的双射，互动 ②）。滑动两个集合的大小，看看哪种映射还可能存在：
基数实验室与技能核查
Set Cardinality, Playable基数 |A| = 集合元素的个数。核心规则（第 15 章计数规则的预告片）：不交并 |A∪B| = |A|+|B|；一般并要容斥 |A∪B| = |A|+|B|−|A∩B|；积规则 |A×B| = |A|·|B|；幂集 |pow(A)| = 2^|A|。
终局自测
Final Check六题，覆盖全章。
彩蛋与课后挑战
Easter Eggs & Problems幂集套娃：pow({∅, {∅}})（原书习题 4.1）
它的子集有几个？四个：∅、{∅}、{{∅}}、{∅, {∅}}。注意 ∅ 和 {∅} 是两个不同的东西——空集的幂集是 {{∅}}，恰好一个元素。这套套娃是集合论"万物皆集合"世界观的第一口深井（第一章提过的 ZFC 公理体系就在井底）。
类型错误博物馆（原书 4.1.5 节警告）
X、Y 是集合时写 "X AND Y" 会触发类型错误——AND 只吃真值，不吃集合，正确写法 X ∩ Y；同理命题 P、Q 写 "P ∪ Q" 也是类型错误，应为 P OR Q。第一章学过的每条命题逻辑定律，都在集合运算里有孪生兄弟（De Morgan：NOT(A ∩ B) ⟺ Ā ∪ B̄）——但孪生兄弟不能互相冒名顶替。
集合构造器记号一窥（原书 4.1.4 节）
{n ∈ ℕ | n 是素数且 n = 4k+1} 的前几个成员：5, 13, 17, 29, 37, 41, 53, …——列出前十个根本看不出规律，这就是"谓词定义"比"枚举"强大的原因。再如 C ::= {a+bi ∈ ℂ | a² + 2b² ≤ 1} 是复平面上围绕原点的一个椭圆区域——集合可以是一块"形状"。
课后挑战（均出自原书习题）
- 4.2 只用 ∈、⊆、=、∪、−、pow 把"x 是 y 的真子集"等关系写成集合论公式（自制一门"集合语言"）。
- 4.5 由命题逻辑 De Morgan 推导集合版 NOT(A ∩ B) = Ā ∪ B̄——把 3、4 两章的知识缝起来。
- 4.4 节概念题 用关系语言严格定义"函数 f 是全的"与"f 的像"（4.4.2 节的 R(Y)）。
- 鸽笼原理·前奏 映射规则版：|A| > |B| 时从 A 到 B 的全函数必有两人同席——原书 15.8 节将正式登场。