# Set Theory Cheatsheet

集合论 (set theory) 的 cheatsheet.

## 1. 集合代数

### 定义 1.1

设 $A, B$ 为集合, 如果 $B$ 中的每个元素都是 $A$ 中的元素, 则称 $B$ 是 $A$ 的
*子集合*, 简称 *子集*.  这时也称 *B 被 A 包含*, 或 *A 包含 B*, 记作
$B \subseteq A$.

如果 $B$ 不被 $A$ 包含, 则记作 $B \nsubseteq A$.

包含的符号化表示为
$$B \subseteq A \Leftrightarrow \forall x(x \in B \rightarrow x \in A)$$

### 定义 1.2

设 $A, B$ 为集合, 如果 $A \subseteq B$ 且 $B \subseteq A$, 则称 $A$ 与 $B$
*相等, 记作 $A = B$, 如果不相等, 则记作 $A \ne B$.

相等的符号化表示为
$$A = B \Leftrightarrow A \subseteq B \land B \subseteq A$$

### 定义 1.3

设 $A, B$ 为集合, 如果 $B \subseteq A$ 且 $B \ne A$, 则称 $B$ 是 $A$ 的
*真子集*, 记作 $B \subset A$, 如果 $B$ 不是 $A$ 的真子集, 则记作
$A \not\subset B$.

真子集的符号化表示为
$$B \subset A \Leftrightarrow B \subseteq A \land B \ne A$$

### 定义 1.4

不含任何元素的集合叫做 *空集*, 记作 $\emptyset$.

空集可以符号化表示为 $$\emptyset = \{ x | x \ne x \}$$

### 定理 1.1

空集是一切集合的子集.

**推论:** 空集是唯一的.

### 定义 1.5

设 $A$ 为集合, 把 $A$ 的全体子集构成的集合叫做 $A$ 的 *幂集*, 记作 $P(A)$ (或
$\mathscr{P} A, 2^A$).

幂集的符号化表示为 $$P(A) = \{ x | x \subseteq A \}$$

**推论:** 若 $A$ 是 n 元集, 则 $P(A)$ 有 $2^n$ 个元素.

### 定义 1.6

在一个具体问题中, 如果所涉及的集合都是某个集合的子集, 则称这个集合为 *全集*, 记作
$E$.

### 定义 1.7

设 $A, B$ 为集合, $A$ 与 $B$ 的 *并集* $A \cup B$, *交集* $A \cap B$, $B$
对 $A$ 的 *相对补集* $A - B$ 分别定义如下:
$$A \cup B = \{ x | x \in A \lor x \in B \}$$
$$A \cap B = \{ x | x \in A \land x \in B \}$$
$$A - B = \{ x | x \in A \land x \notin B \}$$

### 定义 1.8

设 $A, B$ 为集合, $A$ 与 $B$ 的 *对称差集* $A \oplus B$ 定义为
$$A \oplus B = (A - B) \cup (B - A)$$

### 定义 1.9

$$\sim A = E - A = \{ x | x \in E \land x \notin A \}$$

### 定义 1.10

设 $A$ 为集合, $A$ 的元素的元素构成的集合称为 $A$ 的 *广义并*, 记为 $\cup A$,
符号化表示为 $$\cup A = \{ x | \exists z(z \in A \land x \in z) \}$$

空集的广义并是空集.

### 定义 1.11

设 $A$ 为非空集合, $A$ 的所有元素的公共元素构成的集合称为 $A$ *广义交*, 记为
$\cap A$.  符号化表示为
$$\cap A = \{ x | \forall z(z \in A \rightarrow x \in z) \}$$

### 定理 1.2 包含排斥原理

设 $S$ 为有穷集, $P_1, P_2, \dots, P_n$ 是 $n$ 个性质.  $S$ 中的任何元素
$x$ 或者具有性质 $P_i$, 或者不具有性质 $P_i$, 两种情况必居其一.  令 $A_i$ 表示
$S$ 中具有性质 $P_i$ 的元素构成的子集, 则 $S$ 中不具有性质
$P_1, P_2, \dots, P_n$ 的元素数为
$$|\overline{A_1} \cap \overline{A_2} \cap \dots \cap \overline{A_n}|$$
$$= |S| - \sum_{i = 1}^n |A_i| + \sum_{1 \le i \lt j \le n} |A_i \cap A_j|$$
$$- \sum_{1 \le i \lt j \lt k \le n} |A_i \cap A_j \cap A_k| + \dots + (-1)^n |A_1 \cap A_2 \cap \dots \cap A_n|$$

**推论:** $S$ 中至少具有一条性质的元素数为
$$|A_1 \cup A_2 \cup \dots \cup A_n|$$
$$= \sum_{i = 1}^n |A_i| - \sum_{1 \le i \lt j \le n} |A_i \cap A_j|$$
$$+ \sum_{1 \le i \lt j \lt k \le n} | A_i \cap A_j \cap A_k| - \dots + (-1)^n|A_1 \cap A_2 \cap \dots \cap A_n|$$

### 集合恒等式

1. 幂等律
$$A \cup A = A$$
$$A \cap A = A$$
2. 结合律
$$(A \cup B) \cup C = A \cup (B \cup C)$$
$$(A \cap B) \cap C = A \cap (B \cap C)$$
3. 交换律
$$A \cup B = B \cup A$$
$$A \cap B = B \cap A$$
4. 分配律
$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$
$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$
5. 同一律
$$A \cup \emptyset = A$$
$$A \cap E = A$$
6. 零律
$$A \cup E = E$$
$$A \cap \emptyset = \emptyset$$
7. 排中律
$$A \cup \sim A = E$$
8. 矛盾律
$$A \cap \sim A = \emptyset$$
9. 吸收律
$$A \cup (A \cap B) = A$$
$$A \cap (A \cup B) = A$$
10. 德摩根律
$$A - (B \cup C) = (A - B) \cap (A - C)$$
$$A - (B \cap C) = (A - B) \cup (A - C)$$
$$\sim (B \cup C) = \sim B \cap \sim C$$
$$\sim (B \cap C) = \sim B \cup \sim C$$
$$\sim \emptyset = E$$
$$\sim E = \emptyset$$
11. 双重否定律
$$\sim \sim A = A$$

### 其它运算性质的重要结果

$$A \cap B \subseteq A, A \cap B \subseteq B$$
$$A \subseteq A \cup B, B \subseteq A \cup B$$
$$A - B \subseteq A$$
$$A - B = A \cap \sim B$$
$$A \cup B = B \Leftrightarrow A \subseteq B \Leftrightarrow A \cap B = A \Leftrightarrow A - B = \emptyset$$
$$A \oplus B = B \oplus A$$
$$(A \oplus B) \oplus C = A \oplus (B \oplus C)$$
$$A \oplus \emptyset = A$$
$$A \oplus A = \emptyset$$
$$A \oplus B = A \oplus C \Rightarrow B = C$$

## 2. 二元关系

### 定义 2.1

由两个元素 $x$ 和 $y$ (允许 $x = y$) 按一定顺序排列成的二元组叫做一个 *有序对* 或
*序偶*, 记作 $<x, y>$, 其中 $x$ 是它的第一元素, $y$ 是它的第二元素.

### 定义 2.2

设 $A, B$ 为集合, 用 $A$ 中元素为第一元素, $B$ 中元素为第二元素构成有序对.
所有这样的有序对组成的集合叫做 $A$ 和 $B$ 的 *笛卡尔积*, 记作 $A \times B$.

笛卡尔积的符号化表示为 $$A \times B = \{ <x, y> | x \in A \land y \in B \}$$

### 定义 2.3

如果一个集合满足一下条件之一:

1. 集合非空, 且它的元素都是有序对.
2. 集合是空集.

则称该集合为一个 *二元关系*, 记作 $R$.  二元关系也可简称为 *关系*. 对于二元关系 $R$,
如果 $<x, y> \in R$, 可记作 $x\mathrel{R}y$, 如果 $<x, y> \notin R$, 则记作
$x\not\mathrel{R}y$.

### 定义 2.4

设 $A, B$ 为集合, $A \times B$ 的任何子集所定义的二元关系叫做 *从 A 到 B 的二元关系*,
特别当 $A = B$ 时叫做 $A$ 上的 *二元关系*.

### 定义 2.5

对任何集合 $A$, 定义
$$E_A = \{ <x, y> | x \in A \land y \in A \} = A \times A$$
$$I_A = \{ <x, x> | x \in A \}$$

### 定义 2.6

设 $R$ 是二元关系.

1. $R$ 中所有有序对的第一元素构成的集合称为 $R$ 的 *定义域*, 记作 $dom R$,
形式化表示为 $$dom R = \{ x | \exists y(<x, y> \in R) \}$$
2. $R$ 中所有有序对的第二元素构成的集合称为 $R$ 的 *值域*, 记作 $ran R$.
形式化表示为 $$ran R = \{ y | \exists x(<x, y> \in R) \}$$
3. $R$ 的定义域和值域的并集称为 $R$ 的 *域*, 记作 $fld R$.  形式化表示为
$$fld R = dom R \cup ran R$$

### 定义 2.7

设 $R$ 为二元关系, $R$ 的 *逆关系*, 简称 $R$ 的 *逆*, 记作 $R^-1$, 其中
$$R^-1 = \{ <x, y> | <y, x> \in R \}$$

### 定义 2.8

设 $F, G$ 为二元关系, $G$ 对 $F$ 的 *右复合* 记作 $F \circ G$, 其中
$$F \circ G = \{ <x, y> | \exists t(<x, t> \in F \land <t, y> \in G) \}$$
*左复合* $F \circ G$ 即
$$F \circ G = \{ <x, y> | \exists t(<x, t> \in G \land <t, y> \in F) \}$$

### 定义 2.9

设 $R$ 为二元关系, $A$ 是集合.

1. $R$ 在 $A$ 上的 *限制* 记作 $R \upharpoonright A$, 其中
$$R \upharpoonright A = \{ <x, y> | x\mathrel{R}y \land x \in A \}$$
2. $A$ 在 $R$ 下的 *像* 记作 $R[A]$, 其中
$$R[A] = ran(R \upharpoonright A)$$

**推论:** $R$ 在 $A$ 上的限制 $R \upharpoonright A$ 是 $R$ 的子关系.  $A$
在 $R$ 下的像 $R[A]$ 是 $ran R$ 的子集.

### 定理 2.1

设 $F$ 是任意的关系, 则:

1. $(F^{-1})^{-1} = F$.
2. $dom F^{-1} = ran F, ran F^{-1} = dom F$.

### 定理 2.2

设 $F, G, H$ 是任意的关系, 则:

1. $(F \circ G) \circ H = F \circ (G \circ H)$.
2. $(F \circ G)^{-1} = G^{-1} \circ F^{-1}$.

### 定理 2.3

设 $R$ 为 $A$ 上的关系, 则 $$R \circ I_A = I_A \circ R = R$$

### 定理 2.4

设 $F, G, H$ 为任意关系, 则:

1. $F \circ (G \cup H) = F \circ G \cup F \circ H$.
2. $(G \cup H) \circ F = G \circ F \cup H \circ F$.

### 定理 2.5

设 $F$ 为关系, $A, B$ 为集合, 则:

1. $F \upharpoonright (A \cup B) = F \upharpoonright A \cup F \upharpoonright B$.
2. $R[A \cup B] = F[A] \cup F[B]$.
3. $F \upharpoonright (A \cap B) = F \upharpoonright A \cap F \upharpoonright B$.
4. $F[A \cap B] \subseteq F[A] \cap F[B]$.

### 定义 2.10

设 $R$ 为 $A$ 上的关系, $n$ 为自然数, 则 $R$ 的 *n 次幂 $R^n$* 定义为:

1. $R^0 = \{ <x, x> | x \in A \} = I_A$.
2. $R^{n + 1} = R^n \circ R$.

### 定理 2.6

设 $A$ 为 n 元集, $R$ 是 $A$ 上的关系, 则存在自然数 $s$ 和 $t$, 使得 $R^s = R^t$.

### 定理 2.7

设 $R$ 为 $A$ 上的关系, $m, n \in \mathbb{N}$, 则:

1. $R^m \circ R^n = R^{m + n}$.
2. $(R^n)^n = R^{mn}$.

### 定理 2.8

设 $R$ 为 $A$ 上的关系, 若存在自然数 $s, t (s \lt t)$ 使得 $R^s = R^t$, 则:

1. 对任何 $k \in \mathbb{N}$ 有 $R^{s + k} = R^{t + k}$.
2. 对任何 $k, i \in \mathbb{N}$ 有 $R^{s + kp + i} = R^{s + i}$, 其中 $p = t - s$.
3. 令 $S = \{ R^0, R^1, \dots, R^{t - 1} \}$, 则对于任意的 $q \in \mathbb{N}$ 有
$R^q \in S$.

### 定义 2.11

设 $R$ 为 $A$ 上的关系.

1. 若 $\forall x(x \in A \rightarrow <x, x> \in R)$, 则称 $R$ 在 $A$ 上是 *自反* 的.
1. 若 $\forall x(x \in A \rightarrow <x, x> \notin R)$, 则称 $R$ 在 $A$ 上是
*反自反* 的.

### 定义 2.12

设 $R$ 为 $A$ 上的关系.

1. 若 $\forall x \forall y(x, y \in A \land <x, y> \in R \rightarrow <y, x> \in R)$,
则称 $R$ 为 $A$ 上 *对称* 的关系.
2. 若 $\forall x \forall y(x, y \in A \land <x, y> \in R \land <y, x> \in R \rightarrow x = y)$,
则称 $R$ 为 $A$ 上 *反对称* 的关系.

### 定义 2.13

设 $R$ 为 $A$ 上的关系, 若
$$\forall x \forall y \forall z(x, y, z \in A \land <x, y> \in R \land <y, z> \in R \rightarrow <x, z> \in R)$$
则称 $R$ 为 $A$ 上 *传递* 的关系.

### 定理 2.9

设 $R$ 为 $A$ 上的关系, 则:

1. $R$ 在 $A$ 上自反当且仅当 $I_A \subseteq R$.
2. $R$ 在 $A$ 上反自反当且仅当 $R \cap I_A = \emptyset$.
3. $R$ 在 $A$ 上对称当且仅当 $R = R^{-1}$.
4. $R$ 在 $A$ 上反对称当且仅当 $R \cap R^{-1} \subseteq I_A$.
5. $R$ 在 $A$ 上传递当且仅当 $R \circ R \subseteq R$.

### 五种性质的特点

||自反性|反自反性|对称性|反对称性|传递性|
|:-:|:-:|:-:|:-:|:-:|:-:|
|集合表达式|$I_A \in R$|$R \cap I_A = \emptyset$|$R = R^{-1}$|$R \cap R^{-1} \subseteq I_A$|$R \circ R \subseteq R$|
|关系矩阵|主对角线元素全是 1|主对角线元素全是 0|矩阵是对称矩阵|若 $r_{ij} = 1$ 且 $i \ne j$, 则 $r_{ji} = 0$|对 $M^2$ 中 1 所在的位置, $M$ 中相应的位置都是 1|
|关系图|每个顶点都有环|每个顶点都没有环|如果两个顶点之间有边, 一定是一对方向相反的边 (无单边)|如果两个顶点之间有边, 一定是一条有向边 (无双向边)|如果顶点 $x_i$ 到 $x_j$ 有边, $x_j$ 到 $x_k$ 有边, 则从 $x_i$ 到 $x_k$ 也有边|

### 原有性质与运算的关系

||自反性|反自反性|对称性|反对称性|传递性|
|:-:|:-:|:-:|:-:|:-:|:-:|
|$R_1^{-1}$|能保持|能保持|能保持|能保持|能保持|
|$R_1 \cap R_2$|能保持|能保持|能保持|能保持|能保持|
|$R_1 \cup R_2$|能保持|能保持|能保持|不一定能保持|不一定能保持|
|$R_1 - R_2$|不一定能保持|能保持|能保持|能保持|不一定能保持|
|$R_1 \circ R_2$|能保持|不一定能保持|不一定能保持|不一定能保持|不一定能保持|

### 定义 2.14

设 $R$ 是非空集合 $A$ 上的关系, $R$ 的自反 (对称或传递) 闭包是 $A$ 上的关系 $R\prime$,
使得 $R\prime$ 满足以下条件:

1. $R\prime$ 是自反的 (对称或传递的).
2. $R \subseteq R\prime$.
3. 对 $A$ 上任何包含 $R$ 的自反 (对称或传递) 关系 $R\prime\prime$ 有
$R\prime \subseteq R\prime\prime$.

一般将 $R$ 的自反闭包记作 $r(R)$, 对称闭包记作 $s(R)$, 传递闭包记作 $t(R)$.

### 定理 2.10

设 $R$ 为 $A$ 上的关系, 则有:

1. $r(R) = R \cup R^0$.
2. $s(R) = R \cup R^{-1}$.
3. $t(R) = R \cup R^2 \cup R^3 \cup \dots$.

**推论:** 设 $R$ 为有穷集 $A$ 上的关系, 则存在正整数 $r$ 使得
$$t(R) = R \cup R^2 \cup R^3 \cup \dots \cup R^r$$

### 定理 2.11

设 $R$ 是非空集合 $A$ 上的关系, 则:

1. $R$ 是自反的当且仅当 $r(R) = R$.
2. $R$ 是对称的当且仅当 $s(R) = R$.
3. $R$ 是传递的当且仅当 $t(R) = R$.

### 定理 2.12

设 $R_1$ 和 $R_2$ 是非空集合 $A$ 上的关系, 且 $R_1 \subseteq R_2$, 则:

1. $r(R_1) \subseteq r(R_2)$.
2. $s(R_1) \subseteq s(R_2)$.
3. $t(R_1) \subseteq t(R_2)$.

### 定理 2.13

设 $R$ 是非空集合 $A$ 上的关系, 则:

1. 若 $R$ 是自反的, 则 $s(R)$ 与 $t(R)$ 也是自反的.
2. 若 $R$ 是对称的, 则 $r(R)$ 与 $t(R)$ 也是对称的.
3. 若 $R$ 是传递的, 则 $r(R)$ 是传递的.

### 定义 2.15

设 $R$ 为非空集合 $A$ 上的关系, 如果 $R$ 是自反的, 对称的和传递的, 则称 $R$
为 $A$ 上的 *等价关系*.  设 $R$ 是一个等价关系, 若 $<x, y> \in R$, 则称
*x 等价于 y*, 记作 $x \sim y$.

### 定义 2.16

设 $R$ 为非空集合 $A$ 上的等价关系, $\forall x \in A$, 令
$$[x]_R = \{ y | y \in A \land x \mathrel{R} y \}$$
称 $[x]_R$ 为 *x 关于 R 的等价类*, 简称为 $x$ 的 *等价类*, 简记为 $[x]$ 或
$\overline{x}$.

### 定理 2.14

设 $R$ 为非空集合 $A$ 上的等价关系, 则:

1. $\forall x \in A$, $[x]$ 是 $A$ 的非空子集.
2. $\forall x, y \in A$, 如果 $x \mathrel{R} y$, 则 $[x] = [y]$.
3. $\forall x, y \in A$, 如果 $x \not\mathrel{R} y$, 则 $[x]$ 与 $[y]$
不交.
4. $\cup \{ [x] | x \in A \} = A$.

### 定义 2.17

设 $R$ 为非空集合 $A$ 上的等价关系, 以 $R$ 的所有等价类作为元素的集合称为 $A$
关系于 $R$ 的 *商集*, 记作 $A / R$, 即 $$A / R = \{ [x]_R | x \in A \}$$

### 定义 2.18

设 $A$ 为非空集合, 若 $A$ 的子集族 $\pi$ ($\pi \subseteq P(A)$, 是 $A$
的子集构成的集合) 满足下面的条件:

1. $\emptyset \notin \pi$.
2. $\forall x \forall y(x, y \in \pi \land x \ne y \rightarrow x \cap y = \emptyset)$.
3. $\cup \pi = A$.

则称 $\pi$ 是 $A$ 的一个 *划分*, 称 $\pi$ 中的元素为 $A$ 的 *划分块*.

### 定义 2.19

设 $R$ 为非空集合 $A$ 上的关系.  如果 $R$ 是自反的, 反对称的和传递的, 则称 $R$ 为
$A$ 上的 *偏序关系*, 记作 $\preccurlyeq$.  设 $\preccurlyeq$ 为偏序关系, 如果
$<x, y> \in \preccurlyeq$, 则记作 $x \preccurlyeq y$, 读作 x "小于或等于" y.

### 定义 2.20

设 $preccurlyeq$ 为非空集合 $A$ 上的偏序关系, 定义:

1. $\forall x, y \in A, x \prec y \Leftrightarrow x \preccurlyeq y \land x \ne y$.
2. $\forall x, y \in A, x 与 y 可比 \Leftrightarrow x \preccurlyeq y \lor y \preccurlyeq x$.

### 定义 2.21

设 $R$ 为非空集合 $A$ 上的偏序关系, 如果 $\forall x, y \in A$, $x$ 与 $y$
都是可比的, 则称 $R$ 为 $A$ 上的 *全序关系* (或 *线序关系*).

### 定义 2.22

集合 $A$ 和 $A$ 上的偏序关系 $\preccurlyeq$ 一起叫做 *偏序集*,
记作 $<A, \preccurlyeq>$.

### 定义 2.23

设 $<A, \preccurlyeq>$ 为偏序集, $\forall x, y \in A$, 如果 $x \prec y$
且不存在 $z \in A$ 使得 $x \prec z \prec y$, 则称 *y 覆盖 x*.

### 定义 2.24

设 $<A, \preccurlyeq>$ 为偏序集, $B \subseteq A, y \in B$.

1. 若 $\forall x(x \in B \rightarrow y \preccurlyeq x)$ 成立, 则称 $y$ 为
$B$ 的 *最小元*.
2. 若 $\forall x(x \in B \rightarrow x \preccurlyeq y)$ 成立, 则称 $y$ 为
$B$ 的 *最大元*.
3. 若 $\forall x(x \in B \land x \preccurlyeq y \rightarrow x = y)$ 成立,
则称 $y$ 为 $B$ 的 *极小元*.
4. 若 $\forall x(x \in B \land y \preccurlyeq x \rightarrow x = y)$ 成立,
则称 $y$ 为 $B$ 的 *极大元*.

### 定义 2.25

设 $<A, \preccurlyeq>$ 为偏序集, $B \subseteq A, y \in A$.

1. 若 $\forall x(x \in B \rightarrow x \preccurlyeq y)$ 成立, 则称 $y$ 为
$B$ 的 *上界*.
2. 若 $\forall x(x \in B \rightarrow y \preccurlyeq x)$ 成立, 则称 $y$ 为
$B$ 的 *下界*.
3. 令 $C = \{ y | y 为 B 的上界 \}$, 则称 $C$ 的最小元为 $B$ 的 *最小上界* 或
*上确界*.
4. 令 $D = \{ y | y 为 B 的下界 \}$, 则称 $D$ 的最大元为 $B$ 的 *最大下界* 或
*下确界*.

## 3. 函数

### 定义 3.1

设 $F$ 为二元关系, 若 $\forall x \in dom F$ 都存在唯一的 $y \in ran F$
使 $x \mathrel{F} y$ 成立, 则称 $F$ 为 *函数* (也可称作 *映射*).  对于函数 $F$,
如果有 $x \mathrel{F} y$, 则记作 $y = F(x)$, 并称 $y$ 为 $F$ 在 $x$ 的值.

### 定义 3.2

设 $F, G$ 为函数, 则
$$F = G \Leftrightarrow F \subseteq G \land G \subseteq F$$

### 定义 3.3

设 $A, B$ 为集合, 如果 $f$ 为函数, 且 $dom f = A, ran f \subseteq B$, 则 $f$
称为 *从 A 到 B 的函数*, 记作 $f: A \rightarrow B$.

### 定义 3.4

所有从 $A$ 到 $B$ 的函数的集合记作 $B^A$, 读作 "B 上 A", 符号化表示为
$$B^A = \{ f | f: A \rightarrow B \}$$

### 定义 3.5

设函数 $f: A \rightarrow B, A_1 \subseteq A, B_1 \subseteq B$.

1. 令 $f(A_1) = \{ f(x) | x \in A_1 \}$, 称 $f(A_1)$ 为 $A_1$ 在 $f$ 下的
*像*.  特别地, 当 $A_1 = A$ 时称 $f(A)$ 为 *函数的像*.
2. 令 $f^{-1}(B_1) = \{ x | x \in A \land f(x) \in B_1 \}$, 称 $f^{-1}(B_1)$
为 $B_1$ 在 $f$ 下的 *完全原像*.

### 定义 3.6

设 $f: A \rightarrow B$.

1. 若 $ran f = B$, 则称 $f: A \rightarrow B$ 是 *满射* 的.
2. 若 $\forall y \in ran f$ 都存在唯一的 $x \in A$ 使得 $f(x) = y$, 则称
$f: A \rightarrow B$ 是 *单射* 的.
3. 若 $f: A \rightarrow B$ 既是满射又是单射的, 则称 $f: A \rightarrow B$ 是
*双射* 的 (或一一映像).

### 定义 3.7

1. 设 $f: A \rightarrow B$, 如果存在 $c \in B$ 使得对所有的 $x \in A$ 都有
$f(x) = c$, 则称 $f: A \rightarrow B$ 是 *常函数*.
2. 称 $A$ 上的恒等关系 $I_A$ 为 $A$ 上的 *恒等函数*.  对所有的 $x \in A$ 都有
$I_A(x) = x$.
3. 设 $<A, \preccurlyeq>$, $<B, \preccurlyeq>$ 为偏序集,
$f: A \rightarrow B$, 如果对任意的 $x_1, x_2 \in A, x_1 \prec x_2$, 就有
$f(x_1) \preccurlyeq f(x_2)$, 则称 $f$ 为 *单调递增* 的, 如果对任意的
$x_1, x_2 \in A, x_1 \prec x_2$, 就有 $f(x_1) \prec f(x_2)$, 则称 $f$ 为
*严格单调递增* 的.  类似地也可以定义 *单调递减* 的和 *严格单调递减* 的函数.
4. 设 $A$ 为集合, 对于任意的 $A\prime \subseteq A$, $A\prime$ 的 *特征函数*
$\chi_{A\prime}: A \rightarrow \{0, 1\}$ 定义为:
\begin{equation}
    \chi_{A\prime}(a) = \begin{cases}
        1, a \in A\prime \\
        0, a \in A - A\prime
    \end{cases}
\end{equation}
5. 设 $R$ 是 $A$ 上的等价关系, 令
$$g: A \rightarrow A / R$$
$$g(a) = [a], \forall a \in A$$
称 $g$ 是从 $A$ 到商集 $A / R$ 的 *自然映射*.

### 定理 3.1

设 $F, G$ 是函数, 则 $F \circ G$ 也是函数, 且满足:

1. $dom (F \circ G) = \{ x | x \in dom F \land F(x) \in dom G \}$.
2. $\forall x \in dom (F \circ G)$ 有 $F \circ G(x) = G(F(x))$.

**推论1:** 设 $F, G, H$ 为函数, 则 $(F \circ G) \circ H$ 和
$F \circ (G \circ H)$ 都是函数, 且
$$(F \circ G) \circ H = F \circ (G \circ H)$$

**推论2:** 设 $f: A \rightarrow B, g: B \rightarrow C$, 则
$f \circ g: A \rightarrow C$, 且 $\forall x \in A$ 都有
$f \circ g(x) = g(f(x))$.

### 定理 3.2

设 $f: A \rightarrow B, g: B \rightarrow C$.

1. 如果 $f: A \rightarrow B, g: B \rightarrow C$ 都是满射的, 则
$f \circ g: A \rightarrow C$ 也是满射的.
2. 如果 $f: A \rightarrow B, g: B \rightarrow C$ 都是单射的, 则
$f \circ g: A \rightarrow C$ 也是单射的.
3. 如果 $f: A \rightarrow B, g: B \rightarrow C$ 都是双射的, 则
$f \circ g: A \rightarrow C$ 也是双射的.

### 定理 3.3

设 $f: A \rightarrow B$, 则有 $$f = f \circ I_B = I_A \circ f$$

### 定理 3.4

设 $f: A \rightarrow B$ 是双射的, 则 $f^{-1}: B \rightarrow A$
也是双射的.

### 定理 3.5

设 $f: A \rightarrow B$ 是双射的, 则
$$f^{-1} \circ f = I_B, f \circ f^{-1} = I_A$$

### 定义 3.8

设 $A, B$ 是集合, 如果存在着从 $A$ 到 $B$ 的双射函数, 就称 $A$ 和 $B$
是 *等势* 的, 记作 $A \approx B$, 如果 $A$ 不与 $B$ 等势, 则记作
$A \not\approx B$.

### 定理 3.6

设 $A, B, C$ 是任意集合.

1. $A \approx A$.
2. 若 $A \approx B$, 则 $B \approx A$.
3. 若 $A \approx B, B \approx C$, 则 $A \approx C$.

### 定理 3.7 康托定理

1. $\mathbb{N} \not\approx \mathbb{R}$.
2. 对任意集合 $A$ 都有 $A \not\approx P(A)$.

### 定义 3.9

1. 设 $A, B$ 是集合, 如果存在从 $A$ 到 $B$ 的单射函数, 就称 $B$ *优势于*
$A$, 记作 $A \preccurlyeq\bullet B$.  如果 $B$ 不是优势于 $A$, 则记作
$A \not\preccurlyeq\bullet B$.
2. 设 $A, B$ 是集合, 若 $A \preccurlyeq\bullet B$ 且 $A \not\approx B$,
则称 *B 真优势于 A*, 记作 $A \prec\bullet B$.  如果 $B$ 不是真优势于 $A$,
则记作 $A \nprec\bullet B$.

### 定理 3.8

设 $A, B, C$ 是任意的集合, 则:

1. $A \preccurlyeq\bullet A$.
2. 若 $A \preccurlyeq\bullet B$ 且 $B \preccurlyeq\bullet A$, 则
$A \approx B$.
3. 若 $A \preccurlyeq\bullet B$ 且 $B \preccurlyeq\bullet C$, 则
$A \preccurlyeq\bullet C$.

### 定义 3.10

用空集和 *后继* $n^+$ (紧跟在 $n$ 后面的自然数) 可以把所有的自然数定义为集合, 即
$$0 = \emptyset$$
$$n^+ = n \cup \{ n \}, \forall n \in \mathbb{N}$$

**推论 (自然数的 *三歧性*):** 对任何自然数 $n$ 和 $m$, 以下三个式子:
$$m \in n, m \approx n, n \in m$$
必成立其一且仅成立其一.

### 定义 3.11

一个集合是 *有穷* 的当且仅当它与某个自然数等势.  如果一个集合不是有穷的, 就称作
*无穷集*.

### 定义 3.12

1. 对于有穷集合 $A$, 称与 $A$ 等势的那个唯一的自然数为 $A$ 的 *基数*, 记作 $card A$
(或 $|A|$), 即 $$card A = n \Leftrightarrow A \approx n$$
2. 自然数集合 $\mathbb{N}$ 的基数记作 $\aleph_0$, 即 $$card \mathbb{N} = \aleph_0$$
3. 实数集 $\mathbb{R}$ 的基数记作 $\aleph$, 即 $$card \mathbb{R} = \aleph$$

### 定义 3.13

设 $A, B$ 为集合, 则:

1. $card A = card B \Leftrightarrow A \approx B$.
2. $card A \le card B \Leftrightarrow A \preccurlyeq\bullet B$.
3. $card A \lt card B \Leftrightarrow card A \le card B \land card A \ne card B$.

### 定义 3.14

设 $A$ 为集合, 若 $card A \le \aleph_0$, 则称 $A$ 为 *可数集* 或 *可列集*.

7230872e965642e0f6f6e2400057131638c9d29b
ipynb
Jupyter Notebook
st.ipynb
anqurvanillapy/ipynbs
baa63d7b503319106d6edf0a3dc4785580a282fa
MIT
st.ipynb
anqurvanillapy/ipynbs
baa63d7b503319106d6edf0a3dc4785580a282fa
MIT
2018-01-05T07:39:22.000Z
2018-01-05T07:39:22.000Z
st.ipynb
anqurvanillapy/ipynbs
baa63d7b503319106d6edf0a3dc4785580a282fa
MIT
Qwen/Qwen-72B
1. YES
2. YES