← 首页 / 集合论 · 从 ∈ 到映射与量词 待审核 11 页

集合论 · 从 ∈ 到映射与量词

集合(set)是「若干互不相同、无先后次序的对象」，几乎所有数学结构都建立在它之上。本系列不谈公理化细节，只把常用的那套符号与运算逐个呈现在可交互的 Venn 图与列表上：一个元素属于还是不属于一个集合、两个集合相等 / 包含 / 不相交、如何并 / 交 / 差 / 补出新集合、集合有多大、怎样用旧集合构造新集合，以及映射与逻辑量词如何把集合串成整张网。

每页都可直接输入集合、挑选运算或谓词，即时看到 Venn 分区着色、结果外延 {…} 与基数 |·| 随之变化。

关系与运算 · 元素、包含与四则

先分清两种「属于」——元素 ∈ 集合、集合 ⊆ 集合；再在同一张 Venn 图上做 ∪ ∩ − △ 与补集，看清每种运算对应哪一块分区。

成员关系 · ∈ ∉ ∅

属于与不属于：元素和集合的关系

集合最基本的问句：元素 x 在不在集合 A 里？在记 x ∈ A，不在记 x ∉ A。点元素把它加入 / 移出 A，看外延 {…} 与判定即时变化；顺带认识无元素的空集 ∅——对任何 x 都有 x ∉ ∅。

集合关系 · = ≠ ⊆ ⊂ ⊇ ⊃

相等、子集、真子集与不相交

两个集合之间的关系：元素完全一致即相等 =；A 的元素全在 B 里即子集 A ⊆ B，若还严格更小则是真子集 A ⊂ B；两者无公共元素即不相交 A ∩ B = ∅。拖动元素归属，所有判定一次点亮。

基础运算 · ∪ ∩ − △ ᶜ

并、交、差、对称差与补

从两个集合造第三个：并 A ∪ B、交 A ∩ B、差 A - B、对称差 A △ B，以及相对全集 U 的补 A^c。选一种运算，Venn 图上对应的分区着色，下方即时列出结果外延与基数。

规模与构造 · 有多大、怎样造新集合

用基数 |A| 度量集合大小（含可数 / 不可数无限），再用笛卡尔积、幂集、划分与商集从已有集合搭出新集合。

规模计算 · |A| · ℵ₀

基数：有限、可数无限与不可数

基数 |A| 是集合的「大小」。有限集就是数元素个数，并满足容斥 |A ∪ B| = |A| + |B| - |A ∩ B|；无限集则靠一一对应比较大小——自然数 ℕ 与偶数「一样多」（可数 ℵ₀），而实数 ℝ 严格更多（不可数）。

构造运算 · × P(A) 划分 A/R

造新集合：笛卡尔积、幂集、划分与商集

笛卡尔积 A×B 是所有有序对 (a, b)(|A×B| = |A|·|B|)；幂集 P(A) 是 A 的全部子集（2^|A| 个）；划分把集合切成互不相交、并起来是全集的若干块；商集 A/R 则按等价关系把元素归入等价类。

枚举子集 · 2ⁿ · 四种算法

枚举全部子集：四种算法

幂集给出全部子集的定义；这一页用四种算法不重不漏地逐一生成它们（共 2ⁿ 个）：二进制计数（整数的位当选 / 不选）、逐元素递归（每个元素入 / 不入）、迭代级联（从空集起逐元素翻倍）、Gray code（相邻子集只差一个元素），在同一块 board 上看它们以不同次序点亮同一批子集。

枚举划分 · Bell 数 Bₙ

枚举全部划分：三种算法

幂集列出全部子集；这一页列出把集合切成若干块的全部划分（共 Bell 数 Bₙ 个，增长比 2ⁿ 还猛）。用三种算法不重不漏地生成它们：逐元素递归（每个元素进老块或开新块）、restricted growth string（用合法编号串与划分一一对应）、含最小元素的块（每步为最小剩余元素挑同伴），在同一块 board 上看它们以不同次序点亮同一批划分；还可按块数等条件筛，看命中数落在 Stirling 第二类数 S(n,k) 上（Bₙ = Σₖ S(n,k)）。

映射与逻辑 · 集合之间、集合与命题

映射 f:A→B 把一个集合的元素送到另一个集合；集合推导 {x | P(x)} 与量词 ∀ / ∃ 则把集合与逻辑命题接通。

映射运算 · f：A→B · 像 / 原像 · 复合 / 逆

映射 f：A→B 与像、原像、复合、逆

映射（函数） f:A→ B 给定义域 A 的每个元素指定 B 中唯一的去处。子集的像 f(S) 与原像 f⁻¹(T)（原像完美保持并 / 交 / 补，像只保并不保交）；把两个映射接起来的复合 g∘f、反向的逆映射 f⁻¹（存在 ⟺ 双射），最后数一数 A→ B 一共有多少映射（n^m / 下降阶乘 / Stirling 数）。

逻辑运算 · {x | P(x)} · ∀ ∃

集合推导与量词 ∀ ∃

集合推导 {x ∈ U | P(x)} 用一个谓词 P 从全集里筛出满足条件的子集。量词则对整个集合下判断：∃ x P(x)（存在至少一个）与 ∀ x P(x)（所有都满足），分别给出见证或反例，并含全称 / 存在命题的否定。

命题 · 真假 · 且 ∧ 或 ∨ 非 ¬ · 四种命题

命题：真假、联结词与四种命题

命题是能判真假的陈述句。逻辑联结词 且 / 或 / 非（∧ / ∨ / ¬）拼出的复合命题，其真值集合正好是集合的交 / 并 / 补；四种命题（原 / 逆 / 否 / 逆否）里 原 ⟺ 逆否、逆 ⟺ 否，用真值集合的包含即可解释。

充分必要条件 · p ⇒ q ⟺ P ⊆ Q

充分必要条件：其实就是集合包含

常用逻辑用语里的充分 / 必要条件就是集合包含换了身衣服：把命题 p、q 的真值集合 P、Q 摆上 Venn 图，p ⇒ q ⟺ P ⊆ Q。充分对应子集、必要对应超集、充要对应相等 P = Q。

它对应到代码里的什么

Set 容器：∈ 是 has()，∪ / ∩ / − 是集合的并交差，|A| 是 size。 filter：集合推导 {x ∈ U | P(x)} 就是 U.filter(P)，谓词 P 决定去留。 map：映射 f:A→B 对应 A.map(f)，像 f(A) 是去重后的结果集（值域）。 some / every：量词 ∃ / ∀ 分别是 arr.some(P) / arr.every(P)。 GROUP BY / 等价类：数据库分组、并查集的连通分量，都是把集合按等价关系切成划分、取商集 A/R。