集合代数

集合的基本概念

集合的定义

由一些个体构成的整体称为集合。称为集合的个体为元素。

集合的表示

• 枚举法：列举出集合中的所有元素。

• 谓词表示法：通过谓词概括集合中的元素。 例如：

• 枚举法：自然数集合：$\mathbb{N} = \lbrace 1, 2, 3, \cdots \rbrace$

• 谓词表示法：偶数集合：$A = \lbrace x | x = 2k, k \in \mathbb{N} \rbrace$

• 集合的树形结构表示：

          A
         /|\
        / | \
       /  |  \
      /   |   \
     /    |    \
  {a, b}{{b}}   d
   /  \   |
  a    b {b}
          |
          b

集合的元素具有的性质

• 无序性：集合中的元素之间没有先后次序之分。
• 相异性：集合中的元素各不相同。
• 确定性：一个元素要么属于一个集合，要么不属于一个集合。
• 任意性：集合中的元素可以是任意的，也可以是集合。

元素和集合的关系

$\in$：元素属于集合。 $\notin$：元素不属于集合。

集合与集合的关系

$$A \subseteq B \Leftrightarrow \forall x(x \in A \Rightarrow x \in B)$$ $$A = B \Leftrightarrow A \subseteq B \land B \subseteq A$$ $$A \varsubsetneqq B \Leftrightarrow A \subseteq B \land A \neq B$$ $$A \nsubseteq B \Leftrightarrow \exists x(x\in A \land x \notin B)$$

空集

不包含任何元素的集合称为空集，记作 $\varnothing$ 空集是任何集合的子集，即 $\varnothing \subseteq A$ 空集是唯一的。

全集

包含一切可能元素的集合称为全集，记作 $E$。

全集具有相对性，与讨论的问题有关，不存在绝对的全集。

幂集

$$P(A) = \lbrace x \ | \ x \subseteq A \rbrace$$ 例如：$A = \lbrace a, b \rbrace$，则 $P(A) = \lbrace \varnothing, \lbrace a \rbrace, \lbrace b \rbrace, \lbrace a, b \rbrace \rbrace$

集合的运算

$$\begin{aligned} 并 & & A \cup B &= \lbrace x \ | \ x \in A \lor x \in B \rbrace \newline 交 & & A \cap B &= \lbrace x \ | \ x \in A \land x \in B \rbrace \newline 相对补\ /\ 差 & & A - B &= \lbrace x \ | \ x \in A \land x \notin B \rbrace \newline 绝对补 & & \overline{A} &= ~A = E - A \newline 对称差 & & A \oplus B &= (A - B) \cup (B - A) \newline \newline 广义并 & & \bigcup_{i=1}^n A_i &= \lbrace x \ | \ \exists z(z \in A \land x \in z) \rbrace \newline 广义交 & & \bigcap_{i=1}^n A_i &= \lbrace x \ | \ \forall z(z \in A \to x \in z) \rbrace \newline \end{aligned}$$

1. $\displaystyle \bigcup \varnothing = \varnothing$，$\displaystyle \bigcap \varnothing$ 无意义
2. 广义运算减少集合的层次（括弧减少一层）
3. 广义运算的计算：一般情况下可以转变成初级运算

运算顺序

一类运算：广义并，广义交，幂集，绝对补，运算由右向左进行 二类运算：初级运算 $\cup$，$\cap$，$-$，$\oplus$，运算由左向右进行 混合运算：一类运算优先于二类运算

有穷集合的计数

1. 文氏图法
2. 包含排斥原理（容斥原理） $$\begin{aligned} \left| \overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n} \right| =& \left| E \right| \newline &- \sum_{i=1}^n \left| A_i \right| \newline &+ \sum_{1 \leq i < j \leq n} \left| A_i \cap A_j \right| \newline &- \cdots \newline &+ (-1)^n \left| A_1 \cap A_2 \cap \cdots \cap A_n \right| \end{aligned}$$ 推论：$n$ 个集合的并的元素个数 $$\begin{aligned} \left| A_1 \cup A_2 \cup \cdots \cup A_n \right| =& \sum_{i=1}^n \left| A_i \right| \newline &- \sum_{1 \leq i < j \leq n} \left| A_i \cap A_j \right| \newline &+ \cdots \newline &+ (-1)^{n-1} \left| A_1 \cap A_2 \cap \cdots \cap A_n \right| \end{aligned}$$

$$\left| A_1 \cup A_2 \cup \cdots \cup A_n \right| = \left|E\right| - \left| \overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n} \right|$$

集合恒等式

只涉及一个运算符的恒等式

涉及两个不同运算符的恒等式

涉及补运算的恒等式

涉及空集和全集的恒等式

集合等式的证明

命题演算法

例3 证明 $A \cup (A \cap B) = A$ （吸收律）

$$\begin{aligned} \text{证：任取 } x \newline x \in A \cup (A \cap B) \Leftrightarrow &x \in A \lor x \in A \cap B \newline \Leftrightarrow &x \in A \lor (x \in A \land x \in B) \newline \Leftrightarrow &(x \in A \land x \in E) \lor (x \in A \land x \in B) \newline \Leftrightarrow &x \in A \land (x \in E \lor x \in B) \newline \Leftrightarrow &x \in A \newline \text{因此得 } A \cup (A \cap B) = A. \end{aligned}$$

等式置换法

直接运用集合恒等式演算。

二元关系

二元关系的性质

有序对与笛卡尔积

有序对

由两个元素 $x$ 和 $y$，按照一定的顺序组成的二元组称为有序对，记作 $\langle x,y \rangle$.

有序对性质：

• 有序性：$<x,y> \neq \langle y,x \rangle$
• 相等性：$<x,y> = <u,v> \Leftrightarrow x = u \land y = v$

笛卡尔积

$$A \times B = \lbrace <x,y> \ | \ x \in A \land y \in B \rbrace$$

笛卡尔积的性质：

• 不适合交换律：
• 不适合结合律：
• 对于并和交运算满足分配律： $$A \times (B \cup C) = (A \times B) \cup (A \times C)$$ $$A \times (B \cap C) = (A \times B) \cap (A \times C)$$
• $A \times \varnothing = \varnothing \times B = \varnothing$
• $\left|A \times B\right| = \left|A\right| \times \left|B\right|$

二元关系

二元关系的定义

集合 $R$ 称为一个二元关系，当：

• $R$ 是空集
• $R$ 中的所有元素都是有序对 若 $<x,y> \in R$，则称 $x$ 与 $y$ 有关系 $R$，记作 $xRy$. 若 $<x,y> \notin R$，则称 $x$ 与 $y$ 无关系 $R$，记作 $x \cancel{R} y$.

设 $A$ 和 $B$ 是两个集合，$A \times B$ 的任意子集所定义的二元关系称为从 $A$ 到 $B$ 的二元关系. 当 $A = B$ 时，称为 $A$ 上的二元关系.

重要关系的实例

设 $A$ 为集合

• 空关系：$\varnothing$ 是 $A$ 上的关系，称为空关系
• 全域关系：$E_A = \lbrace <x, y> \ | \ x in A \land y \in A \rbrace = A \times A$ 是 $A$ 上的关系，称为全域关系
• 相等关系：$I_A = \lbrace <x, x> \ | \ x \in A \rbrace$ 是 $A$ 上的关系，称为相等关系
• 小于等于关系：$L_A = \lbrace <x, y> \ | \ x, y \in A \land x \leq y \rbrace$ 是 $A$ 上的关系，称为小于等于关系
• 整除关系：$D_A = \lbrace <x, y> \ | \ x, y \in A \land x | y \rbrace$ 是 $A$ 上的关系，称为整除关系
• 包含关系：$R_\subseteq = \lbrace <x, y> \ | \ x, y \in A \land x \subseteq y \rbrace$ 是 $A$ 上的关系，称为包含关系

关系的表示

关系矩阵

$A = \lbrace x_1, x_2, \cdots, x_m \rbrace$，$B = \lbrace y_1, y_2, \cdots, y_n \rbrace$，$R$ 是 $A$ 到 $B$ 的关系，$R$ 的关系矩阵是一个 $m \times n$ 的布尔矩阵 $M_R = [r_{ij}]_{m \times n}$，其中 $$r_{ij} = 1 \Leftrightarrow x_i R y_j$$

关系图

$G_R = (A, R)$，$A$ 是顶点集，$R$ 是边集，$R$ 是 $A$ 到 $A$ 的关系，$G_R$ 是一个有向图.

关系矩阵适合表示从 $A$ 到 $B$ 的关系或 $A$ 上的关系（ $A$，$B$ 为有穷集） 关系图适合表示有穷集 $A$ 上的关系

关系的运算

• 定义域：$\mathrm{dom}R = \lbrace x \ | \ \exists y(xRy) \rbrace$

• 值域：$\mathrm{ran}R = \lbrace y \ | \ \exists x(xRy) \rbrace$

• 域：$fldR = \mathrm{dom}R \cup \mathrm{ran}R$

• 逆运算：$R^{-1} = \lbrace <y, x> \ | \ <x, y> \in R \rbrace$

• 复合运算：$R \circ S = \lbrace <x, z> \ | \ \exists y(xRy \land ySz) \rbrace$

  • $R \circ S \neq S \circ R$

• 幂运算： $$R^n = \begin{cases} {<x, x> \ | \ x \in A} = I_A & n = 0 \newline R \circ R^{n-1} & n > 0 \end{cases}$$

• 限制：$R \upharpoonright A = R \cap (A \times A) = \lbrace <x, y> \ | \ <x, y> \in R \land x \in A \rbrace$

  • $R$ 在 $A$ 上的限制 $R \upharpoonright A$ 是 $R$ 在 $A$ 上的部分，是 $R$ 的子关系，即 $R \upharpoonright A \subseteq R$

• 像：$R[A] = \lbrace y \ | \ \exists x(x \in A \land xRy) \rbrace = \mathrm{ran}(R \upharpoonright A)$

  • A 在 $R$ 下的像 $R[A]$ 是 $\mathrm{ran}R$ 的子集，即 $R[A] \subseteq \mathrm{ran}R$

关系的运算性质

• 逆运算的逆运算：$(F^{-1})^{-1} = F$

• 逆运算的域：$\mathrm{dom}R^{-1} = \mathrm{ran}R, \quad \mathrm{ran}R^{-1} = \mathrm{dom}R$

• 复合运算的逆运算：$(F \circ G)^{-1} = G^{-1} \circ F^{-1}$

• 复合运算的结合律：$(F \circ G) \circ H = F \circ (G \circ H)$

• 复合运算的分配律： $$\begin{aligned} F \circ (G \cup H) = (F \circ G) \cup (F \circ H) & & (G \cup H) \circ F = (G \circ F) \cup (H \circ F) \newline F \circ (G \cap H) \subseteq (F \circ G) \cap (F \circ H)& & F \circ (G \cap H) \supseteq (F \circ G) \cap (F \circ H) \end{aligned}$$ 可以推广到有限个集合的并和交

• 相等关系上的复合运算：$I_A \circ R = R \circ I_A = R$

• 限制与像运算的分配律： $$\begin{aligned} F \upharpoonright (A \cup B) &= F \upharpoonright A \cup F \upharpoonright B & F \upharpoonright (A \cap B) &= F \upharpoonright A \cap F \upharpoonright B \newline F [A \cup B] &= F[A] \cup F[B] & F [A \cap B] &\subseteq F[A] \cap F[B] \end{aligned}$$

幂运算的性质

不同的幂运算只有有限个

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

关系的性质

• 自反性：$R$ 是自反的，当 $\forall x(x \in A \to xRx)$

• 反自反性：$R$ 是反自反的，当 $\forall x(x \in A \to x \cancel{R} x)$

• 对称性：$R$ 是对称的，当 $\forall x \forall y(xRy \to yRx)$

• 反对称性：$R$ 是反对称的，当 $\forall x \forall y(xRy \land yRx \to x = y)$

• 传递性：$R$ 是传递的，当 $\forall x \forall y \forall z(xRy \land yRz \to xRz)$

关系的闭包

关系的闭包

需要改造 $R$ 为一个具有某种性质的关系，$R$ 的闭包是 $A$ 上具有该性质的关系中最小的一个 $R’$。即：

• $R’$ 具有该性质
• $R \subseteq R'$
• 对 $A$ 上任何具有该性质的关系 $S$，$R’ \subseteq S$

$R$ 的自反闭包记作 $r(R) = R \cup R^{0} = R \cup I_A$
$R$ 的对称闭包记作 $s(R) = R \cup R^{-1}$
$R$ 的传递闭包记作 $t(R) = R \cup R^2 \cup R^3 \cup \cdots$

对有穷集 $A(\left|A\right| = n)$，$R$ 的传递闭包 $t(R) = R \cup R^2 \cup \cdots \cup R^n$

矩阵表示

分别设 $R, r(R), s(R), t(R)$ 的关系矩阵为 $M, M_r, M_s, M_t$，则 $$\begin{aligned} M_r &= M + I M_s &= M + M^T M_t &= M + M^2 + M^3 + \cdots + M^n \end{aligned}$$

图表示

• $r(R)$：在 $G_R$ 中添加自环
• $s(R)$：在 $G_R$ 中添加对称边
• $t(R)$：在 $G_R$ 中添加传递边

闭包的性质

$R$ 是自反的 $\Leftrightarrow$ $r(R) = R$
$R$ 是对称的 $\Leftrightarrow$ $s(R) = R$
$R$ 是传递的 $\Leftrightarrow$ $t(R) = R$

若 $R_1 \subseteq R_2$，则
$r(R_1) \subseteq r(R_2)$
$s(R_1) \subseteq s(R_2)$
$t(R_1) \subseteq t(R_2)$

• $r(s(R)) = s(r(R))$
• $r(t(R)) = t(r(R))$
• $s(t(R)) \subseteq t(s(R))$
• $t(s(r(R))) = r(t(s(R))) = t(r(s(R)))$

偏序关系

偏序关系

若 $R$ 是自反的、反对称的、传递的，则称 $R$ 是偏序关系。记作 $\preccurlyeq$。 设 $\preccurlyeq$ 是一个偏序关系，若 $<x, y> \in \preccurlyeq$，则称 $x$ 小于等于 $y$，记作 $x \preccurlyeq y$。

偏序关系的性质

设 $R$ 是 $A$ 上的偏序关系

1. $\forall x, y \in A, x \prec y \Leftrightarrow x \preccurlyeq y \land x \neq y$
2. $\forall x, y \in A, x 与 y \textcolor{orange}{可比} \Leftrightarrow x \preccurlyeq y \lor y \preccurlyeq x$
   • 若 $\forall x, y \in A, x 与 y \textcolor{orange}{可比}$，则称 $R$ 是全序关系
   • 实例：数集上的小于或等于关系是全序关系，整除关系不是正整数集合上的全序关系
3. 若 $x \prec y \land \neg\exists z(x \prec z \prec y)$，则称 $y$ 覆盖 $x$

偏序集

集合 $A$ 与其上的偏序关系 $\preccurlyeq$ 称为偏序集，记作 $\langle A, \preccurlyeq \rangle$ 如：$\langle \mathbb{Z}, \leq \rangle$，$<P(A), \subseteq>, \langle \mathbb{N}, | \rangle$

哈斯图

在 $\langle A, \preccurlyeq \rangle$ ，若 $y$ 覆盖 $x$，则 $y$ 在哈斯图中位于 $x$ 的上方，且用一条从 $x$ 指向 $y$ 的有向边表示。（绘制时忽略箭头）

哈斯图是简化的关系图，是由偏序关系的性质而省略的：

1. 自反性：每个顶点都有自环，故省略自环。
2. 反对称性：从小到大的有向边只有一条，故省略箭头。
3. 传递性：$<a, b>, <b, c> \in R \Rightarrow <a, c> \in R$，故省略 $\langle a, c \rangle$ 的有向边。

特殊元素

最大元、最小元、极大元、极小元

设 $\langle A, \preccurlyeq \rangle$ 是一个偏序集， $B \subseteq A$，$\color{cyan}y \in B$，则

1. 最大元：若 $\forall x(x \in B \to x \preccurlyeq y)$，则称 $y$ 是 $B$ 的最大元
2. 最小元：若 $\forall x(x \in B \to y \preccurlyeq x)$，则称 $y$ 是 $B$ 的最小元
3. 极大元：若 $\forall x(x \in B \to (y \preccurlyeq x \to x = y))$，则称 $y$ 是 $B$ 的极大元
4. 极小元：若 $\forall x(x \in B \to (x \preccurlyeq y \to x = y))$，则称 $y$ 是 $B$ 的极小元

最大元和极小元要求集合中所有元素与其有偏序关系
极大元和极小元仅要求没有比它更大或更小的元素。

最大元和最小元不一定存在，但若存在则唯一。
极大元和极小元一定存在，但不一定唯一。

最大元一定是极大元，最小元一定是极小元。

上界、下界、上确界、下确界

设 $\langle A, \preccurlyeq \rangle$ 是一个偏序集，$B \subseteq A$，$\color{cyan}y \in A$，则

1. 上界：若 $\forall x(x \in B \to x \preccurlyeq y)$，则称 $y$ 是 $B$ 的上界
2. 下界：若 $\forall x(x \in B \to y \preccurlyeq x)$，则称 $y$ 是 $B$ 的下界
3. 上确界：若 $C = \lbrace y \ | \ y \text{ 是 } B \text{ 的上界} \rbrace$，则 $C$ 的最小元称为 $B$ 的上确界或最小上界，记作 $\text{sup}B$
4. 下确界：若 $C = \lbrace y \ | \ y \text{ 是 } B \text{ 的下界} \rbrace$，则 $C$ 的最大元称为 $B$ 的下确界或最大下界，记作 $\text{inf}B$

上下界与最大最小元的区别在于，上下界是在整个偏序集中寻找，而最大最小元是在指定的子集中寻找。

上界和下界不一定存在，若存在也不一定唯一。 上确界和下确界不一定存在，若存在一定唯一。

一个集合的最小元是它的下确界，最大元是它的上确界。反之不一定成立。

等价关系

等价关系与划分

若 $R$ 是自反的、对称的、传递的，则称 $R$ 是等价关系。 设 $R$ 是一个等价关系，若 $xRy$，则称 $x$ 与 $y$ 是等价的，记作 $x \sim y$.

等价类

设 $R$ 是 $A$ 上的等价关系，$x \in A$，则 $$[x]_R = \lbrace y \ | \ y \in A \land xRy \rbrace$$

$$\forall x \in A, [x]_R \neq \varnothing, [x]_R \subseteq A$$ $$\forall x, y \in A, [x]_R \cap [y]_R = \begin{cases} \varnothing & x \nsim y \newline [x]_R & x \sim y \end{cases}$$ $$\bigcup \lbrace [x]_R | x \in A \rbrace = A$$

商集与划分

$$A/R = \lbrace [x]_R \ | \ x \in A \rbrace$$ 实例：$A = \lbrace 1, 2, \cdots 8 \rbrace$，关于模 $3$ 同余的等价关系 $R$ 的商集 $A/R = \lbrace [1]_R, [2]_R, [3]_R \rbrace = \lbrace \lbrace 1, 4, 7 \rbrace, \lbrace 2, 5, 8 \rbrace, \lbrace 3, 6 \rbrace \rbrace$

若 $A$ 的子集族 $\pi(\pi \subseteq P(A))$ 满足

• $\varnothing \notin \pi$
• $\bigcup \pi = A$ 则称 $\pi$ 是 $A$ 的一个覆盖。

若 $A$ 的子集族 $\pi$ 是一个覆盖，且

• $\forall x \forall y(x, y \in \pi land x \neq y \to x \cap y = \varnothing)$ 则称 $\pi$ 是 $A$ 的一个划分，$\pi$ 的元素称为 $A$ 的划分块。

集合 $A$ 上的一个等价关系 $R$ , 决定了 $A$ 的一个划分，该划分就是商集 $A/R$

集合 $A$ 的一个划分,确定 $A$ 的元素间的一个等价关系

函数

函数的定义

设 $F$ 为 二元关系 ，若 $F$ 满足 $\forall x \in \mathrm{dom}F$ 都存在唯一的 $y \in \mathrm{ran}F$ 使 $xFy$ 成立，则称 $F$ 为函数 。 对于函数 $F$，若有 $xFy$，则记作 $y = F(x)$，并称 $y$ 为 $F$ 在 $x$ 处的值

函数相等

$$F = G \Leftrightarrow F \subseteq G \land G \subseteq F \Leftrightarrow \mathrm{dom}F = \mathrm{dom}G \land \forall x (x \in \mathrm{dom}F \to F(x) = G(x))$$

设 $A$ 和 $B$ 是两个集合，$f$ 为函数， $\mathrm{dom}F = A$，$\mathrm{ran}F \subseteq B$，则称 $f$ 为从 $A$ 到 $B$ 的函数，记作 $f: A \to B$ 。

从 $A$ 到 $B$ 的函数的集合

所有从 $A$ 到 $B$ 的函数的集合记作 $B^A$。 $$B^A = \lbrace f \ | \ f: A \to B \rbrace$$ $$\left|B^A\right| = \left|B\right|^{\left|A\right|}$$

特别地： $A = \varnothing$，则 $B^A = B^\varnothing = \lbrace \varnothing \rbrace$ $A \ne \varnothing$ 且 $B = \varnothing$，则 $B^A = \varnothing^A = \varnothing$

函数的像和完全原像

设 $f: A \to B$，$A_1 \subseteq A$，$B_1 \subseteq B$，则

1. $A_1$ 在 $f$ 下的像为 $f(A_1) = \lbrace f(x) \ | \ x \in A_1 \rbrace$
2. $B_1$ 在 $f$ 下的完全原像为 $f^{-1}(B_1) = \lbrace x \ | \ f(x) \in B_1 \rbrace$

像和函数值的区别： $f(x) \in B$，$f(A_1) \subseteq B$

$$\begin{aligned} f^{-1}(f(A_1)) \neq A_1, \quad A_1 \subseteq f^{-1}(f(A_1)) \newline f(f^{-1}(B_1)) \neq B_1, \quad f(f^{-1}(B_1)) \subseteq B_1 \end{aligned}$$ 前者是因为 $f$ 不一定是单射，后者是因为 $f$ 不一定是满射。

函数的性质

• 单射：$\forall x_1, x_2 \in \mathrm{dom}F, F(x_1) = F(x_2) \Leftrightarrow x_1 = x_2$
• 满射：$\mathrm{ran}F = B$
• 双射：若 $f$ 既是单射又是满射，则称 $f$ 为双射的。

某些重要函数

1. 常函数：$f: A \to B$，$\forall x \in A, f(x) = b$，称 $f$ 为常函数。
2. 恒等函数：$I_A = \lbrace <x, x> \ | \ x \in A \rbrace$，$I_A$ 是 $A$ 上的函数，称为恒等函数。
3. 单调函数：$\langle A, \preceq \rangle$ 和 $\langle B, \preceq \rangle$ 是两个偏序集，$f: A \to B$。
   • 若 $\forall x_1, x_2 \in A, x_1 \preceq x_2 \Rightarrow f(x_1) \preceq f(x_2)$，则称 $f$ 为单调递增函数。
   • 若 $\forall x_1, x_2 \in A, x_1 \prec x_2 \Rightarrow f(x_1) \prec f(x_2)$，则称 $f$ 为严格单调递增函数。
   • 类似的，可以定义单调递减函数和严格单调递减函数。
4. 特征函数：$A$ 是集合，对任意的 $A’ \subseteq A$，定义 $f: A \to \lbrace 0, 1 \rbrace$，$f(x) = \begin{cases} 1, & x \in A’ \newline 0, & x \notin A’ \end{cases}$，称 $f$ 为 $A’$ 的特征函数，记为 $\chi_{A’}$。不同的子集对应不同的特征函数。
5. 自然映射：设 $R$ 是集合 $A$ 上的等价关系，$g: A \to A/R$，$g(x) = [x]_R$，称 $g$ 为 $A$ 到 $A/R$ 的自然映射。

不同的等价关系确定不同的自然映射
恒等关系确定的自然映射是双射
其他自然映射一般来说只是满射

函数的运算

复合运算

若 $f$ 和 $g$ 是函数，则 $h = f \circ g$ 也是函数，满足：

1. $\mathrm{dom}h = \lbrace x \ | \ x \in \mathrm{dom}f \land f(x) \in \mathrm{dom}g \rbrace$
2. $\forall x \in \mathrm{dom}h, h(x) = g(f(x))$

复合运算的性质

1. 若 $f: A \to B$ 是单射的，$g: B \to C$ 是单射的，则 $g \circ f: A \to C$ 是单射的。
2. 若 $f: A \to B$ 是满射的，$g: B \to C$ 是满射的，则 $g \circ f: A \to C$ 是满射的。
3. 若 $f: A \to B$ 是双射的，$g: B \to C$ 是双射的，则 $g \circ f: A \to C$ 是双射的。

上述的逆命题都不一定成立。

设 $f: A \to B$，则 $f = f \circ I_B = I_A \circ f$。

反函数

1. 函数 $f$ 的逆 $f^{-1}$ 不一定是函数，只是个二元关系
2. 单射函数的逆是函数，且 $f: A \to B$ 的逆函数 $f^{-1}$ 是 $\mathrm{ran}f$ 到 $A$ 的双射函数。
3. 双射函数 $f: A \to B$ 的逆是在 $B$ 到 $A$ 的双射函数。

对双射函数 $f: A \to B$ $$f^{-1} \circ f = I_A, \quad f \circ f^{-1} = I_B$$

集合的等势

设 $A$ 和 $B$ 是两个集合，若存在双射函数 $f: A \to B$，则称 $A$ 和 $B$ 是等势的，记作 $A \approx B$。

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

实例：

• $\mathbb{N} \approx \mathbb{Z} \approx \mathbb{Q} \approx \mathbb{N \times N}$
• $a, b \in \mathbb{R}, a < b$，$(a, b) \approx (a, b] \approx [a, b] \approx [a, b) \approx \mathbb{R}$
  • 以 $[0, 1] \approx (0, 1)$ 为例。
  • $A = {0, 1, 1 / 2, 1 / 3, \cdots} \subset [0, 1]$
  • $B = {1 / 2, 1 / 3, 1 / 4, \cdots} \subset (0, 1)$
  • 关键在于构造双射函数 $f: A \to B$，$f(x) = x / (x + 2)$
• $P(A) \approx \lbrace0, 1\rbrace^A$，$P(A)$ 是 $A$ 的幂集，$\lbrace 0, 1 \rbrace^A$ 是 $A$ 到 $\lbrace 0, 1 \rbrace$ 的函数集合。双射函数为 $f: P(A) \to {0, 1}^A$，$f(A’) = \chi_{A’}$

康托定理

1. $\mathbb{N} \not\approx \mathbb{R}$
2. $A \not \approx P(A)$

证明

1. 定义基数：如果两个集合之间存在双射（双向一一对应），则称这两个集合等势，表示为它们的基数相同。我们希望证明 $\mathbb{N}$ 和 $\mathbb{R}$ 不等势，换句话说，$\mathbb{R}$ 的基数大于 $\mathbb{N}$ 的基数。

2. 假设反证法：假设 $\mathbb{R}$ 和 $\mathbb{N}$ 等势，也就是说，假设存在一个从 $\mathbb{N}$ 到 $\mathbb{R}$ 的双射 $f \colon \mathbb{N} \to \mathbb{R}$。这样，所有实数可以被自然数“列举”出来。

3. 使用康托尔对角线法则：我们接下来将通过对角线法则，展示出在 $\mathbb{R}$ 中总有一个实数无法通过 $f$ 来与自然数一一对应，从而得出矛盾。

   • 考虑单位区间 $[0, 1]$ 中的实数，可以表示为无限小数（例如：0.123456…）。
   • 假设我们能够通过 $f$ 列出这些实数：$f(1), f(2), f(3), \dots$，其中每个 $f(n)$ 都表示 $[0,1]$ 中的一个实数，其小数部分为 $f(n) = 0.a_{n1}a_{n2}a_{n3}\dots$，其中 $a_{ni}$ 表示第 $n$ 个数的第 $i$ 位小数。
   • 现在通过对角线法构造一个新的实数 $r$，使得 $r$ 的第 $i$ 位小数 $b_i$ 与 $f(i)$ 的第 $i$ 位小数 $a_{ii}$ 不同。例如：可以令 $b_i$ 取值为 $9$（若 $a_{ii} \neq 9$），或 $8$（若 $a_{ii} = 9$）。
   • 由于 $r$ 的每一位与对应的 $f(i)$ 在第 $i$ 位不同，因此 $r \neq f(i)$ 对所有 $i$ 都成立。

4. 矛盾产生：这个通过对角线法构造出来的 $r$ 在 $[0, 1]$ 中，但根据假设，$f$ 应该是一个双射，也就是说，应该能够“列举”出所有实数。然而，$r$ 不在这列举出来的实数序列中，这与 $f$ 为双射的假设矛盾。

因此，假设 $\mathbb{N}$ 和 $\mathbb{R}$ 等势是错误的，$\mathbb{R}$ 的基数严格大于 $\mathbb{N}$ 的基数。

集合的优势

设 $A$ 和 $B$ 是两个集合，若存在单射函数 $f: A \to B$，则称 $B$ 优势于 $A$，记作 $A \preccurlyeq\cdot B$。如果 $B$ 不优势于 $A$，则记作 $B \not\preccurlyeq\cdot A$。

设 $A$ 和 $B$ 是两个集合，若 $A \preccurlyeq\cdot B$ 且 $A \not\approx B$，则称 $B$ 真优势于 $A$，记作 $A \prec\cdot B$。如果 $B$ 不真优势于 $A$，则记作 $B \not\prec\cdot A$。

实例：

• $\mathbb{N} \preccurlyeq\cdot \mathbb{N}, \mathbb{N} \preccurlyeq\cdot \mathbb{R}, A \preccurlyeq\ P(A)$
• $\mathbb{R} \not\preccurlyeq\cdot \mathbb{N}$
• $\mathbb{N} \prec\cdot \mathbb{R}, \mathbb{N} \not\prec\cdot \mathbb{N}, A \prec\cdot P(A)$

性质

1. $A \preccurlyeq\cdot A$
2. $A \preccurlyeq\cdot B \land B \preccurlyeq\cdot C \Rightarrow A \preccurlyeq\cdot C$
3. $A \preccurlyeq\cdot B \land B \preccurlyeq\cdot A \Rightarrow A \approx B$

式 3. 可以用于构造两个单射函数证明两个集合等势。

自然数的集合定义

$a^+ = a \cup \lbrace a \rbrace$，称 $a^+$ 为 $a$ 的后继。 $$\begin{aligned} 0 &= \varnothing \newline 1 &= 0^+ = \lbrace 0 \rbrace = \lbrace \varnothing \rbrace \newline 2 &= 1^+ = \lbrace 0, 1 \rbrace = \lbrace \varnothing, \lbrace 0 \rbrace \rbrace \newline 3 &= 2^+ = \lbrace 0, 1, 2 \rbrace = \lbrace \varnothing, \lbrace 0 \rbrace, \lbrace 0, 1 \rbrace \rbrace \newline \cdots \end{aligned}$$

有穷集与无穷集

一个集合是 有穷的 当且仅当它与某个自然数等势。否则，它是 无穷的。 实例：

1. $\lbrace a, b, c \rbrace$ 是有穷集，与 $3 = \lbrace 0, 1, 2 \rbrace$ 等势。
2. $\mathbb{N}$ 和 $\mathbb{R}$ 是无穷集。

任何有穷集只与某个自然数等势，而无穷集与任何自然数都不等势。

集合基数

1. 对于有穷集 $A$，$A$ 的基数是 $\mathrm{card}A = n \Leftrightarrow A \approx n$，称 $n$ 为集合 $A$ 的基数。
2. 自然数集合 $\mathbb{N}$ 的基数是 $\aleph_0$
3. 实数集 $\mathbb{R}$ 的基数是 $\aleph$

集合基数的性质

1. $\mathrm{card}A = \mathrm{card}B \Leftrightarrow A \approx B$
2. $\mathrm{card}A \le \mathrm{card}B \Leftrightarrow A \preccurlyeq\cdot B$
3. $\mathrm{card}A < \mathrm{card}B \Leftrightarrow A \prec\cdot B$

$$\begin{aligned} \mathrm{card}\mathbb{Z} = \mathrm{card}\mathbb{N} &= \mathrm{card}\mathbb{Q} = \mathrm{card}\mathbb{N \times N} = \aleph_0 \newline \mathrm{card}\mathbb{R} = \mathrm{card}[a, b] = \mathrm{card}(c, d) &= \mathrm{card} P(N) = \mathrm{card} 2^\mathbb{N} = \aleph \newline \end{aligned}$$ 有 $\aleph_0 < \aleph$

若 $\mathrm{card}A \le aleph_0$，则称 $A$ 是可数的，否则称 $A$ 是不可数的。