小狍子皮皮奇

外观

等价关系与等价类

约 858 字大约 3 分钟

2025-03-14

一、等价关系

定义

等价关系是集合 AA 上的二元关系 RR，满足以下三个性质：

  1. 自反性：∀a∈A,(a,a)∈R\forall a \in A, (a, a) \in R；
  2. 对称性：若 (a,b)∈R(a, b) \in R，则 (b,a)∈R(b, a) \in R；
  3. 传递性：若 (a,b)∈R(a, b) \in R 且 (b,c)∈R(b, c) \in R，则 (a,c)∈R(a, c) \in R。

示例：

  • 实数集上的“等于”关系；
  • 整数集上的模nn同余关系（如a≡b(mod3)a \equiv b \pmod{3}）。

二、等价类

定义

设 RR 是集合 AA 上的等价关系，对任意 a∈Aa \in A，其等价类定义为：

[a]R={x∈A∣(x,a)∈R}[a]_R = \{ x \in A \mid (x, a) \in R \}

即所有与 aa 等价的元素组成的子集。

性质

  1. 覆盖性：所有等价类的并集等于 AA；
  2. 互斥性：任意两个等价类要么相等，要么不相交；
  3. 划分性：等价类的集合构成 AA 的划分。

示例：

  • 对整数集 Z\mathbb{Z} 和模3同余关系，等价类为：

    [0]3={...,−6,−3,0,3,6,...}[0]_3 = \{ ..., -6, -3, 0, 3, 6, ... \}

    [1]3={...,−5,−2,1,4,7,...}[1]_3 = \{ ..., -5, -2, 1, 4, 7, ... \}

    [2]3={...,−4,−1,2,5,8,...}[2]_3 = \{ ..., -4, -1, 2, 5, 8, ... \}

三、偏序关系

定义

偏序关系是集合 AA 上的二元关系 RR，满足：

  1. 自反性：∀a∈A,(a,a)∈R\forall a \in A, (a, a) \in R；
  2. 反对称性：若 (a,b)∈R(a, b) \in R 且 (b,a)∈R(b, a) \in R，则 a=ba = b；
  3. 传递性：若 (a,b)∈R(a, b) \in R 且 (b,c)∈R(b, c) \in R，则 (a,c)∈R(a, c) \in R。

示例：

  • 集合的包含关系（⊆\subseteq）；
  • 自然数集上的整除关系（a∣ba \mid b）；
  • 实数集上的小于等于关系（≤\leq）。

全序关系：若偏序关系中任意两元素均可比较，则称为全序关系（如实数集的≤\leq）。

四、例题

例题1：验证等价关系

题目：设集合 A={1,2,3,4}A = \{1, 2, 3, 4\}，关系 R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}R = \{(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)\}，判断 RR 是否为等价关系。

解：

  1. 自反性：所有对角元素 (1,1),(2,2),(3,3),(4,4)(1,1), (2,2), (3,3), (4,4) 均存在，满足；
  2. 对称性：所有非对角元素均对称（如 (1,2)(1,2) 与 (2,1)(2,1)），满足；
  3. 传递性：需验证所有可能的传递链：
    • (1,2)∧(2,3)  ⟹  (1,3)∈R(1,2) \land (2,3) \implies (1,3) \in R，满足；
    • 其他组合类似，均满足。
      结论：RR 是等价关系。

例题2：确定等价类

题目：在整数集 Z\mathbb{Z} 上定义关系 RR：aRb  ⟺  a2≡b2(mod7)a R b \iff a^2 \equiv b^2 \pmod{7}。求所有等价类。

解：

  1. 计算模7的平方剩余：
    • 02≡0(mod7)0^2 \equiv 0 \pmod{7}
    • 12≡1(mod7)1^2 \equiv 1 \pmod{7}
    • 22≡4(mod7)2^2 \equiv 4 \pmod{7}
    • 32≡2(mod7)3^2 \equiv 2 \pmod{7}
    • 42≡2(mod7)4^2 \equiv 2 \pmod{7}
    • 52≡4(mod7)5^2 \equiv 4 \pmod{7}
    • 62≡1(mod7)6^2 \equiv 1 \pmod{7}
  2. 等价类划分：
    • [0]R={x∣x≡0(mod7)}[0]_R = \{ x \mid x \equiv 0 \pmod{7} \}
    • [1]R={x∣x≡1 或 6(mod7)}[1]_R = \{ x \mid x \equiv 1 \text{ 或 } 6 \pmod{7} \}
    • [2]R={x∣x≡3 或 4(mod7)}[2]_R = \{ x \mid x \equiv 3 \text{ 或 } 4 \pmod{7} \}
    • [4]R={x∣x≡2 或 5(mod7)}[4]_R = \{ x \mid x \equiv 2 \text{ 或 } 5 \pmod{7} \}

例题3：偏序关系的判定

题目：集合 A={2,3,4,6,8,12}A = \{2, 3, 4, 6, 8, 12\}，关系 RR 定义为整除关系（a∣ba \mid b）。验证 RR 是否为偏序关系。

解：

  1. 自反性：每个数均能整除自身，满足；
  2. 反对称性：若 a∣ba \mid b 且 b∣ab \mid a，则 a=ba = b（如 2∣42 \mid 4 但 4∤24 \nmid 2，不违反）；
  3. 传递性：若 a∣ba \mid b 且 b∣cb \mid c，则 a∣ca \mid c（如 2∣42 \mid 4 且 4∣8  ⟹  2∣84 \mid 8 \implies 2 \mid 8）。
    结论：RR 是偏序关系，但非全序（例如 33 和 44 不可比较）。

版权归属：NateHHX

许可证：署名 4.0 国际 (CC-BY-4.0)