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

我们经常希望描述一个集合中两个数学实体之间的关系。例如，如果我们查看地球上所有人的集合，我们可以定义“是...的孩子”作为一种关系。类似地，$\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$ 的所有等价类的集合。为了对这个结构做更有意思的说明，我们需要更多尚未发展的理论。但是，这是我们最重要的结构之一，在整本书中都会得到很多关注。