二元关系的性质

有序对与笛卡尔积

有序对

由两个元素 $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$ 的元素间的一个等价关系