矩阵理论1 集合上的等价关系（equivalence relations on a set S）

定义

对于一个集合S, 如果集合$\mathcal{E}\subset S\times S$满足以下条件

1. 自反性: 对于$\forall s\in S,都有(s,s)\in \mathcal{E}$
2. 对称性: $(s,t)\in \mathcal{E}\iff (t,s)\in \mathcal{E}$
3. 传递性: 如果$(s,t)\in \mathcal{E}$ 且$(t,u)\in \mathcal{E}$, 则$(s,u)\in \mathcal{E}$

如果$(s,t)\in \mathcal{E}$, 我们可以将这种情况记为$s\sim t$.
给定$t\in S$, 我们将*$t$在等价关系$\mathcal{E}$下的等价类*记为$[t]$, 其中$[t]\subset S$ ,且有
[t]={s∈S∣s∼t}[t] = \{s\in S|s\sim t\} [t]={s∈S∣s∼t}
显然$t\in [t]$.
反过来, 如果S的某个子集$[t]\subset S$刚好是某个元素$t\in S$在等价关系$\mathcal{E}$下的等价类, 我们则称t是该集合/该等价类的表示(representative).
易知对于集合S上的某个特定的等价关系$\mathcal{E}$, 任意S中的元素都具有一个等价类. 我们将所有元素的等价类构成的集合记为$[\mathcal{E}]$, 即
$$[\mathcal{E}]=\{[s]|s\in S\}$$

例子

ex1. 若S指地球上所有的动物个体构成的集合, 设$\mathcal{E}\subset S\times S$, 其中
$$(s_1,s_2)\in \mathcal{E}\iff s_1和s_2是同一个物种$$
易知$\mathcal{E}$满足

1. 自反性
2. 对称性
3. 传递性

所以$\mathcal{E}$为S上的一个等价关系

ex2. 令S={A,B,C}S = \{A,B,C\}S={A,B,C}, 设$\mathcal{E}\subset S\times S$, 其中
E={{A,A},{B,B},{C,C},{A,B},{B,A}}\mathcal{E} = \{\{A,A\}, \{B,B\}, \{C,C\}, \{A,B\}, \{B,A\}\} E={{A,A},{B,B},{C,C},{A,B},{B,A}}
易知$\mathcal{E}$满足

1. 自反性
2. 对称性
3. 传递性

所以$\mathcal{E}$为S上的一个等价关系
而且, [A]=[B]={A,B},[C]={C}[A] =[B]= \{A, B\}, [C] = \{C\}[A]=[B]={A,B},[C]={C}

注意到例题2中, 在集合S上的等价关系$\mathcal{E}$下, 所有元素的等价类构成的集合$[\mathcal{E}]$形成了集合S的一个分划(partition).
这是一个很普遍的结论, 而且, 集合S的任一分划均可视为某种等价关系$\mathcal{E}$下的等价类集合$[\mathcal{E}]$. 也就是下面的命题.

命题

如果$\mathcal{E}\subset S\times S$是集合S上的一个等价关系, 则$[\mathcal{E}]$是集合S的一个分划. 反过来, 若P是集合S的一个分划, 则必然存在某个集合S上的等价关系$\mathcal{E}\subset S\times S$, 使得$[\mathcal{E}]=P$