1等价关系与集合的分类

对应视频的p1-p6

定义二元关系 $R$
等价关系
1. 反身性： $\forall a \to a R a$
2. 对称性： $a R b \Rightarrow b R a$
3. 传递性： $a R b \land b R c \Rightarrow a R c$
等价类
1. 定义： $[a]$ 表示所有与 $a$ 等价的元素的集合
2. 等价类是满足以下条件的集合：任意两个元素 $a$ 和 $b$ 都属于同一个等价类当且仅当 $a R b$
3. 公式定义: $[a] = {x \in S ∣ x R a}$
4. 类在这里的意思为:"物以群分",分类的意思,等价类就是把满足等价关系的元素归为一类.
商集: $S$ 的全体等价类构成的集合,集合 $S$ 在等价关系下的商集记作 $S / ∽$
集合的分类
1. 定义： $S$ 是一个集合，如果存在一个等价关系 $R$ 使得 $S$ 的所有元素都可以划分为等价类，则称 $S$ 为 $R$ 的分类
2. 如果非空集合 $S$ 是它的某些两两不相交的非空子集的并,则称这些子集为集合 $S$ 的一种分类(partition),其中每个子集称为集合 $S$ 的一个类(class)

若集合 $S$ 的子集族 ${S_{i} ∣ i \in I}$ 构成了S的一种分类当且仅当

$S = ⋃_{i \in I} S_{i}$
$S_{i} \cap S_{j} = \emptyset$ (i.e., $S_{i}$ and $S_{j}$ are pairwise disjoint)

集合 $S$ 的任何一种等价关系都确定了 $S$ 的一种分类。

例题

$a R b \Leftrightarrow m ∣ a - b, \forall a, b \in Z (1)$

证明1式是等价关系.也就是证明 $m ∣ a - b$ 是等价关系.

公式的含义解释: m是a与b差的因子,则说明a,b对于m同余.这两者是等价的.

下面证明这两者是等价关系.

设 A: $a \equiv b (mod m)$ , B: $m ∣ a - b$ .

$A \to B$ ,把a,b写成带余数除法的形式.

$a = k_{1} \times m + r b = k_{2} \times m + r a - b = m (k_{1} - k_{2}) \to m ∣ a - b$

必要性证明完毕,证明充分性.

$m ∣ a - b \to a - b = k \times m \to a = b + k \times m \to a mod m = (b + k \times m) mod m \to a mod m = b mod m$

qed;

证明自反性:

$a R a \Leftrightarrow m ∣ a - a$

显然成立.

证明对称性:

根据 $m ∣ x \to m ∣ - x$

那么

$m ∣ a - b \to m ∣ - (a - b) \to m ∣ b - a$

证明传递性:

$m ∣ a - b \land m ∣ b - c \to m ∣ a - c$

$a = k_{1} \times m + r b = k_{2} \times m + r c = k_{3} \times m + r \to a - c = k_{1} \times m + r - k_{3} \times m - r \to m ∣ a - c$

证明完毕

说明同余是一种等价关系.

书上又定义了什么叫做同余剩余类.

这个见书.

解:设集合 $S = {a, b, c}$

(1) , $R = {(a, b), (b, a), (a, a), b, b}$ ,因为没有 $(c, c)$ 所以不满足反身性.
(2) , $R = {(a, a), (b, b), (c, c), (a, b)}$ ,因为没有 $(b, a)$ 所以不满足对称性.
(3) , $R = {(a, a), (b, b), (c, c), (a, b), (b, a), (c, a), (c, b)}$ ,因为没有 $(a, c)$ 所以不满足传递性.

有人断言，若S的关系R有对称性和传递性，则必有反身性.这晨因为，对任意的a∈S,由对称性，如果aRb,则bRa.再由传递性，得aRa,所以R有反身性.

关键在于 $a \in S$ ，但如果 $a$ 就没有自己的关系呢?例如习题1的(1),就没有c的关系,所以不能说R有反身性. 因为不一定有 $c R b$ 这个关系.