等价关系

等价关系与划分

若 $R$ 是自反的、对称的、传递的，则称 $R$ 是等价关系。设 $R$ 是一个等价关系，若 $x R y$ ，则称 $x$ 与 $y$ 是等价的，记作 $x \sim y$ .

等价类

设 $R$ 是 $A$ 上的等价关系， $x \in A$ ，则

[x]_{R} = {y | y \in A \land x R y}

\forall x \in A, [x]_{R} \neq \emptyset, [x]_{R} \subseteq A

\forall x, y \in A, [x]_{R} \cap [y]_{R} = {\begin{cases} \emptyset & x ≁ y \\ [x]_{R} & x \sim y \end{cases}

⋃ {[x]_{R} | x \in A} = A

商集与划分

A / R = {[x]_{R} | x \in A}

实例： $A = {1, 2, \dots 8}$ ，关于模 $3$ 同余的等价关系 $R$ 的商集 $A / R = {[1]_{R}, [2]_{R}, [3]_{R}} = {{1, 4, 7}, {2, 5, 8}, {3, 6}}$

若 $A$ 的子集族 $π (π \subseteq P (A))$ 满足

$\emptyset \notin π$
$⋃ π = A$ 则称 $π$ 是 $A$ 的一个覆盖。

若 $A$ 的子集族 $π$ 是一个覆盖，且

$\forall x \forall y (x, y \in π l a n d x \neq y \to x \cap y = \emptyset)$ 则称 $π$ 是 $A$ 的一个划分， $π$ 的元素称为 $A$ 的划分块。

集合 $A$ 上的一个等价关系 $R$ , 决定了 $A$ 的一个划分，该划分就是商集 $A / R$

集合 $A$ 的一个划分,确定 $A$ 的元素间的一个等价关系