# Equivalence Relation 等價關係
在數學中我們常常看到各式各樣的分類與關係，而集合論中有個比較一般化的情況，稱之為等價關係。
- Def: equivalence relation, class
- Def: partition
- Thm: equivalence and partition
## Equivalence relation 等價關係
### 定義: 等價關係、等價類
::: info
**Def: equivalence relation**
一個關係$\sim$在一個集合$S$上被叫做等價關係若且唯若滿足以下三條性質:
**1. 自反性 reflexive**
$$ \forall s \in S[s \sim s]$$
**2. 對稱性 symmetric**
$$ \forall x,y \in S[ \ x \sim y \Rightarrow y \sim x]$$
**3. 傳遞性 transitive**
$$ \forall x,y,z \in S[x \sim y \land y \sim z \Rightarrow x \sim z]$$
**Def: equivalence class**
$S$上一個元素$s$的等價類是收集所有跟$s$等價的元素，記作$[s]$
也就是
$$[s] := \{t: t \sim s\} \subset S$$
注意到由於 $s \sim s$，所以 $[s]非空$
:::
由「等價關係」這個字本身的長相我們就大概能猜到它是什麼樣的一種概念，基本上，可以把它看作是一種相等或相似，也就是說在這個關係下，如果$a \sim b$那我們其實可以(不精確的)把$a$跟$b$看成是差不多一樣的東西，而且這樣我們就說$b$在$a$的等價類中: $b \in [a]$
#### 小練習
檢查以下的關係是否為等價關係，如果是，試著寫出它的等價類
1.$在\mathbb{Z}上，x \sim y : \frac{x-y}{2} \in \mathbb{Z}$
2.$在\mathbb{R}^2上，(x_1, y_1) \sim (x_2, y_2) : x_1y_1=x_2y_2$
3.$S$是一集合，$\sim$ 在 $\wp(S)$上， $X \sim Y : X\cap S=Y\cap S$
<font color="red"> 4.</font> 在$\mathbb{Z} \times (\mathbb{Z}-\{0\})$上，$(a,b) \sim (c,d): ad=bc$
5.在$\mathbb{Z}-\{0\}$上，$m \sim n : mn>0$
p.s. 第四點其實就是我們建構有理數的一步
### 定義: 分割
:::info
**Def: partition**
一個集合$S$的分割是指一組互斥子集，且這些互斥集合的聯集正好是$S$
也就是
$$S \neq \phi , \exists I \neq \phi[(\forall i\in I, S_i \subseteq S) \land (\forall a,b \in I \land a \neq b, S_a \cap S_b = \phi) \land ( \bigcup_{i \in I} S_i = S)]$$
:::
分割，顧名思義可以看成把集合切成一塊塊，而這幾塊彼此都不會交會，就想像是一把很鋒利的刀子在切蛋糕，切完之後每一塊都不會有屑屑掉到其他塊上面。

接下來是關於等價關係一個很重要的性質
### 定理 1.2.1
:::danger
$$S是一非空集，則S上的每一種等價關係都對應了一種S的分割$$
:::
在證明這個定理之前先介紹幾個小引理
:::success
**Lemma 1.2.1:**
若$a \sim b$，則$[a]=[b]$
:::
**Proof:**
$令x \in [a] \Rightarrow x \sim a, \because x \sim a \land a \sim b, \therefore x \sim b \Rightarrow x \in [b]$
$\therefore [a] \subseteq [b]$
另一邊類似，所以得證$\square$
:::success
**Lemma 1.2.2:**
$a,b$相異，則$[a] \cap [b] = \emptyset \lor [a]=[b]$
:::
**Proof:**
考慮$[a] \cap [b] \neq \emptyset$的情況，那麼$\exists x[x \in [a] \cap [b]] \Rightarrow x \sim a \land x \sim b \Rightarrow a \sim x \land x \sim b \Rightarrow a \sim b$
由$Lemma 1.2.1$知$[a]=[b] \square$
接下來是定理的證明

---
**Proof:**
##### (1) 等價關係(類) $\rightarrow$ 分割
設$\sim$ 是 $S$上的一個等價關係，而等價類為$S_1, S_2, S_3, ...$
由$Lemma \ 1.2.2$知$S_i, S_j$ 互斥 $\forall i,j$
**欲證:** $S=S_1\cup S_2\cup S_3\cup...$
**想法:** $S \subseteq S_1\cup S_2\cup S_3\cup... \ \land \ S_1\cup S_2\cup S_3\cup... \subseteq S$
**Step1**: let $x \in S_1\cup S_2\cup S_3\cup... \Rightarrow x \in S_i$ for some $i$
又根據等價類的定義，$x \in S$，所以 $S_1\cup S_2\cup S_3\cup...\ \subseteq S$
**Step2**: let $x \in S, \because x \sim x, x \in [x] \Rightarrow x \in S_k$ for some $k$ (by definition)
$\therefore S \subseteq S_1\cup S_2\cup S_3\cup...$
故得證$\square$
##### (2) 分割 $\rightarrow$ 等價關係
若$P=\{S_1, S_2, S_3,...\}$是$S$的一組分割，那我們可以直接引導出一個等價關係如下:
$$x \sim y \Leftrightarrow \exists S_i \in P[x \in S_i \land y \in S_i] $$
可以試著證明它滿足三個性質$\square$

---
定理$1.2.1$被稱為等價關係基本定理