等价关系

等价关系（equivalence relation）是集合上的一种二元关系，属于集合论基础研究内容。

定义及表示

设$R$是集合$A$上的一个二元关系，称其为一个等价关系，如果它满足以下条件：

1. 自反性：$\forall x \in A, xRx.$
2. 对称性：$\forall x,y \in A, xRy \implies yRx.$
3. 传递性：$\forall x,y,z \in A, (xRy \wedge yRz) \implies xRz.$

等价关系的符号也可写为$\sim.$

若$(x,y) \in R$，称$x$等价于$y$，记作$x \sim y.$

核（kernel）关系：对于映射$f: A \to \mathbf{B}$，称$\text{Ker} f= \{ (a_1, a_2) \in A \times A | f(a_1) = f(a_2)\}$为映射$f$的核关系。它是等价关系，我们后面将会指出，等价关系可以被核关系确定。

集合$A$上所有等价关系的全体记作$\text{Eq}(A).$

等价类

设$R$是集合$A$上的一个等价关系，$A$中等价于元素$x$的所有元素组成的集合称为$x$的等价类（equivalence class），记作$[x]_R = \bar{x} = \{ y \in A | xRy \}.$

性质

设$R$是非空集合$A$上的一个等价关系，等价类具有下列性质：

1. $\forall x \in A, \bar{x} \ne \varnothing$且$\bar{x} \subseteq A$；
2. $\forall x, y \in A$，若$xRy$, 则$\bar{x} = \bar{y}$；
3. $\forall x, y \in A$，若$(x,y) \notin R$, 则$\bar{x} \cap \bar{y} = \varnothing$；
4. $\bigcup_{x \in A} \bar{x} = A$，即$A$为$R$的所有等价类的无交并。

商集

设$R$是非空集合$A$上的一个等价关系，以$R$的所有等价类作为元素的集合称为$A$关于$R$的商集（合）（quotient set），记作$A/R$。

$$\{ \bar{a} | a \in A \}$$

例如：设$A = \{ 1, 2, 3, 4, 5, 6, 7, 8 \}$，如下定义$A$上的关系$R$：

$$R = \{ (x, y) | x, y \in A, x \equiv y~(\bmod~3) \}$$

则有如下等价类的关系：

$$\begin{array}{rcl} {[1] = [4] = [7]} & = & \{ 1, 4, 7 \} \\ {[2] = [5] = [8]} & = & \{ 2, 5, 8 \} \\ {[3] = [6] } & = & \{ 3, 6 \} \end{array}$$

所以商集为

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

划分

集合$A$的子集族$\pi$若满足：

1. 不含空集，即$\varnothing \nsubseteq \pi$；
2. 任意两元素不相交；
3. 所有元素的并等于$A$，

则称$\pi$为$A$的划分（partition），记作$\pi_R = \{ \bar{a} \}_{\bar{a} \in R}$，划分中的每一个元素称为块（block）。

这个定义和等价类的性质第四条是相似的。

例如，设$A = \{ a, b, c, d \}$，则以下的集合中只有$n_1$和$n_2$才是$A$的划分。

$$\begin{array}{rcl} n_1 & = & \{ \{ a, b, c\}, \{ d \} \} \\ n_2 & = & \{ \{ a, b\}, \{ c, d \} \} \\ n_3 & = & \{ \{ a \}, \{ a, b, c,d \} \} \\ n_4 & = & \{ \{ a, b \}, \{ c \} \} \\ n_5 & = & \{ \varnothing, \{ a, b, c\}, \{ d \} \} \\ n_6 & = & \{ \{ a, b, c\}, \{ d, \{ d \} \} \} \\ \end{array}$$

等价关系与划分一一对应定理

设$R$是集合$A$上的一个等价关系，则商集$A/R$就是$A$的一个划分，并且不同的商集将对应于不同的划分，反之，任给$A$的一个划分$\pi$，如下定义$A$上的关系$R$ $R = \{ (x, y) | x, y \in A$,$x$与$y$在$\pi$的同一划分块中$\}$ 则$R$为$A$上的等价关系。

集合范畴

在集合范畴$\mathsf{Set}$中，设有集合$A$及其上的一个等价关系$R$，有投影映射$\pi: A \to A/R$，则对任意的$\mathbf{B} \in \operatorname{Obj} \mathsf{Set}$，以及任意的集合映射$\varphi: A \to \mathbf{B}$，必存在一映射$\overline{\varphi}: A/R \to \mathbf{B}.$有

$$\overline{\varphi} \circ \pi = \varphi.$$

即下图可换

等价关系的偏序

假设$A$是非空集合，$\text{Eq}(A)$是其上等价关系之全体，按照关系作为集合的包含作为偏序形成的偏序集是完全格。

既然$\text{Eq}(A)$是一个格，上面一定诱导了交并运算，它们分别是

1. 交运算：$r_1 \land r_2 = r_1 \cap r_2.$是同时含于两个关系的最大关系集合。
2. 并运算：$r_1 \lor r_2 = r_1 \cup (r_1 \circ r_2) \cup (r_1 \circ r_2 \circ r_1) \cup \cdots.$是同时包含两个关系的最小关系集合。注意并不是简单的$r_1 \cup r_2$，这是因为后者不是一个关系。

$\text{Eq}(A)$对无限交运算是封闭的，即对一族$A$上的等价关系$\{ r_i \}_{i \in I}$有

$$\bigwedge_{i \in I} r_i = \bigcap_{i \in I} r_i.$$

因此它是对偶闭包系统。但是对并不封闭，实际上，无限并运算按照上述规定，应为

$$\bigvee_{i \in I} r_i = \bigcup \{ r_{i_0} \circ r_{i_1} \circ \cdots \circ r_{i_k}: i_0, i_1, \cdots, i_k \in I; k < +\infty \}.$$