4. 关系、等价类与次序

学习目标与定义

识别等价关系和偏序，证明与划分的对应关系，并检查商集运算的良定义性。$X$ 上的关系 $R$ 是 $X\times X$ 的子集；当 $(x,y)\in R$ 时写 $xRy$。

若对每个 $x$ 有 $xRx$，关系是自反的；若 $xRy$ 蕴含 $yRx$，它是对称的；若 $xRy$ 和 $yRz$ 蕴含 $xRz$，它是传递的。等价关系满足这三个条件。$x$ 的等价类为 $[x]=\{y\in X:yRx\}$，$X/R$ 是这些类组成的集合。代表元是用于命名类的元素，不是类本身。

偏序是自反、反对称且传递的。反对称意味着 $xRy$ 和 $yRx$ 同时成立会迫使 $x=y$，而不是说每一对元素都不满足对称性。全序还要求每一对元素都可比较。包含关系是 $\mathcal P(X)$ 上的偏序，但通常不是全序。

定理：等价关系与划分

等价关系的各类非空、覆盖 $X$，且任意两类相等或不相交。反过来，任何由非空不相交块组成的划分，都可通过属于同一块来定义等价关系。

证明。 自反性使每个 $x$ 属于 $[x]$，证明非空性和覆盖性。若 $z\in[x]\cap[y]$，则 $zRx$ 且 $zRy$，由对称性和传递性得 $xRy$。若 $w\in[x]$，则 $wRx$ 和 $xRy$，故 $wRy$，所以 $[x]\subseteq[y]$。交换 $x,y$ 得到相等。反过来，每点属于唯一的块；同属一块具有自反性和对称性。若 $x,y$ 同属一块而 $y,z$ 同属另一块，两块有交集，故相同，从而具有传递性。

商集运算与例题

对整数 $m\ge2$，若 $m\mid(a-b)$，定义 $a\sim b$。整除性验证自反、对称和传递：差分别是 $0$、$m$ 的倍数的相反数及倍数之和。由整数除法，商集的类为 $[0],\ldots,[m-1]$。

定义加法 $[a]+[b]=[a+b]$ 和乘法 $[a][b]=[ab]$。要使定义良好，替换任一代表元都不能改变所得类。若 $a-a'=ms$、$b-b'=mt$，则 $(a+b)-(a'+b')=m(s+t)$，并且

$$ab-a'b'=(a-a')b+a'(b-b')=m(sb+a't).$$

所以两种运算都良定义。相反，试图定义 $[a]\le[b]$ 当且仅当 $a\le b$ 会失败：模三时 $[0]=[3]$，但 $0\le1$、$3\nleq1$ 对同一对类给出冲突结果。

次序例题。 在正整数上，整除关系是偏序。若 $a\mid b$ 且 $b\mid a$，写 $b=ka,a=\ell b$，其中 $k,\ell$ 为正整数；于是 $k\ell=1$，故 $a=b$。它不是全序，因为既无 $2\mid3$，也无 $3\mid2$。

分层练习

1. 基础。 在 $\mathbb Z$ 上，当 $a-b$ 为偶数时定义 $aRb$。证明它是等价关系并列出各类。
2. 核心。 在 $\mathbb R$ 上，以 $|a-b|\le1$ 定义的 $aRb$ 是否为等价关系？逐一检查各性质。
3. 核心。 在模五整数中解 $[2][x]=[1]$，并解释答案为何不依赖代表元的选择。
4. 证明。 对等价关系，证明 $[x]=[y]$ 当且仅当 $xRy$。

详解

1. 零为偶数；偶数差的相反数仍为偶数；两个偶数差之和仍为偶数。这分别证明自反、对称和传递性。两类分别是偶整数 $[0]$ 和奇整数 $[1]$。
2. 由于 $|a-a|=0$，它是自反的；由于绝对差对称，它是对称的。它不传递：$0R1$、$1R2$，但不满足 $0R2$。故不是等价关系。
3. $2\cdot3=6\equiv1\pmod5$，所以 $[x]=[3]$ 是解。若 $2x\equiv1$，乘以 $3$ 得 $x\equiv3$，证明唯一性。上面已证明类的乘法良定义，所以把 $x$ 改变五的倍数不会改变乘积类。
4. 若类相等，自反性给出 $x\in[x]=[y]$，即 $xRy$。若 $xRy$，则 $x\in[x]$ 且 $x\in[y]$，所以两类相交，由划分定理它们相等。

总结与术语

划分将集合分成不相交的非空块；等价类是关系诱导的一个块。若代表元的所有选择都给出相同输出，商集规则是良定义的。偏序允许不可比较的元素，全序不允许。逐一检查定义性质，未经代表元检验，不要将公式转移到类上。