抽象代数/等价关系和同余类

我们经常希望描述一个集合中的两个数学实体之间的关系。例如，如果我们要查看地球上所有人的集合，我们可以将“是某人的孩子”定义为一种关系。类似地，$\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$ 的所有等价类的集合。为了对这个构造说出一些有趣的事情，我们需要更多的理论，这些理论还有待开发。然而，这是我们最重要的构造之一，并且在本书中将会得到很多关注。