Home 数学 集合论

# 二元关系

+,−,×,÷+,-,\times,\div 等运算符号已经被我们熟知，他们都是将左右两侧的对象进行某种操作后返回一个新的结果。这种关系可以实现更抽象化的推广。

定义
令 XX 为集合，称 X×XX \times X 的子集 RR 为集合 XX 上的 二元关系 (Binary Relation)「二元关系」。
对于 x,y∈Xx, y \in X，称 xx 与 yy 之间 存在关系 R (R-related)「R 関係をもつ」，当且仅当 (x,y)∈R(x, y) \in R，记作 xRyxRy。

  • 二元关系的定义看起来很抽象，但是本质非常简单，它只是规定了哪些元素对 (x,y)(x, y) 之间可以定义关系

示例
令集合 XX，定义二元关系如下

Δ:={(x,y)∈X×X∣x=y}\Delta := \{(x, y) \in X \times X \mid x = y\}

则此时对应的二元关系

xΔy⟺x=yx \Delta y \iff x = y

不难看出，在给定 x,yx,y 之间的关系，例如 x=yx=y 之后，就可以确定子集 RR，反之亦然，这也是为什么这被称为二元关系的原因

但是实际上，这里定义的二元关系中，继承于直积的性质，是有序的。也就是说 (x,y)≠(y,x)(x, y) \neq (y, x) 一般成立，所以 xRyxRy 并不意味着 yRxyRx 成立

示例
令 X={1,2,3}X = \{1, 2, 3\}，定义二元关系如下

R:={(1,2),(2,3)}R := \{(1, 2), (2, 3)\}

此时，1R21R2 成立，但 2R12R1 不成立

# 等价关系

最具有研究意义的一类二元关系就是等价关系。我们至今已经无数次接触其中的一种：等号
然而实际上，严格的 == 有时过于严格了。在一些情况下我们更加关注对象的底层性质，只需要二者在主体结构上一致，我们就希望将二者看为同一类对象，例如初等几何中常见的 “全等” 与 “相似”

这样一类，就需要对现有的等号进行推广

定义
令 XX 为集合，RR 为 XX 上的二元关系。称 RR 为集合 XX 上的 等价关系 (Equivalence Relation)「同値関係」，当且仅当对任意 x,y,z∈Xx, y, z \in X，满足以下三个条件

  • (R) 自反性 (Reflexivity)「反射律」：xRxxRx
  • (S) 对称性 (Symmetry)「対称律」：若 xRyxRy，则 yRxyRx
  • (T) 传递性 (Transitivity)「推移律」：若 xRyxRy 且 yRzyRz，则 xRzxRz
  • 一般地，若二元关系 RR 为等价关系，则将 xRyxRy 记作 x∼yx \sim y，称为 xx 与 yy 关于 ∼\sim 等价

示例
对于 n∈Zn \in \mathbb Z，定义 nZ={nk∣k∈Z}n\mathbb Z = \{nk \mid k \in \mathbb Z\}，即 nn 的所有整数倍构成的集合
对于 x,y∈Zx,y \in \mathbb Z，定义二元关系 ~如下

x∼y⟺x−y∈nZx \sim y \iff x - y \in n\mathbb Z

则 ∼\sim 为 Z\mathbb Z 上的等价关系，并且该例中称为 模 n 同余 (Congruence Modulo n)「合同」。

证明

(R)
任取 x∈Zx \in \mathbb Z，则 x−x=0∈nZx - x = 0 \in n\mathbb Z，所以 x∼xx \sim x 成立
(S)
任取 x,y∈Zx, y \in \mathbb Z，若 x∼yx \sim y，则 x−y∈nZx - y \in n\mathbb Z，即存在 k∈Zk \in \mathbb Z，使得 x−y=nkx - y = nk。
则 y−x=−nk∈nZy - x = -nk \in n\mathbb Z，所以 y∼xy \sim x 成立
(T)
任取 x,y,z∈Zx, y, z \in \mathbb Z，若 x∼yx \sim y 且 y∼zy \sim z，则存在 k1,k2∈Zk_1, k_2 \in \mathbb Z，使得

x−y=nk1,y−z=nk2x - y = nk_1,\quad y - z = nk_2

则

x−z=(x−y)+(y−z)=nk1+nk2=n(k1+k2)∈nZx - z = (x - y) + (y - z) = nk_1 + nk_2 = n(k_1 + k_2) \in n\mathbb Z

所以 x∼zx \sim z 成立
□\square

# 等价类

通过对 “相等” 这一概念的推广，原本严格地，只能对一个对象成立的等于符号，变成了可以对一类对象成立。
也就是说可以有一类对象都被视为同一对象，这就是等价类

定义
令 ∼\sim 为集合 XX 上的等价关系，对于 x∈Xx \in X，称

[x]={y∈X∣y∼x}[x] = \{y \in X \mid y \sim x\}

为元素 xx 的 等价类 (Equivalence Class)「同値類」。

  • 等价类 [x][x] 中的各个元素 x∈[x]x \in [x] 称为该等价类的 代表元 (Representative)「代表元」

等价类这一概念非常好理解，就像是一个学校中有上千个学生。但有些时候管理需要面向班级这一对象，此时对于同属一个班级的两个学生就不再进一步区分。那么每个班级就都是一个等价类，里面的每个学生都是该等价类的代表元，也就是所谓的 “XX 班的学生”

示例
令 X={1,2,3,4,5}X = \{1, 2, 3, 4, 5\}，定义等价关系 ∼\sim 如下（等价关系的证明省略）

={(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(2,4),(4,2)}~ = \{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 3), (3, 1), (2, 4), (4, 2)\}

则 XX 上的等价类有

  • [1]={1,3}=[3][1] = \{1, 3\} = [3]
  • [2]={2,4}=[4][2] = \{2, 4\} = [4]
  • [5] = \

示例
考虑模 nn 同余关系 ∼\sim，则对于任意 a∈Za \in \mathbb Z，其等价类为

[a]={b∈Z∣b≡amodn}={a+kn∣k∈Z}[a] = \{b \in \mathbb Z \mid b \equiv a \mod n\} = \{a + kn \mid k \in \mathbb Z\}

等价类具有以下基本性质

命题
令 ∼\sim 为集合 XX 上的等价关系

  1. 对于任意 x∈Xx \in X，有 x∈[x]x \in [x]
  2. 对于任意 x,y∈Xx, y \in X，有 x∼y⟺[x]=[y]x \sim y \iff [x] = [y]
  3. 对于任意 x,y∈Xx, y \in X，有 x≁y⟺[x]∩[y]=∅x \not\sim y \iff [x] \cap [y] = \emptyset
证明

(1)
任取 x∈Xx \in X，由自反性可知 x∼xx \sim x，所以 x∈[x]x \in [x] 成立

(2)
(⇒\Rightarrow)
取 z∈[x]z \in [x]，则 z∼xz \sim x 成立
由 x∼yx \sim y 及传递性可知 z∼yz \sim y，所以 z∈[y]z \in [y]，因此 [x]⊂[y][x] \subset [y]。
同理可得 [y]⊂[x][y] \subset [x]，所以 [x]=[y][x] = [y] 成立

(⇐\Leftarrow)
假设 [x]=[y][x] = [y]，则 x∈[x]=[y]x \in [x] = [y]，所以 x∼yx \sim y 成立

(3)
考虑对偶命题 [x]∩[y]≠∅⟺x∼y[x] \cap [y] \neq \emptyset \iff x \sim y。
(⇒\Rightarrow)
根据条件取 z∈[x]∩[y]z \in [x] \cap [y]，则 z∼xz \sim x 且 z∼yz \sim y 成立
由对称性及传递性可知 x∼yx \sim y 成立

(⇐\Leftarrow)
显然此时有 x∈[x]x \in [x] 且 x∈[y]x \in [y]，所以 [x]∩[y]≠∅[x] \cap [y] \neq \emptyset 成立
□\square

# 商集

定义
令 ∼\sim 为集合 XX 上的等价关系，称等价类全体

X/∼={[x]∣x∈X}X / \sim = \{[x] \mid x \in X\}

为集合 XX 关于等价关系 ∼\sim 的 商集 (Quotient Set)「商集合」。

商集可以自然导出一个映射

π:X→X/∼,x↦[x]\pi : X \to X / \sim, \quad x \mapsto [x]

称为 商映射 (Quotient Map)「商写像」。这一定是满射的

商集的概念在初次接触时可能会感到困难，但实际上本质非常简单。
回到刚刚班级的例子中，既然我们想要管理的对象是班级，我们就希望” 忽略 “班级内部的差异
通过 同一个班等价 这样的等价关系，可以实现将上千名学生分为多个等价类：班级
那么班级全体就是商集。这里相当于是从全校的学生这一千多人中，商掉了班级内部的差异，直接得到班级这一对象
直观上商集的操作可以理解为：将原本的集合进行分组，绘制每个组各自的颜色，接下来就只看这些颜色了

由商集所划分出的组是可以完整复原的，以下结论给出保证

命题
令 ∼\sim 为集合 XX 上的等价关系，则

X=⋃[x]∈X/∼[x]X = \bigcup_{[x] \in X / \sim} [x]

证明

任取 x∈Xx \in X，则 x∈[x]x \in [x]，且 [x]∈X/∼[x] \in X / \sim，所以 x∈⋃[x]∈X/∼[x]x \in \bigcup_{[x] \in X / \sim} [x] 成立
反之，任取 y∈⋃[x]∈X/∼[x]y \in \bigcup_{[x] \in X / \sim} [x]，则存在某个等价类 [x][x]，使得 y∈[x]y \in [x]，所以 y∼xy \sim x 成立，由自反性可知 x∼xx \sim x 成立
由传递性可知 y∼xy \sim x 成立，所以 y∈Xy \in X 成立
□\square

从各个等价类中，可以得到代表元。
而商集内部是多个等价类。通过取每个等价类的代表元组成新的集合，可以得到一个最能概括原有集合的情况的缩小集合
这样的集合叫做完全代表系

定义
令 ∼\sim 为集合 XX 上的等价关系，称 S⊆XS \subseteq X 为集合 XX 关于等价关系 ∼\sim 的 完全代表系 (Complete System of Representatives)「完全集代表系」，当且仅当对任意 [x]∈X/∼[x] \in X / \sim，存在唯一 s∈Ss \in S，使得 s∈[x]s \in [x]。

命题
令 ∼\sim 为集合 XX 上的等价关系，S⊆XS \subseteq X，以下等价

  • SS 为集合 XX 关于等价关系 ∼\sim 的完全代表系
  • 限制下的商映射 π∣S:S→X/∼\pi|_S : S \to X / \sim 为双射
证明

一般来说，映射 f:A→Bf:A \to B 双射，等价于对于任意的 b∈Bb \in B，原象 f−1({b})f^{-1}(\{b\}) 存在且唯一
因此，注意到

(π∣S)−1({[x]})={s∈S∣π(s)=[x]}={s∈S∣s∈[x]}=S∩[x](\pi|_S)^{-1}(\{[x]\}) = \{ s \in S \mid \pi(s) = [x]\} = \{ s \in S \mid s \in [x]\} = S \cap [x]

命题得证
□\square