5.2.4 等价性和序关系

对于集合 $A$ ,最重要的两类二元关系是等价性和序关系.

1. 等价关系

若与集合 $A$ 有关的二元关系 $R$ 是自反、对称和传递的,则称为等价关系. 如果已知等价关系 $R$ ,那么对于 $aRb$ 也可应用记号 $a{\sim }_{R}b$ 或 $a\sim b$ ,并读作 $a$ (对于 $R$ ) 等价于 $b$ .

等价关系的例

$◼\mathbf{B}$: $A=\mathbb{Z},m\in \mathbb{N}\setminus \{0\}$ . 恰当 $a$ 和 $b$ 被 $m$ 除有相同的剩余时,有 $\{a\}{\sim }_R\{b\}$ (它们模 $m$ 同余).

$◼\mathbf{B}$: 在不同区域中的等价关系,例如,在有理数集 $\mathbb{Q}$ 中: $\frac{p_1}{q_1}=\frac{p_2}{q_2}\iff p_1{q}_2=$ $p_2{q}_1\left(p_1,p_2,q_1,q_2\text{是整数,}{q}_1,q_2\ne 0\right)$ ,这里第一个等式定义 $\mathbb{Q}$ 中的相等,而第二个等式表示 $\mathbb{Z}$ 中的相等.

$◼\mathbf{C}$: 几何图形的相似或全等.

$◼\mathbf{D}$: 命题演算的表达式的逻辑等价 (参见第 434 页 5.1.1, 6.).

2. 等价类、分拆

(1) 等价类 集合 $A$ 中每个等价关系定义 $A$ 的一个分划,即将它分为两两不相交的非空子集 (等价类).

$$\begin{array}{}\text{(5.75)}& {\left[a\right]}_R\text{:=}\left\{b\mid b\in A\wedge a{\sim }_{R}b\right\}\end{array}$$

称为 $a$ 对于 $R$ 的一个等价类. 对于等价类,下列性质成立:

$$\begin{array}{}\text{(5.76)}& {\left[a\right]}_R\ne \varnothing ,a{\sim }_{R}b\iff {\left[a\right]}_R={\left[b\right]}_R\text{,并且}a{\sim }_{R}b\iff {\left[a\right]}_R\cap {\left[b\right]}_R=\varnothing \text{.}\end{array}$$

这些等价类形成一个新的集合,即商集 $A/R$ :

$$\begin{array}{}\text{(5.77)}& A/R=\left\{{\left[a\right]}_R\mid a\in A\right\}.\end{array}$$

幂集 $\mathbb{P}\left(A\right)$ 的子集 $Z\subseteq \mathbb{P}\left(A\right)$ 称为 $A$ 的一个分拆,如果

$$\begin{array}{}\text{(5.78)}& \varnothing \notin Z,X,Y\in Z\wedge X\ne Y\Rightarrow X\cap Y=\varnothing ,\bigcup _{X\in Z}=A.\end{array}$$

(2) 分解定理 集合 $A$ 中每个等价关系 $R$ 定义 $A$ 的一个分拆 $Z$ ,即 $Z=A/R$ . 反之,集合 $A$ 的每个分拆定义 $A$ 中的一个等价关系 $R$ :

$$\begin{array}{}\text{(5.79)}& a{\sim }_{R}b\iff \mathrm{\exists }X\in Z\left(a\in X\wedge b\in X\right).\end{array}$$

集合 $A$ 中的等价关系可以看作等式的推广,在此 $A$ 的元素的 “无关重要” 的性质被忽略, 而对于某些性质没有差异的元素属于同一个等价类.

3. 次序关系

集合 $A$ 中的二元关系 $R$ 称为偏序的,如果 $R$ 是自反、反对称并且传递的. 此外,如果 $R$ 是线性的,那么 $R$ 称为线性序或链.集合 $A$ 称为关于 $R$ 有序或线性有序. 在线性有序集中任何两个元素是可比较的. 如果由问题已知次序关系 $R$ ,那么代替 $aRb$ 也可使用记号 $a{\le }_{R}b$ 或 $a\le b$ .

次序关系的例

$◼\mathbf{A}$ : 数集 $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}$ 关于通常的 $\le$ 关系是全序的.

$◼\mathbf{B}$: 子集关系也是有序的, 但仅是偏序的.

$◼\mathbf{C}$: 英语字的字典顺序是一个链.

注 如果 $Z=\{A,B\}$ 是 $\mathbb{Q}$ 的一个具有性质 $a\in A\wedge b\in B\Rightarrow a<b$ 的分拆, 那么(a, b)称为戴德金分割. 如果 $A$ 没有最大元素,而 $B$ 没有最小元素,那么这个分割唯一确定一个无理数. 除了区间套 (参见第 2 页 1.1.1.2) 外, 戴德金分割的概念是另一种引进无理数的方法.

4. 哈塞图

有限有序集可以通过哈塞图表示: 设在有限集 $A$ 上给定序关系 $\le .A$ 的元素用平面上的点表示,在此若 $a<b$ ,则点 $b\in A$ 位于点 $a\in A$ 上方. 如果没有 $c\in A$ 满足 $a<c<b$ ,则称 $a$ 和 $b$ 相邻接或是相邻成员. 于是用一个线段连接 $a$ 和 $b$ .

哈塞图是一个 “简化” 的箭头图, 其中所有的圈、箭头以及由关系的传递性产生的箭都被省略. 图 5.7 给出集合 $A=\{1,2,3,4\}$ 的可除性关系 $T$ 的箭头图,图 5.8 是其哈塞图表示.