Coursera离散数学概论笔记（六）： 集合论之特殊关系及函数

---

1 等价关系

1.1 等价关系（equivalent relation）定义

等价关系 R 定义为：A 上的自反、对称、传递的二元关系，即符合：$xRx,xRy\rightarrow yRx,xRy \bigwedge yRz\rightarrow xRz$xRx,xRy→yRx,xRy⋀yRz→xRz 。

举几个例子：

三角形的相似、全等关系

学生的舍友关系

人的亲戚关系

整数集上的“模 k 相等”关系

1.2 等价类（equivalent class）

设 R 为 A 上的等价关系，对于每个 $a \in A$a∈A，a 的等价类记作 $[a]_R$[a]R​ （简记为 $ [a] $ ），定义为：$[a]_R = \{x|x \in A \bigwedge xRa\}$[a]R​={x∣x∈A⋀xRa} 。

a 称作 $[a]_R$[a]R​ 的代表元素。

等价类是 A 的子集，每个代表元素确定一个等价类，但等价类的代表元素不是唯一的。

举几个等价类的例子：

“模 2 相等”有 2 个等价类：[0] 和 [1]

相等关系 $E_A$EA​ 有 $|A|$∣A∣ 个不同的等价类，每个等价类都是单元素集合

全关系 $A \times A$A×A 只有一个等价类 $A$A

1.3 等价类性质

• A 上任何一个等价关系 R ，任何一个元素 a ，等价类 $[a]_R$[a]R​ 都不会是空集，因为总有 $aRa$aRa （等价关系的自反性）。
• 同一个等价类可能有不同的代表元素，或者说，不同的元素可能有相同的等价类。

1.4 等价类定理

• R 是 A 上的等价关系，则任意 $a,b \in A$a,b∈A ，$aRb$aRb 当且仅当 $[a]_R=[b]_R$[a]R​=[b]R​ 。

  证明如下：

• R 是 A 上的等价关系，则任意 $a,b \in A$a,b∈A ，要么 $[a]=[b]$[a]=[b] ，要么 $[a] \cap [b] = \empty$[a]∩[b]=∅ 。

  证明如下：

2 等价关系与划分

2.1 划分（partitions）的定义

划分是满足下列条件的集合 A 的子集构成的集合族，一般用 $\pi$π 来表示：

• $\forall B(b \in \pi \rightarrow \neq \emptyset)$∀B(b∈π→​=∅) （不空）
• $\cup \pi = A$∪π=A （不漏）
• $\forall B \forall B'(B \in \pi \bigwedge B' \in \pi \bigwedge B \neq B' \rightarrow B \cap B' = \empty)$∀B∀B′(B∈π⋀B′∈π⋀B​=B′→B∩B′=∅) （不交）

$\pi$π 中的元素称为划分的单元，特别约定 $A = \empty$A=∅ 时只有划分 $\empty$∅ 。

2.2 等价关系与划分

A 上的等价关系 R 的所有等价类的集合即构成了 A 的一个划分，称作等价关系 R 对应的划分：$\{[x]_R | x \in A\}${[x]R​∣x∈A} 。

反过来，集合 A 的一个划分 $\pi$π ，也对应 A 上的一等价关系 R ，称作划分 $\pi$π 对应的等价关系：$R = \{<x,y>|\exists B(B \in \pi \bigwedge x \in B \bigwedge y \in B)\}$R={<x,y>∣∃B(B∈π⋀x∈B⋀y∈B)} 或 $R = \cup\{B \times B | B \in \pi\}$R=∪{B×B∣B∈π}

有以下定理：对应 $\pi$π 的等价关系为 R ，当且仅当 R 对应的划分为 $\pi$π ，即等价关系和划分一一对应。

证明如下：

3 划分之间的关系

3.1 划分的“粗细”

如果 $\pi_1$π1​ 的每一个单元都包含于 $\pi_2$π2​ 的某个单元，称 $\pi_1$π1​ 细于 $\pi_2$π2​ ，表示为 $\pi_1 \leq \pi_2$π1​≤π2​ 。

如果 $\pi_1 \leq \pi_2$π1​≤π2​ 且 $\pi_1 \neq \pi_2$π1​​=π2​ ，则表示为 $\pi_1 < \pi_2$π1​<π2​ ，称作 “真细于” 。

将集合比作蛋糕的话，更细的划分可以理解为在更粗的划分上再切几刀：

3.2 划分的“细于”和等价关系的“子集”的联系

定理：$\pi_1,\pi_2$π1​,π2​ 分别是等价关系 $R_1,R_2$R1​,R2​ 对应的划分，那么 $R_1 \subseteq R_2 \leftrightarrow \pi_1 \leq \pi_2$R1​⊆R2​↔π1​≤π2​ 。

证明如下：

定理说明，越“小”（包含二元组较少）的等价关系对应越细的划分。说明两个特殊的等价关系：

• 最小的等价关系是相等关系 $E_A$EA​ ，对应最细的划分（每个单元仅含一个元素）。
• 最大的等价关系是全关系，对应最粗的划分（仅有一个单元）。

4 划分运算

4.1 积划分运算

划分 $\pi_1$π1​ 和 $\pi_2$π2​ 的积划分 $\pi_1 \cdot \pi_2$π1​⋅π2​ 是满足如下条件的划分：

• $\pi_1 \cdot \pi_2$π1​⋅π2​ 细于 $\pi_1$π1​ 和 $\pi_2$π2​

• 如果某个划分 $\pi$π 细于 $\pi_1$π1​ 和 $\pi_2$π2​ ，则 $\pi$π 一定细于 $\pi_1 \cdot \pi_2$π1​⋅π2​ （也就是说，$\pi_1 \cdot \pi_2$π1​⋅π2​ 是细于 $\pi_1$π1​ 和 $\pi_2$π2​ 的最粗划分）

积划分运算对应的示意图如下所示：

积划分运算对应等价关系交运算：$R_1$R1​ 和 $R_2$R2​ 分别是 $\pi_1$π1​ 和 $\pi_2$π2​ 对应的等价关系，则 $\pi_1 \cdot \pi_2$π1​⋅π2​ 是等价关系 $R_1 \cap R_2$R1​∩R2​ 对应的划分。

其证明如下：

4.2 和划分运算

划分 $\pi_1$π1​ 和 $\pi_2$π2​ 的和划分 $\pi_1 + \pi_2$π1​+π2​ 是满足如下条件的划分：

• $\pi_1 + \pi_2$π1​+π2​ 细于 $\pi_1$π1​ 和 $\pi_2$π2​

• 如果有某个划分 $\pi$π ， $\pi_1$π1​ 和 $\pi_2$π2​ 均细于 $\pi$π，则 $\pi_1 \cdot \pi_2$π1​⋅π2​ 一定细于 $\pi$π（也就是说，$\pi_1 \cdot \pi_2$π1​⋅π2​ 是细于 $\pi_1$π1​ 和 $\pi_2$π2​ 的最粗划分）

和划分运算对应的示意图如下所示：

和划分运算不对应等价关系交运算：等价关系中的传递性质对于并运算不封闭。

我们可以针对传递性质扩展并运算结果，定义一个二元关系 $R$R 的传递关系闭包 $t(R)$t(R) ，定义如下：

• $t(R)$t(R) 是传递的，$R \subseteq t(R)$R⊆t(R)
• 对于 A 上的任意一个具有传递性质且包含 $R$R 的关系 $R’$R’ ，$t(R) \subseteq R'$t(R)⊆R′

则和划分对于于等价关系并运算结果的传递闭包。

4.3 商集（quotient sets）

R​ 是 A 上的等价关系，称 A 的划分 $\{[a]_R | a \in A \}${[a]R​∣a∈A} 为 A 的 R 商集，记作 $A / R$A/R 。

每一个划分 $\pi$π 均为 A 上的一个商集，相应的商集的和、积对于划分的和与积，有以下关系式：

• $A / (R_1 \cap R_2) = A /R_1 \cdot A / R_2$A/(R1​∩R2​)=A/R1​⋅A/R2​
• $A / (R_1 \cup R_2) = A /R_1 + A / R_2$A/(R1​∪R2​)=A/R1​+A/R2​

5 序关系

5.1 序关系（ordered relation）定义

序关系 R 定义为：A 上的自反、反对称、传递的二元关系，即符合：$xRx,xRy \bigwedge yRx \rightarrow x = y,xRy \bigwedge yRz\rightarrow xRz$xRx,xRy⋀yRx→x=y,xRy⋀yRz→xRz 。

我们可以将 A 和定义在其上面的序关系 R 结合起来称作有序集（order set），用二元有序组 $<A,R>$<A,R> 表示，一般的有序集表示成 $<A,\leq>$<A,≤> 。（此处的“ $\leq$≤ ”只是一个记号）

举几个序关系的例子：

设 $a,b \in A$a,b∈A ，则有以下说法：

• 如果 $a \leq b$a≤b ，称 a 先于或等于 b（或 a 小于或等于 b ）。

• 如果 $¬ (a \leq b)$¬(a≤b) ，则称 $a,b$a,b 不可比较或者不可排序。

5.2 哈斯图（Hasse graph）

6 序关系中特殊元素

6.1 最大（小）元和极大（小）元

设 $<A,\leq>$<A,≤> 为有序集，$B \subseteq A$B⊆A ，则：

• B 的最小元 b ：$b \in B \bigwedge \forall x(x \in B \rightarrow b \leq x)$b∈B⋀∀x(x∈B→b≤x)

• B 的最大元 b ：$b \in B \bigwedge \forall x(x \in B \rightarrow x \leq b)$b∈B⋀∀x(x∈B→x≤b)

• B 的极小元 b ：$b \in B \bigwedge ¬\exists x(x \in B \bigwedge x \neq b \bigwedge x \leq b)$b∈B⋀¬∃x(x∈B⋀x​=b⋀x≤b)

• B 的极大元 b ：$b \in B \bigwedge ¬\exists x(x \in B \bigwedge x \neq b \bigwedge b \leq x)$b∈B⋀¬∃x(x∈B⋀x​=b⋀b≤x)

极大和最大的差别在于 B 中是否包含不可比较的元素。

举例：

关于最大（小）元和极大（小）元的定理：

• B 的最大（小）元必为 B 的极大（小）元。
• 如果 b 是有限集，则 b 的极大（小）元恒存在。
• 最大（小）元未必存在，存在则唯一。
• 极大（小）元对有限集必然存在，未必唯一。
• 不包含不可比较的元素的有序集必然有最大（小）元。
• 存在最大（小）元的有限有序集。其极大元就等于最大（小）元。

6.1 上（下）界和上（下）确界

设 $<A,\leq>$<A,≤> 为有序集，$B \subseteq A$B⊆A ，则：

• B 的上界 a ：$a \in A \bigwedge \forall x(x \in B \rightarrow x \leq a)$a∈A⋀∀x(x∈B→x≤a) （与 B 内元素都可比较的）

• B 的下界 a ：$a \in A \bigwedge \forall x(x \in B \rightarrow a \leq x)$a∈A⋀∀x(x∈B→a≤x) （与 B 内元素都可比较的）

• B 的上确界 a ：a 是 B 的所有上界的集合的最小元。

• B 的下确界 a ：a 是 B 的所有上界的集合的最大元。

举例：

关于上（下）界和上（下）确界的定理：

• 如果 b 是 B 的最大（小）元，则 b 是 B 是上（下）确界。
• 如果 b 是 B 的上（下）界，而且 $b \in B$b∈B ，则 b 一定是 B 的最大（小）元。
• 如果 B 有上（下）确界，则上（下）确界是唯一的。
• 上（下）界未必存在，存在时也未必唯一。
• 有了上（下）界，也未必存在上（下）确界。

6.3 链和反链

链（chain）：子集 B 中的任意两个元素都是可以比较的。即符合：$\forall x \forall y (x,y \in B \rightarrow x \leq y \bigvee y \leq x)$∀x∀y(x,y∈B→x≤y⋁y≤x)

反链（anti-chain）：子集 B 中的任意两个元素都是不可比较的。即符合：$\forall x \forall y (x,y \in B \rightarrow ¬(x \leq y) \bigvee ¬(y \leq x))$∀x∀y(x,y∈B→¬(x≤y)⋁¬(y≤x))

$|B|$∣B∣ 称作是链或者反链的长度。

关于链和反链的定理：设 $<A,\leq>$<A,≤> 为有限有序集，$B \subseteq A$B⊆A ，如果 A 中最长的链长度为 n，则 A 存在一个划分，划分有 n 个单元，每个单元都是一个反链。

6.4 半序关系（Partiall ordered relation）

半序关系 R 定义为：A 上的反自反、反对称、传递的二元关系，即符合：$¬(xRx),xRy \bigwedge yRx \rightarrow x = y,xRy \bigwedge yRz\rightarrow xRz$¬(xRx),xRy⋀yRx→x=y,xRy⋀yRz→xRz 。

将 $<A,R>$<A,R> 称作半序集，举两个个例子：

实数集合上的“大于”关系

公司内部职员的“下属”关系

7 函数

7.1 函数（function）定义

在集合论中，我们将函数看作是一种特殊的关系，具体定义如下：

如果 $X$X 到 $Y$Y 的二元关系 $f \subseteq X \times Y$f⊆X×Y ，对于每个 $x \in Y$x∈Y ，都有唯一的 $y \in Y$y∈Y ，使得 $<x,y> \in f$<x,y>∈f ，则称 $f$f 为 $X$X 到 $Y$Y 的函数，记作：$f:X \rightarrow Y$f:X→Y 。

当 $X = X_1 \times ... \times X_n$X=X1​×...×Xn​ 时，称 $f$f 为 n 元函数。

函数也称作映射（mapping） 或变换（transformation），也是一种特殊的关系，其具有以下性质：

• 前域和定义域重合
• 单值性：$<x,y> \in f \bigwedge <x,y'> \in f \rightarrow y = y'$<x,y>∈f⋀<x,y′>∈f→y=y′

举几个函数的例子：

7.2 函数特殊表示法

由于函数的单值性，我们可以把函数表示为：$y=f(x)$y=f(x) ，称 $x$x 为自变元，$y$y 为函数在 $x$x 处的值。从映射的角度来看，称 $y$y 为 $x$x 的像点，$x$x 为 $y$y 的源点。

不满足单值性的关系不适合这种表示法。

7.3 函数的规定方法

• 列表法：将函数包含的所有序偶排成一个表
• 图表法：用平面直角坐标系上的点集合表示函数
• 解析法：采用算术表达式或者其他命名式表示函数
• 归纳定义：作为关系和集合，函数也可以采用归纳定义的方法来进行定义（分为函数初值定义和函数调用自身部分的定义）

7.4 函数的相等和包含

设 $f:A \rightarrow B$f:A→B ，$g:C \rightarrow D$g:C→D，

如果 $A = C,B = D$A=C,B=D ，且对每个 $x \in A$x∈A ，都有：$f(x) = g(x)$f(x)=g(x) ，则函数 $f$f 等于 $g$g ，记作 $f = g$f=g 。

如果 $A \subseteq C,B = D$A⊆C,B=D ，且对每个 $x \in A$x∈A ，都有：$f(x) = g(x)$f(x)=g(x) ，则函数 $f$f 包含于 $g$g ，记作 $f \subseteq g$f⊆g 。

7.5 函数的个数

如果 $|X| = m$∣X∣=m ，$|Y| = n$∣Y∣=n ，则 $\{f|f:X \rightarrow Y\}${f∣f:X→Y} 的基数为 $n^m$nm ，即共有 $n^m$nm 个 $X$X 到 $Y$Y 的函数。

从 $X$X 到 $Y$Y 的全体函数构成的集合表示为 $Y^X$YX ，形式同基数的表达形式类似。

7.6 映像（image）

设 $f:X \rightarrow Y$f:X→Y ，$A \subseteq X$A⊆X ，将 $f'(A)$f′(A) 称作 $A$A 的映像，定义为：$f'(A) = \{y | \exists x(x \in A \bigwedge y = f(x))\}$f′(A)={y∣∃x(x∈A⋀y=f(x))} 。

由此可见，映像 $f'$f′ 是 $\rho(X)$ρ(X) 到 $\rho(Y)$ρ(Y) 的函数。

举一些特殊的映像例子：

• $f’(\empty)=\empty$f’(∅)=∅
• $f’(X) = Ran(f)$f’(X)=Ran(f) （函数的值域）
• $f'(\{x\}) = \{f(X)\}(x \in A)$f′({x})={f(X)}(x∈A)

映像还具有一些特性：

设 $f:X \rightarrow Y$f:X→Y ，对任意 $A \subseteq X,B \subseteq X$A⊆X,B⊆X ，有：

• $f'(A \cup B) = f'(A) \cup f'(B)$f′(A∪B)=f′(A)∪f′(B)
• $f'(A \cap B) \subseteq f'(A) \cap f'(B)$f′(A∩B)⊆f′(A)∩f′(B)
• $f'(A) - f'(B)\subseteq f'(A - B)$f′(A)−f′(B)⊆f′(A−B)

8 函数合成

8.1 函数合成的定义

设 $f:X \rightarrow Y, g:Y \rightarrow Z$f:X→Y,g:Y→Z ，那么关系的合成 $f \circ g$f∘g 是一个 $X$X 到 $Z$Z 的函数。

证明如下：

习惯上把 $f(x)$f(x) 和 $g(x)$g(x) 的合成记作 $g(f(x))$g(f(x)) ，所以函数的合成按照关系合成的相反顺序记作 $g \circ f$g∘f 。

8.2 函数合成运算的性质

• 函数合成满足结合律，不满足交换律。

• 函数 $f$f 的 n 次合成：$f^n$fn

• $f \circ E_x = E_y \circ f = f$f∘Ex​=Ey​∘f=f

• 若 $f^2 = f$f2=f ，则 $f$f 称作等幂函数。

9 特殊函数类

9.1 单射函数（injection）

如果任意 $x_1 \neq x_2$x1​​=x2​，且有 $f(x_1) \neq f(x_2)$f(x1​)​=f(x2​) ，则称 $f$f 为单射函数，也称作一对一函数。
有关单射函数的合成具有以下性质：

• 如果 $f$f 和 $g$g 都是单射函数，则其合成 $g \circ f$g∘f 也是单射函数。
• 如果$g \circ f$g∘f 是单射函数，则 $f$f 一定是单射函数。

9.2 满射函数（surjection）

如果任意 $y$y 都有 $x$x 使得 $y=f(x)$y=f(x) ，即 $f$f 的值域等于 $Y$Y ，则称 $f$f 为满射函数，也称作“映上的”函数。
有关单射函数的合成具有以下性质：

• 如果 $f$f 和 $g$g 都是满射函数，则其合成 $g \circ f$g∘f 也是满射函数。
• 如果$g \circ f$g∘f 是满射函数，则 $g$g 一定是满射函数。

9.3 双射函数（bijection）

如果 $f$f 既是单射函数又是满射函数，则其称作双射函数，也称作”一一对应“。

有关双射函数的合成具有以下性质：

• 如果 $f$f 和 $g$g 都是双射函数，则其合成 $g \circ f$g∘f 也是双射函数。
• 如果$g \circ f$g∘f 是双射函数，则 $f$f 一定是单射函数， $g$g 一定是满射函数。

9.4 逆函数（inverse function）

如果 $f$f 不是单射，则 $f\sim$f∼ 无法满足单值性，如果 $f$f 不是满射，则 $Dom(f \sim) \neq Y$Dom(f∼)​=Y ，所以只有双射函数存在逆函数。

双射函数 $f$f 的逆函数记作 $f^{-1}$f−1 ，也是双射函数，称 $f$f 是可逆的。

对于非双射函数，也存在类似逆函数的对应函数：

• 如果 $g \circ f = E_x$g∘f=Ex​ ，则称 $g$g 为 $f$f 的左逆函数（left inverse）。$f$f 有左逆函数当且仅当 $f$f 是单射函数。
• 如果 $f \circ g = E_y$f∘g=Ey​ ，则称 $g$g 为 $f$f 的右逆函数（right inverse）。$f$f 有右逆函数当且仅当 $f$f 是满射函数。

$f$f 可逆当且仅当 $f$f 既有左逆函数，又有右逆函数，而且左逆函数和右逆函数相等。

逆函数具有以下性质：

• $(f^{-1})^{-1} = f$(f−1)−1=f
• $f^{-1} \circ f = E_X$f−1∘f=EX​
• $f \circ f^{-1} = E_Y$f∘f−1=EY​
• $(g \circ f) ^{-1} = f^{-1} \circ g^{-1}$(g∘f)−1=f−1∘g−1