Sets, Relations and Languages

Elements, Sets, and Subsets#

集合（Set） 是对象的无序汇集。元素的排列顺序与重复次数不影响集合：

集合也可以作为元素，例如：

除列举元素外，还可以用条件描述集合：

空集与“包含空集的集合”不同。 $\varnothing$ 没有元素，$\{\varnothing\}$ 有一个元素。

Set Operations and Identities#

设 $A=\{1,3,9\}$，$B=\{3,5,7\}$。

若 $A\cap B=\varnothing$，称两个集合不相交。例如 $\{1,3,9\}\cap\{a,b,c,d\}=\varnothing$。

Set Families and Power Sets#

集合族 $\mathcal S$ 的元素本身是集合。对集合族做并、交，可以写成：

这里的交集讨论非空集合族；未指定全集时，不直接套用空集合族的交集。

例如，$\mathcal S=\{\{a,b\},\{b,c\},\{c,d\}\}$，则 $\bigcup\mathcal S=\{a,b,c,d\}$，$\bigcap\mathcal S=\varnothing$。若 $\mathcal S=\{\{n\}:n\in\mathbb N\}$，则 $\bigcup\mathcal S=\mathbb N$。

幂集（Power Set） 是一个集合的所有子集组成的集合，记作 $2^A$：

例如：

若 $A$ 有 $n$ 个元素，则 $2^A$ 有 $2^n$ 个元素。

Partitions#

非空集合 $A$ 的一个划分（Partition），是满足下列条件的集合族 $\Pi\subseteq 2^A$：

每块非空，且 $A$ 中每个元素恰好属于一块。

例如，$\{\{a,b\},\{c\},\{d\}\}$ 是 $\{a,b,c,d\}$ 的划分；$\{\{b,c\},\{c,d\}\}$ 既重复包含 $c$，又遗漏 $a$，不满足要求。偶自然数集合与奇自然数集合组成 $\mathbb N$ 的一个划分。

Ordered Pairs, Cartesian Products, and Relations#

有序对（Ordered Pair） 保留位置：

当 $a\ne b$ 时，$(a,b)\ne(b,a)$；也允许 $(a,a)$。这与集合的无序性、去重性质不同。

笛卡尔积（Cartesian Product） 列出两个集合之间所有可能的有序配对：

Example:

$A$ 与 $B$ 上的二元关系（Binary Relation） 就是 $A\times B$ 的一个子集：

例如，$\{(1,b),(1,c),(3,d),(9,d)\}$ 是上述笛卡尔积中的一个关系。

“小于”也可以写成关系 $\{(i,j)\in\mathbb N^2:i<j\}$。

关系负责从全部可能的配对中，选出满足指定条件的配对。

TIP

有序 $n$ 元组为 $(a_1,\ldots,a_n)$，$n$ 元关系是 $A_1\times\cdots\times A_n$ 的子集。若各集合相同，乘积记作 $A^n$。元组的长度、位置和嵌套结构都需要保留，因此 $(4,4)$、$(4,4,4)$、$((4,4),4)$、$(4,(4,4))$ 彼此不同。

Functions#

函数（Function） $f:A\to B$ 是一个满足特殊条件的二元关系：

记 $(a,b)\in f$ 为 $f(a)=b$。

每个输入恰有一个输出；不同输入可以有相同输出。

若输入是元组，通常省去一层括号。例如 $f:\mathbb N^2\to\mathbb N$，$f(m,n)=m+n$。

Injections, Surjections, and Bijections#

证明单射时，也可以从 $f(a)=f(a')$ 推出 $a=a'$。

Inverse Relations and Functions#

对任意 $R\subseteq A\times B$，交换每个有序对的两个位置，得到逆关系：

逆关系始终可以定义，但 $f^{-1}$ 要成为从整个 $B$ 到 $A$ 的函数，需要 $f:A\to B$ 是双射：单射保证反向输出唯一，满射保证每个 $b\in B$ 都有反向输出。

此时：

$\{a\in A:f(a)=b\}$ 写成 $f^{-1}(b)$，此时返回的是一个集合，可能为空或包含多个元素。要区分“集合值的逆像”与“双射的逆函数”。

Composition#

若 $f:A\to B$、$g:B\to C$，先用 $f$，再用 $g$，得到 $h:A\to C$：

“狗 → 主人 → 主人的年龄”。

关系也可以这样复合：如果 $a$ 经第一个关系关联到某个 $b$，而 $b$ 经第二个关系关联到 $c$，就把 $(a,c)$ 放入复合关系。

复合记号 $Q\circ R=\{(a,c):\exists b,\ (a,b)\in Q\land(b,c)\in R\}$，即先 $Q$ 后 $R$；上述 $h$ 写作 $f\circ g$。

Graphs and Adjacency Matrices#

考虑 $R\subseteq A\times A$。用有向图（Directed Graph） 表示时，每个元素对应一个节点；$(a,b)\in R$ 对应一条从 $a$ 指向 $b$ 的边。$(a,a)$ 对应自环。这里不允许同一方向上的平行边。

邻接矩阵（Adjacency Matrix）。固定节点顺序 $a_1,\ldots,a_n$ 后，按关系定义写为：

行对应起点，列对应终点。 一个对称且不含自环的关系，可以用无向图表示，把相反方向的两条边合为一条无向边。

Basic Relation Properties#

反对称不等于“不是对称关系”。 等号关系既对称又反对称；也有关系既不对称，又不反对称。 “有相同父亲”具有自反性、对称性；“是父亲”具有反对称性；“是祖先”具有传递性。$\mathbb N$ 上的 $\le$ 同时自反、反对称、传递。

Equivalence Relations and Classes#

等价关系（Equivalence Relation） 同时满足自反、对称、传递。

元素 $a$ 所在的等价类（Equivalence Class） 为：

Theorem: Equivalence Classes Form a Partition#

非空集合 $A$ 上的等价关系 $R$，其所有不同等价类构成 $A$ 的划分。

展开证明

令 $\Pi=\{[a]:a\in A\}$。

非空：自反性给出 $aRa$，所以 $a\in[a]$。

不同等价类不相交：设 $c\in[a]\cap[b]$，则 $aRc$、$bRc$。由对称性和传递性得到 $aRb$、$bRa$。

对任意 $x\in[a]$，有 $aRx$；由 $bRa$ 与 $aRx$ 得 $bRx$，所以 $x\in[b]$，即 $[a]\subseteq[b]$。同理 $[b]\subseteq[a]$，故 $[a]=[b]$。

因此，两个等价类只要有一个公共元素，就完全相同。

覆盖：每个 $a\in A$ 都属于自己的等价类 $[a]$，所以 $\bigcup\Pi=A$。

反过来，给定划分 $\Pi$，定义“$a,b$ 在同一块中”即可得到等价关系。因此，等价关系与划分可以相互确定。

Orders and Extremal Elements#

偏序（Partial Order） 同时满足自反、反对称、传递。用 $a\preceq b$ 表示 $(a,b)\in R$。

偏序不要求任意两个元素都可比较；若进一步满足

就得到全序（Total Order）。

“祖先关系”在约定每个人也是自己的祖先后，成为偏序；不同支系的人未必可比较。自然数上的 $\le$ 是全序。

“极小”只排除更小者，不要求与所有其他元素可比较；“最小”提出了更强的要求。

NOTE

例如，将整除偏序限制在 $\{2,3,6\}$：令 $a\preceq b\iff a\mid b$。极小元素有 2、3 两个，最小元素不存在；6 同时是极大元素和最大元素。

非空有限偏序至少有一个极小元素；由对偶定义也至少有一个极大元素。 无限偏序没有这一保证，例如整数上的 $\le$ 没有极小元素。全序最多有一个极小元素；若存在，它也是最小元素。

Paths and Cycles#

满足 $(a_i,a_{i+1})\in R$ 的节点序列 $(a_1,\ldots,a_n)$ 称为从 $a_1$ 到 $a_n$ 的路径（Path），其中 $n\ge1$。

将路径长度定义为序列中的节点数 $n$。 这条路径经过 $n-1$ 条边；下文有关长度的定理沿用此约定。

单节点序列 $(a)$ 也是路径，从 $a$ 到自身且不经过边。若 $a_1,\ldots,a_n$ 两两不同，且还有 $(a_n,a_1)\in R$，则构成环（Cycle）。

Cardinality and Bijections#

集合 $A,B$ 等势（Equinumerous），表示存在双射 $f:A\to B$，记作 $|A|=|B|$。这里 $|A|$ 表示集合的基数（Cardinality）。

有限集的基数是元素个数；无限集也用双射比较大小。

Dovetailing#

交错枚举（Dovetailing） : 将多个可数集合的枚举过程交错进行，

若 $A=\{a_0,a_1,\ldots\}$、$B=\{b_0,b_1,\ldots\}$、$C=\{c_0,c_1,\ldots\}$ 两两不交，可枚举为：

这样不会因为一直枚举 $A$ 而永远轮不到 $B,C$。集合有交叠时，跳过已经列出的重复元素即可。

对于可数无限多个可数无限集，需要每轮只处理有限多个位置，并让各位置最终都被访问。由此得到：可数无限多个可数无限集的并仍然可数无限。

Example#

证明自然数对集合可数无限

证明 $\mathbb N\times\mathbb N$ 与 $\mathbb N$ 等势。

按两个坐标的和分组：

$$\begin{array}{c|l} i+j&\text{依次列出}\\\hline 0&(0,0)\\ 1&(0,1),(1,0)\\ 2&(0,2),(1,1),(2,0)\\ 3&(0,3),(1,2),(2,1),(3,0)\\ \vdots&\vdots \end{array}$$

每组有限，任意 $(i,j)$ 都会在和为 $i+j$ 的一组中出现。

展开双射公式与编号推导

令 $s=i+j$，编号从 0 开始。在和为 $s$ 的一组之前，已经有

$$1+2+\cdots+s=\frac{s(s+1)}2$$

个元素。本组从 $(0,s)$ 开始，$(i,j)$ 位于组内偏移 $i$ 的位置。因此：

$$f(i,j)=\frac{(i+j)(i+j+1)}2+i =\frac{(i+j)^2+3i+j}{2}.$$

不同组对应互不重叠的连续编号区间；同组中不同的 $i$ 对应不同编号，因此是单射。所有区间首尾相接，覆盖全部自然数，因此是满射。

Infinite Sets and Proper Subsets#

Continuum Hypothesis#

讨论自然数与实数之间是否存在中间大小的无限集合。记

连续统假设（Continuum Hypothesis） 断言不存在集合 $A$ 满足 $\aleph_0<|A|<\mathfrak c$。

$\mathfrak c=2^{\aleph_0}$，在连续统假设成立时有 $\mathfrak c=\aleph_1$。

Mathematical Induction#

数学归纳法（Mathematical Induction） 将无限多个命题的证明组织为“起点成立 + 从已有情形推出下一情形”。

形式为：若 $A\subseteq\mathbb N$ 满足

则 $A=\mathbb N$。用于命题 $P(n)$ 时，写成：

基础情形：证明 $P(0)$；归纳假设：假设某个任意 $n\ge0$ 下，$P(0),\ldots,P(n)$ 都成立；归纳步骤：利用假设证明 $P(n+1)$。

归纳假设不能包含尚待证明的 $P(n+1)$。题目从其他整数开始时，基础情形也相应调整。

Pigeonhole Principle#

鸽巢原理（Pigeonhole Principle）：若 $A,B$ 为有限集，且 $|A|>|B|$，则不存在从 $A$ 到 $B$ 的单射。

换句话说，只要函数 $f:A\to B$ 存在，就必有两个不同元素被映到同一个目标。

Diagonalization#

对角化（Diagonalization） 的核心构造是：针对第 $i$ 个候选对象，在第 $i$ 个位置故意与它不同。 这样得到的新对象不可能等于候选列表中的任何一个。

设 $R\subseteq A\times A$，定义各行对应的集合

以及对角集合

因为 $a\in D\iff a\notin R_a$，所以 $D\ne R_a$ 对每个 $a\in A$ 都成立。这一理由不依赖 $A$ 是否有限。

Example#

有限关系中的对角集合

行 $x$	对应集合 $R_x$	$x\in R_x$？	$x\in D$？
$a$	$\{b,d\}$	否	是
$b$	$\{b,c\}$	是	否
$c$	$\{c\}$	是	否
$d$	$\{b,c,e,f\}$	否	是
$e$	$\{e,f\}$	是	否
$f$	$\{a,c,d,e\}$	否	是

因此 $D=\{a,d,f\}$。它与第 $a$ 行在元素 $a$ 上不同，与第 $b$ 行在元素 $b$ 上不同，以此类推。

Closure Properties#

设 $D$ 是讨论对象的全集，$R\subseteq D^{n+1}$ 是一条具有 $n$ 个输入、一个输出位置的关系。若 $B\subseteq D$ 满足

就称 $B$ 对 $R$ 封闭（Closed under $R$）。对一组这样的关系封闭，称为一个闭包性质。

允许的规则以集合内元素为输入时，所有要求得到的结果也已经在集合内。

若给定初始集合 $A\subseteq D$，它在这些规则下的闭包（Closure） 是：包含 $A$、满足指定封闭性，并且没有多余元素的最小集合。

封闭性描述一个集合是否已经满足规则；闭包描述从指定初始集合出发需要补全成什么。

Existence and Uniqueness of Closures#

存在且唯一

对任意由上述关系定义的闭包性质 $P$，以及 $A\subseteq D$，存在唯一最小的 $B$，使得 $A\subseteq B$ 且 $B$ 满足 $P$。

Transitive and Reflexive Transitive Closures#

对 $R\subseteq A\times A$，令 $I_A=\{(a,a):a\in A\}$。

Closure Algorithms and Complexity#

三个求有限关系 $R^*$ 的算法。令 $n=|A|$，把检查、插入一个有序对视为基本操作。

1
C ← R ∪ I_A
2
只要存在 a_i, a_j, a_k，使
3
    (a_i,a_j) ∈ C 且 (a_j,a_k) ∈ C，但 (a_i,a_k) ∉ C：
4
    将 (a_i,a_k) 加入 C
5
    从头搜索下一处缺口
6
返回 C

1
C ← R ∪ I_A
2
for j = 1, ..., n:
3
    for i = 1, ..., n:
4
        for k = 1, ..., n:
5
            if (a_i,a_j) ∈ C and (a_j,a_k) ∈ C:
6
                将 (a_i,a_k) 加入 C
7
返回 C