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

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

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

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

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

等價關係

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

存在非常多種類的關係。事實上，仔細觀察我們之前舉的例子，我們可以發現這兩種關係非常不同。在“是某人的孩子”關係中，我們可以觀察到有些人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$ 當且僅當存在某個 $k\in Z$ 使得 $a-b=kp$。證明這定義了整數集合上的等價關係。

證明

• 反身性：對於任何 $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 X$，都有 $a\in [a]$，所以 $\cup P=X$。此外，根據上述定理，此並集是互斥的。因此，$\sim$ 的等價類集合是 $X$ 的劃分。

(劃分誘導等價關係): 令 $X_{i}\,,\,i\in I$ 是 $X$ 的一個劃分。然後，在 $X$ 上定義 $\sim$ 使得 $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$ 的所有等價類的集合。為了對這個構造說出一些有趣的事情，我們需要更多的理論，這些理論還有待開發。然而，這是我們最重要的構造之一，並且在本書中將會得到很多關注。