7.特殊关系

1.等价关系

1. 设 $R$ 为非空集合 $A$ 上的关系，如果 $R$ 是自反的，对称的和传递的，则称 $R$ 为 $A$ 上的等价关系。

2. 设 $R$ 为非空集合 $A$ 上的等价关系，$\forall x \in A$，令$[x]_{R}=\{y \mid y \in A \land xRy\}$， 称 $[x]_{R}$ 为 $x$ 关于 $R$ 的等价类，简称为 $x$ 的等价类，简记为 $[x]$。

   • 例：设 $A=\{1,2, \dots, 8\}$，定义 $A$ 上的关系 $R$： $R=\{<x,y> \mid x,y \in A \land x \equiv y(\bmod 3)\}$，其中 $x \equiv y(\bmod 3)$ 称作 $x$ 与 $y$ 模3相等，即 $x$ 除以3的余数与 $y$ 除以3的余数相等，求等价类。
     解：
     $[1]=[4]=[7]=\{1,4,7\}$
     $[2]=[5]=[8]=\{2,5,8\}$
     $[3]=[6]=\{3,6\}$

3. 设 $R$ 为非空集合 $A$ 上的等价关系，以 $R$ 的所有等价类作为元素的集合称为 $A$ 关于 $R$ 的商集，记作 $A/R=\{[x]_{R} \mid x \in A\}$

   • 例：$A/R=\{\{1,4,7\},\{2,5,8\},\{3,6\}\}$

4. 设 $A$ 为非空集合，若 $A$ 的子集族 $\pi(\pi \subseteq P(A))$ 满足如下条件：

   • $\emptyset \notin \pi$
   • $\forall x\forall y\big(x,y \in \pi \land x \neq y \to x \cap y=\emptyset\big)$
   • $\bigcup \pi = A$ 则称 $\pi$ 是 $A$ 的一个划分。

• 例1：设 $A=\{a,b,c,d\}$，给定 $\pi_1,\pi_2,\pi_3,\pi_4,\pi_5,\pi_6$，判断是否为 $A$ 的划分。
  $\pi_1=\{\{a,b,c\},\{d\}\} \quad \text{是}$
  $\pi_2=\{\{a,b\},\{c\},\{d\}\} \quad \text{是}$
  $\pi_3=\{\{a\},\{a,b,c,d\}\} \quad \text{不是}$
  $\pi_4=\{\{a,b\},\{c\}\} \quad \text{不是}$
  $\pi_5=\{\emptyset,\{a,b\},\{c,d\}\} \quad \text{不是}$
  $\pi_6=\{\{a,\{a\}\},\{b,c,d\}\} \quad \text{不是}$

• 例2：求 $A=\{1,2,3\}$ 上所有的等价关系。
  解：给出 $A$ 的所有划分。 $\pi_1=\{\{1,2,3\}\}$，$\pi_1$ 对应于全域关系 $E_A$。
  $\pi_2=\{\{1\},\{2,3\}\}$，$\pi_2$ 对应等价关系 $R_2$：$R_2=\{<2,3>,<3,2>\} \cup I_A$
  $\pi_3=\{\{2\},\{1,3\}\}$，$\pi_3$ 对应等价关系 $R_3$：$R_3=\{<1,3>,<3,1>\} \cup I_A$
  $\pi_4=\{\{3\},\{1,2\}\}$，$\pi_4$ 对应等价关系 $R_4$：$R_4=\{<1,2>,<2,1>\} \cup I_A$
  $\pi_5=\{\{1\},\{2\},\{3\}\}$，$\pi_5$ 对应于恒等关系 $I_A$
  $\pi_1$ 诱导等价关系序偶：$R_1=\{<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>,<1,3>,<3,1>\}$
  $\pi_2$ 诱导等价关系序偶：$R_2=\{<1,1>,<2,2>,<3,3>,<2,3>,<3,2>\}$
  $\pi_3$ 诱导等价关系序偶：$R_3=\{<1,1>,<2,2>,<3,3>,<1,3>,<3,1>\}$
  $\pi_4$ 诱导等价关系序偶：$R_4=\{<1,1>,<2,2>,<3,3>,<1,2>,<2,1>\}$
  $\pi_5$ 诱导等价关系序偶：$R_5=\{<1,1>,<2,2>,<3,3>\}$

• 例3：设 $R$ 是 $A$ 上的自反和传递关系，定义 $A$ 上关系 $T$，使得$\forall x,y \in A,\ <x,y> \in T \Leftrightarrow <x,y> \in R \land <y,x> \in R$
  证明：$T$ 是 $A$ 上的等价关系。
  证：

  • ① 自反性：$\forall x \in A,\ \because R\text{是自反的}$
    $\therefore <x,x> \in R \land <x,x> \in R$
    $\therefore <x,x> \in T，T自反$
  • ② 对称性：$\forall x,y \in A,\ <x,y> \in T$
    $\Rightarrow <x,y> \in R \land <y,x> \in R$
    $\Rightarrow <y,x> \in R \land <x,y> \in R$
    $\therefore <y,x> \in T，T对称$
  • ③ 传递性：$\forall x,y,z \in A$ $\text{设}<x,y> \in T \Rightarrow <x,y> \in R \land <y,x> \in R$
    $<y,z> \in T \Rightarrow <y,z> \in R \land <z,y> \in R$
    $\because R\text{是传递的}$
    $\therefore <x,z> \in R \land <z,x> \in R$
    $\therefore <x,z> \in T，T是传递的$
    综上，$T$ 是 $A$ 上的等价关系。

---

2.次序关系

偏序关系

• 设 $R$ 为非空集合 $A$ 上的关系，如果 $R$ 是自反的，反对称的和传递的，则称 $R$ 为 $A$ 上的偏序关系，记作 $\preccurlyeq$。
  集合 $A$ 和 $A$ 上的偏序关系 $\preccurlyeq$ 一起称作偏序集，记作 $<A,\preccurlyeq>$。
  • 例：设 $A=\{2,3,6,12,24,36\}$，画出偏序集 $<A,\text{整除}>$ 的哈斯图。

    注：画偏序集 $<A,\preccurlyeq>$ 的哈斯图：

    1. 适当排列顶点顺序，使得$\forall x,y \in A$，若 $x\preccurlyeq y$，则将 $x$ 画在 $y$ 的下方。
    2. 对 $A$ 中两个不同元素 $x,y$，如果$x$和$y$有相应关系，就用一条线段连接 $x$ 和 $y$。

最大元和最小元

• 设 $<A,\preccurlyeq>$ 是偏序集，$B$ 是 $A$ 的任意一个子集。
  1. 若存在 $b\in B$，对任意 $x\in B$，满足 $x\preccurlyeq b$，则称 $b$ 为 $B$ 的最大元。
  2. 若存在 $b\in B$，对任意 $x\in B$，都有 $b\preccurlyeq x$，则称 $b$ 为 $B$ 的最小元。

  • 例：$A=\{2,3,6,12,24,36\}$ 的偏序集（整除关系）

    	$\{6,12\}$	$\{2,3\}$	$\{24,36\}$	$\{2,3,6,12\}$
    最大元	12	无	无	12
    最小元	6	无	无	无

极大元和极小元

• 设 $<A,\preccurlyeq>$ 是偏序集，$B$ 是 $A$ 的任意一个子集。
  1. 若存在 $b\in B$，对任意 $x\in B$，满足 $b\preccurlyeq x \Rightarrow x=b$，则称 $b$ 为 $B$ 的极大元。
  2. 若存在 $b\in B$，对任意 $x\in B$，满足 $x\preccurlyeq b \Rightarrow x=b$，则称 $b$ 为 $B$ 的极小元。
  • 例：如上$A=\{2,3,6,12,24,36\}$ 的偏序集中

    	$\{6,12\}$	$\{2,3\}$	$\{24,36\}$	$\{2,3,6,12\}$
    极大元	12	2,3	24,36	12
    极小元	6	2,3	24,36	2,3

上界和上确界

• 设 $<A,\preccurlyeq>$ 是偏序集，$B$ 是 $A$ 的任意一个子集。
  1. 若存在 $a\in A$，对任意 $x\in B$，满足 $x\preccurlyeq a$，则称 $a$ 为 $B$ 的上界。
  2. 若 $a'\in A$ 是 $B$ 的上界，且对 $B$ 的任意上界 $a$，都有 $a'\preccurlyeq a$，则称 $a'$ 为 $B$ 的上确界（最小上界）。
  • 例：如上$A=\{2,3,6,12,24,36\}$ 的偏序集中

    	$\{6,12\}$	$\{2,3\}$	$\{24,36\}$	$\{2,3,6,12\}$
    上界	12,24,36	6,12,24,36	无	12,24,36
    上确界	12	6	无	12

下界和下确界

• 设 $<A,\preccurlyeq>$ 是偏序集，$B$ 是 $A$ 的任意一个子集。
  1. 若存在 $a\in A$，对任意 $x\in B$，满足 $a\preccurlyeq x$，则称 $a$ 为 $B$ 的下界。
  2. 若 $a'\in A$ 是 $B$ 的下界，且对 $B$ 的任意下界 $a$，都有 $a\preccurlyeq a'$，则称 $a'$ 为 $B$ 的下确界（最大下界）。
  • 例：如上$A=\{2,3,6,12,24,36\}$ 的偏序集中

    	$\{6,12\}$	$\{2,3\}$	$\{24,36\}$	$\{2,3,6,12\}$
    下界	2,3,6	无	2,3,6,12	无
    下确界	6	无	12	无

拟序关系

• 设 $R$ 为非空集合 $A$ 上的关系，如果 $R$ 是反自反的、反对称的、传递的，则称 $R$ 为 $A$ 上的拟序关系。

  注：反自反+传递可以隐含反对称。

全序关系

• 拟序关系 + 集合中任意两个元素都可以比较大小。

良序关系

• 全序关系 + 集合的任意非空子集都存在最小元。