Equivalence Relations and Their Application to Set Partitioning | 等价关系及其在集合划分中的应用

📚 Equivalence Relations and Their Application to Set Partitioning | 等价关系及其在集合划分中的应用

Equivalence relations are one of the most fundamental concepts in discrete mathematics and computer science. They formalize the idea of “sameness” or “equivalence” between objects, allowing us to group objects with shared properties and reason about them as a single unit.

等价关系是离散数学和计算机科学中最基本的概念之一。它形式化了对象之间“相同”或“等价”的思想，使我们能够将具有共同性质的对象分组，并将它们作为一个整体来推理。

---

1. What Is an Equivalence Relation? | 什么是等价关系？

Given a set A, a binary relation R on A is an equivalence relation if it satisfies three properties:

给定集合 A，A 上的二元关系 R 是等价关系，如果它满足以下三个性质：

• Reflexivity: For every x in A, x R x.

• Symmetry: For every x, y in A, if x R y then y R x.

• Transitivity: For every x, y, z in A, if x R y and y R z then x R z.

自反性：对于 A 中的每个 x，x R x 成立。

对称性：对于 A 中的任意 x 和 y，若 x R y 则 y R x。

传递性：对于 A 中的任意 x、y、z，若 x R y 且 y R z 则 x R z。

Using set notation, a relation R ⊆ A × A is an equivalence relation if the above three conditions hold. The symbol “~” is often used to denote an equivalence relation.

用集合表示，关系 R ⊆ A × A 是等价关系，当且仅当上述三个条件成立。通常用符号“~”表示等价关系。

---

2. Standard Examples | 典型例子

Example 1: Equality on any set. Two elements are related if and only if they are identical. This is the finest equivalence relation: it places every element in its own class.

例 1：任意集合上的“相等”关系。当且仅当两个元素相同时它们相关。这是最细的等价关系：每个元素都自成一类。

Example 2: Congruence modulo n on the integers. Define a R b if a – b is divisible by n. This relation is reflexive, symmetric, and transitive, and its equivalence classes are exactly the residue classes 0, 1, …, n-1.

例 2：整数上的“模 n 同余”关系。定义 a R b 当 a – b 能被 n 整除。该关系满足自反性、对称性和传递性，其等价类恰好是模 n 的剩余类 0, 1, …, n-1。

Example 3: Connectedness in an undirected graph. Two vertices are related if there is a path between them. The equivalence classes are the connected components of the graph.

例 3：无向图中顶点的连通性。如果两个顶点之间存在路径，则它们相关。等价类就是图的连通分量。

---

3. Equivalence Classes | 等价类

If ~ is an equivalence relation on A, then for each element a in A, the equivalence class of a, written [a], is the set of all elements related to a:

如果 ~ 是 A 上的等价关系，那么对 A 中每个元素 a，a 的等价类记为 [a]，它包含所有与 a 相关的元素：

[a] = { x ∈ A | x ~ a }

Every element of A belongs to exactly one equivalence class. An element of an equivalence class is called a representative; any member can serve as the class representative.

A 中每个元素恰好属于一个等价类。等价类中的元素称为代表元；类中任意成员都可以作为该类代表。

The collection of all equivalence classes of A under ~ is called the quotient set and is denoted A/~.

在 ~ 下 A 的所有等价类组成的集合称为商集，记为 A/~。

---

4. Set Partitions | 集合划分

A partition of a set A is a collection of nonempty, pairwise disjoint subsets of A whose union is exactly A. Each subset is called a block or part of the partition.

集合 A 的划分是由 A 的若干非空子集组成的集合，这些子集两两互不相交，并且它们的并集恰好等于 A。每个子集称为划分的块或部分。

There is a one-to-one correspondence between equivalence relations on A and partitions of A. Given an equivalence relation, its equivalence classes form a partition. Conversely, given any partition of A, we can define an equivalence relation by declaring two elements equivalent if and only if they belong to the same block.

A 上的等价关系与 A 的划分之间一一对应。给定一个等价关系，其等价类构成一个划分。反过来，给定 A 的任意划分，可以定义一个等价关系：当且仅当两个元素属于同一块时它们等价。

This correspondence is fundamental: it shows that partitioning a set is exactly the act of identifying objects we wish to treat as indistinguishable.

这种对应至关重要：它表明划分一个集合，恰恰就是在识别我们希望视为不可区分的对象。

---

5. The Refinement Lattice | 划分的加细格

Partitions can be ordered by refinement: a partition P is finer than Q if every block of P is contained in some block of Q. Then Q is coarser than P.

划分之间可以按加细关系排序：如果划分 P 的每一块都包含于 Q 的某一块中，则称 P 比 Q 更细，Q 比 P 更粗。

The finest partition is the one with every element as a singleton; it corresponds to the equality relation. The coarsest partition is the single block A; it corresponds to the universal relation where any two elements are equivalent.

最细的划分是每个元素都是单元素块；它对应相等关系。最粗的划分是只有一个块 A；它对应全关系，即任意两个元素都等价。

In computer science, this hierarchy appears in abstraction and type systems, where a program may be analysed at varying levels of granularity.

在计算机科学中，这种层级出现在抽象和类型系统中，程序可以在不同粒度的层次上进行分析。

---

6. Modular Arithmetic and Hashing | 模运算与哈希

Congruence modulo n partitions the integers into n equivalence classes. In programming, the operator % computes the remainder when one integer is divided by n, effectively selecting a representative from each residue class.

模 n 同余将整数划分为 n 个等价类。在编程中，运算符 % 计算一个整数除以 n 的余数，实际上是从每个剩余类中选取一个代表元。

Hash tables use an equivalence relation implicitly: keys are grouped into buckets based on a hash function. A good hash function maps equivalent keys (for example, keys with equal content) to the same bucket, while distributing different keys uniformly.

哈希表隐式地使用了等价关系：键根据哈希函数被分到不同的桶中。好的哈希函数将相等的键（例如内容相同的键）映射到同一桶，同时将不同的键均匀分布。

Modular arithmetic also underlies cyclic data structures, pseudo-random number generation, and finite field arithmetic used in cryptography.

模运算还是循环数据结构、伪随机数生成以及密码学中有限域算术的基础。

---

7. Graph Connectivity and Union-Find | 图的连通性与并查集

In an undirected graph, the relation “there exists a path between vertices” is an equivalence relation. Its equivalence classes are the connected components. This allows problems like “are two vertices connected?” to be reduced to checking whether they lie in the same class.

在无向图中，关系“顶点之间存在一条路径”是等价关系。其等价类就是连通分量。这允许将“两个顶点是否连通”这类问题简化为检查它们是否属于同一类。

The union-find (disjoint-set) data structure maintains dynamic equivalence classes under an operation that merges two classes. It supports two operations: find(x) which returns the representative of the class containing x, and union(x, y) which merges the classes of x and y.

并查集（不相交集合）数据结构支持在合并两个类的操作下维护动态等价类。它支持两种操作：find(x) 返回 x 所在类的代表元，union(x, y) 合并 x 和 y 所在的类。

With path compression and union by rank, both operations run in nearly constant amortised time, making union-find the workhorse for Kruskal’s minimum spanning tree algorithm and many graph-processing applications.

通过路径压缩和按秩合并，两种操作的均摊时间接近常数，使并查集成为 Kruskal 最小生成树算法以及许多图处理应用的核心工具。

---

8. Database Normalisation | 数据库规范化

Relational database design uses equivalence relations to identify redundant data. A functional dependency X → Y in a relation table induces an equivalence relation on tuples: two tuples are equivalent if they agree on all attributes in X.

关系数据库设计使用等价关系识别冗余数据。关系表中的函数依赖 X → Y 在元组上诱导出一个等价关系：两个元组在 X 的所有属性上取值相同则它们等价。

Normalisation decomposes a table into smaller tables so that each table represents one equivalence class of dependencies. This reduces anomalies and storage waste, ensuring that every fact is stored exactly once.

规范化将表分解为更小的表，使每个表表示依赖的一个等价类。这减少了异常和存储浪费，确保每个事实只存储一次。

The process of normalisation is essentially finding a partition of the columns that respects the functional dependencies and yields lossless-join decomposition.

规范化过程本质上是寻找列的一个划分，该划分尊重函数依赖并产生无损连接分解。

---

9. Finite Automata and State Equivalence | 有限自动机与状态等价

In the theory of computation, two states of a finite automaton are equivalent if they produce identical future behaviour for every input string. This relation is an equivalence relation on the set of states.

在计算理论中，如果有限自动机的两个状态对每个输入字符串产生相同的未来行为，则它们等价。该关系是状态集合上的等价关系。

Minimisation of a DFA proceeds by iteratively refining a partition of states, merging states that are indistinguishable. The resulting minimal DFA has one state for each equivalence class.

DFA 的最小化通过迭代细化状态划分，合并不可区分的状态。得到的极小 DFA 中，每个等价类对应一个状态。

Myhill–Nerode theorem states that a language is regular if and only if the equivalence relation induced by the language on strings has finitely many classes. This ties equivalence relations directly to the expressive power of finite automata.

Myhill–Nerode 定理指出，一个语言是正则语言当且仅当该语言在字符串上诱导的等价关系只有有限多个等价类。这直接将等价关系与有限自动机的表达能力联系起来。

---

10. Concurrency and Parallel Partitioning | 并发与并行划分

Equivalence relations are used to model observational equivalence in concurrent systems: two processes are equivalent if, from the outside, they cannot be distinguished by any sequence of observations.

等价关系用于建模并发系统中的观察等价：如果从外部不能通过任何观察序列区分两个进程，则它们等价。

In parallel computing, domain decomposition partitions data into equivalence classes to be processed by different workers. The partition must balance load while minimising communication between classes.

在并行计算中，域分解将数据划分为等价类，由不同的工作节点处理。划分必须平衡负载并最小化类之间的通信。

Formal verification techniques such as model checking rely on quotienting a state space by an equivalence relation such as bisimulation, dramatically reducing the number of states to explore.

形式化验证技术（如模型检测）依赖于通过等价关系（如互模拟）对状态空间取商，从而大幅减少需要探索的状态数量。

---

11. Implementing Partitions: Union-Find Details | 实现划分：并查集细节

A practical implementation of dynamic partitions uses a forest of rooted trees. Each tree represents one equivalence class, and the root is the representative.

动态划分的一种实用实现使用有根树森林。每棵树表示一个等价类，根就是代表元。

find(x): Climb from x to the root, applying path compression so that future finds are faster.

find(x)：从 x 向上爬到根，并应用路径压缩，使后续查找更快。

union(x, y): Find the roots of x and y; make one root point to the other, always attaching the smaller tree under the larger tree (union by size).

union(x, y)：找到 x 和 y 的根；将一个根指向另一个根，并始终将较小的树连接到较大的树下面（按大小合并）。

Both optimisations make the amortised inverse-Ackermann complexity O(α(n)), which is effectively constant for all practical input sizes.

两种优化使均摊复杂度达到逆 Ackermann 函数 O(α(n))，在实际输入规模下可视为常数。

---

12. Conclusion | 总结

Equivalence relations provide a unifying mathematical framework for treating objects as indistinguishable when appropriate. Through their tight link to set partitions, they enable efficient data structures, cleaner database schemas, and deeper insights into automata and concurrency.

等价关系提供了一个统一的数学框架，使我们在适当的时候可以将对象视为不可区分。通过与集合划分的紧密联系，它支撑起高效的数据结构、更简洁的数据库模式，并为自动机与并发系统提供了深刻洞见。

Mastering this concept equips a computer scientist with a powerful tool for abstraction and system design.

掌握这一概念，能够让计算机科学工作者获得一种强大的抽象与系统设计工具。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）