抽象代數/等價關係和同餘類

我們經常希望描述一個集合中兩個數學實體之間的關係。例如，如果我們檢視地球上所有人的集合，我們可以定義“是...的孩子”作為一種關係。類似地，$\geq$ 運算子在整數集上定義了一種關係。二元關係，以下簡稱關係，是針對兩個集合的元素任意選擇定義的二元命題。

形式上，關係是兩個集合 $X$ 和 $Y$ 之間的笛卡爾積的任意子集，因此，對於一個關係 $R$，$R\subseteq X\times Y$。在這種情況下，$X$ 被稱為該關係的定義域，$Y$ 被稱為其陪域。如果一個有序對 $(x,y)$ 是 $R$ 的元素（根據 $R$ 的定義，$x\in X$ 且 $y\in Y$），那麼我們說 $x$ 透過 $R$ 與 $y$ 相關。我們將使用 $R(x)$ 來表示集合

$\{y\in Y:(x,y)\in R\}$.

換句話說，$R(x)$ 用於表示在$R$ 的陪域中，某些定義域中的 $x$ 所關聯的所有元素的集合。

等價關係

為了表示兩個元素 $x$ 和 $y$ 對於關係 $R$ 相關聯，其中 $R$ 是某個笛卡爾積 $X\times X$ 的子集，我們將使用一箇中綴運算子。我們寫成 $x\sim y$ 對於某些 $x,y\in X$ 和 $(x,y)\in R$。

有很多種關係。實際上，進一步檢查我們之前提到的例子可以發現這兩種關係大不相同。在“是某人的孩子”關係中，我們可以發現有些人物 A、B，既不是 A 是 B 的孩子，也不是 B 是 A 的孩子。在 $\geq$ 運算子的情況下，我們知道對於任何兩個整數 $m,n\in Z$，$m\geq n$ 或 $n>m$ 只有一個是正確的。為了學習關係，我們必須研究更小的關係類。

特別是，我們關注關係的以下性質

• 自反性：關係 $R\subseteq X\times X$ 是自反的，如果對於所有 $a\in X$，都滿足 $a\sim a$。
• 對稱性：關係 $R\subseteq X\times X$ 是對稱的，如果對於所有的 $a,b\in X$ 都有 ${a\sim b}\implies {b\sim a}$。
• 傳遞性：關係 $R\subseteq X\times X$ 是傳遞的，如果對於所有的 $a,b,c\in X$ 都有 ${{a\sim b}\wedge {b\sim c}}\implies {a\sim c}$。

需要注意的是，在這三個性質中，我們都是對集合 $X$ 中的所有元素進行量化。

任何具有自反性、對稱性和傳遞性的關係 $R\subseteq X\times X$ 被稱為 $X$ 上的等價關係。由等價關係相關的兩個元素被稱為在等價關係下等價。我們用 $a\sim _{R}b$ 表示 $a$ 和 $b$ 在 $R$ 下等價。如果只有一個等價關係在考慮中，我們可以簡單地寫成 $a\sim b$ 。為了方便起見，我們可以簡單地說 $\sim$ 是集合 $X$ 上的等價關係，並讓其他含義隱含。

示例：對於一個固定的整數 $p$，我們在整數集合上定義一個關係 $\sim _{p}$，使得 $a\sim _{p}b$ 當且僅當 $a-b=kp$ 對某個 $k\in Z$ 成立。證明這個關係在整數集合上定義了一個等價關係。

證明

• 自反性：對於任意 $a\in X$，立即得到 $a-a=0=0p$，因此 $a\sim _{p}a$ 對於所有 $a\in G$ 成立。
• 對稱性：對於任意 $a,b\in X$，假設 $a\sim _{p}b$。那麼必須有 $a-b=kp$ 對於某個整數 $k$ 成立，並且 $b-a=(-k)p$。由於 $k$ 是一個整數，$-k$ 也必須是一個整數。因此，${a\sim _{p}b}\implies {b\sim _{p}a}$ 對於所有 $a,b\in G$ 成立。
• 傳遞性：對於任意$a,b,c\in X$，假設$a\sim _{p}b$ 和 $b\sim _{p}c$。則$a-b=k_{1}p$ 和 $b-c=k_{2}p$，對於某些整數$k_{1},k_{2}$。透過將這兩個等式加在一起，我們得到${(a-b)+(b-c)=(k_{1}p)+(k_{2}p)}\Leftrightarrow {a-c=(k_{1}+k_{2})p}$，因此$a\sim _{p}c$.

證畢。

備註：在初等數論中，我們用$a\equiv b({\text{mod }}p)$ 來表示這種關係，並說 a 與 b 模 p 同餘。

等價類

令$\sim$ 為在$X$ 上的等價關係。然後，對於任何元素$a\in X$ 我們定義$a$ 的等價類為子集$\left[a\right]\subseteq X$，由

$\left[a\right]=\left\{b\in X|a\sim b\right\}$

定理：$b\in \left[a\right]\implies \left[b\right]=\left[a\right]$

證明：假設$b\in \left[a\right]$。根據定義，$a\sim b$.

• 我們首先證明$\left[b\right]\subseteq \left[a\right]$。設$p$ 是$\left[b\right]$ 中的任意元素。那麼根據等價類的定義，$p\sim b$，並且根據等價關係的傳遞性，$p\sim a$。因此，${p\in \left[b\right]}\implies {p\in \left[a\right]}$ 並且 $\left[b\right]\subseteq \left[a\right]$。
• 我們現在證明$\left[a\right]\subseteq \left[b\right]$。設$q$ 是$\left[a\right]$ 中的任意元素。那麼根據定義$q\sim a$。根據傳遞性，$q\sim b$，所以$q\in \left[b\right]$。因此，${q\in \left[a\right]}\implies {q\in \left[b\right]}$ 並且 $\left[a\right]\subseteq \left[b\right]$。

由於$\left[a\right]\subseteq \left[b\right]$ 並且 $\left[b\right]\subseteq \left[a\right]$，我們有$\left[b\right]=\left[a\right]$。

證畢。

集合的劃分

集合 $X$ 的一個劃分是集合 $X_{i}$，$i\in I$ 的一個不相交的族，使得 $\bigcup _{i\in I}X_{i}=X$.

定理： $X$ 上的等價關係 $\sim$ 誘匯出 $X$ 的一個唯一劃分，同樣地，一個劃分也誘匯出 $X$ 上的一個唯一等價關係，使得它們是等價的。

證明：（等價關係誘匯出劃分）：設 $P$ 是 $\sim$ 的等價類的集合。那麼，由於 $a\in [a]$ 對於每個 $a\in X$ 都成立，$\cup P=X$。此外，根據上述定理，該並集是不相交的。因此，$\sim$ 的等價類集合是 $X$ 的一個劃分。

(劃分誘導等價關係): 令 $X_{i}\,,\,i\in I$ 是 $X$ 的一個劃分。那麼，定義 $\sim$ 在 $X$ 上，使得 $a\sim b$ 當且僅當 $a$ 和 $b$ 都是同一個 $X_{i}$ 的元素，對於某個 $i\in I$。 $\sim$ 的自反性和對稱性是直接的。對於傳遞性，如果 $a,b\in X_{i}$ 且 $b,c\in X_{i}$ 對於同一個 $i\in I$，我們必然有 $a,c\in X_{i}$，傳遞性隨之而來。因此，$\sim$ 是一個等價關係，其等價類為 $X_{i}\,,\,i\in I$。

最後，從 $\sim$ 中獲得 $X$ 的一個劃分 $P$，然後從 $P$ 獲得一個等價方程，顯然又回到了 $\sim$，所以 $\sim$ 和 $P$ 是等價結構。

證畢。

商集

令 $\sim$ 是集合 $X$ 上的一個等價關係。那麼，定義集合 $X/\sim$ 為 $X$ 的所有等價類的集合。為了對這個結構做更有意思的說明，我們需要更多尚未發展的理論。但是，這是我們最重要的結構之一，在整本書中都會得到很多關注。