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

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

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

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

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

先分清两种「属于」——元素 $\in$ 集合、集合 $\subseteq$ 集合；再在同一张 Venn 图上做 $\cup \; \cap \; - \; \triangle$ 与补集，看清每种运算对应哪一块分区。

成员关系 ·

\in \; \notin \; \emptyset

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

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

集合关系 ·

= \; \ne \; \subseteq \; \subset \; \supseteq \; \supset

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

两个集合之间的关系：元素完全一致即相等 $=$ ； $A$ 的元素全在 $B$ 里即子集 $A \subseteq B$ ，若还严格更小则是真子集 $A \subset B$ ；两者无公共元素即不相交 $A \cap B = \emptyset$ 。输入两组成员，六条判定一次点亮。

基础运算 ·

\cup \; \cap \; - \; \triangle \; {}^{c}

并、交、差、对称差与补

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

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

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

规模计算 ·

|A|

\aleph_0

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

基数 $|A|$ 是集合的「大小」。有限集就是数元素个数，并满足容斥 $|A \cup B| = |A| + |B| - |A \cap B|$ ；无限集则靠一一对应比较大小——自然数 $\mathbb{N}$ 与偶数「一样多」（可数 $\aleph_0$ ），而实数 $\mathbb{R}$ 严格更多（不可数）。

构造运算 ·

\times

P(A)

划分

A/R

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

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

枚举子集 ·

{2^n}

· 四种算法

枚举全部子集：四种算法

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

枚举划分 · Bell 数

B_n

枚举全部划分：三种算法

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

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

映射 $f:A \to B$ 把一个集合的元素送到另一个集合；集合推导 $\{x \mid P(x)\}$ 与量词 $\forall / \exists$ 则把集合与逻辑命题接通。

映射运算 ·

f:A \to B

· 像 / 原像 · 复合 / 逆

映射 $f:A \to B$ 与像、原像、复合、逆

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

逻辑运算 ·

\{x \mid P(x)\}

\forall

\exists

集合推导与量词 ∀ ∃

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

命题 · 真假 · 且

\land

或

\lor

非

\neg

· 四种命题

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

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

充分必要条件 ·

p \Rightarrow q \iff P \subseteq Q

充分必要条件与集合包含

常用逻辑用语里的充分 / 必要条件即集合包含：把命题 $p$ 、 $q$ 的真值集合 $P$ 、 $Q$ 摆上 Venn 图， $p \Rightarrow q \iff P \subseteq Q$ 。充分对应子集、必要对应超集、充要对应相等 $P = Q$ 。

它对应到代码里的什么

Set 容器：

\in

是 has()，

\cup / \cap / -

是集合的并交差，

|A|

是 size。 filter：集合推导

\{x \in U \mid P(x)\}

就是 U.filter(P)，谓词 P 决定去留。 map：映射

f:A \to B

对应 A.map(f)，像

f(A)

是去重后的结果集（值域）。 some / every：量词

\exists

\forall

分别是 arr.some(P) / arr.every(P)。 GROUP BY / 等价类：数据库分组、并查集的连通分量，都是把集合按等价关系切成划分、取商集

A/R

。