等价关系

Equivalence relation

满足自反、对称和传递性的关系。

领域: 逻辑与基础
条目类型: 定义

形式陈述

集合 $A$ 上的关系 $\sim$ 称为等价关系，当且仅当对所有 $x,y,z\in A$ ：

x\sim x \quad\text{（自反）},

x\sim y\Rightarrow y\sim x \quad\text{（对称）},

x\sim y\land y\sim z\Rightarrow x\sim z \quad\text{（传递）}.

元素 $x$ 的等价类为

[x]=\{y\in A:y\sim x\}.

三条公理保证任意两个等价类要么相等、要么不交，并且

A=\bigcup_{x\in A}[x].

因此等价类组成 $A$ 的一个划分。反过来，给定任何划分 $\mathcal P$ ，定义

x\sim_{\mathcal P}y \quad\Longleftrightarrow\quad x,y\text{ 属于同一块},

便得到等价关系。两种构造互逆。

直觉

等价关系把“忽略某些差异后视为相同”变成严格分类。自反性保证每个对象属于某类，对称性消除方向，传递性阻止类别沿局部相似链相互重叠。

普通相似度往往缺少传递性。两个对象分别都与第三个“很接近”，不表示它们彼此也足够接近；这类关系不能直接形成商对象。

例子与边界

整数模 $n$ 同余、向量相差非零标量倍、字符串在变量改名下的 $\alpha$ -等价，都是等价关系。

实数上的

x\sim y\iff |x-y|<1

自反且对称，却不传递： $0\sim0.75$ 、 $0.75\sim1.5$ ，但 $0\not\sim1.5$ 。因此“按距离小于阈值分组”可能产生重叠簇，而不是等价类。

偏序的对称部分通常只剩相等；“ $\le$ ”本身不对称，不是等价关系。图的可达性在无向图中是等价关系，在有向图中仅是预序；若改为相互可达，才得到强连通分量的等价关系。

定义商集上的函数时，必须证明代表元无关：

x\sim y\Rightarrow f(x)=f(y).

否则公式只定义在代表元上，不能下降到等价类。

推论与应用

商集把每个等价类视为一个新对象。群的正规子群、环的理想、拓扑中的同伦、自动机最小化中的不可区分性，都用等价关系压缩冗余表示。

等价关系与集合划分在结构上等价。若关系只满足自反与传递，得到的是预序；再按

x\equiv y\iff x\preceq y\land y\preceq x

取商，才能得到真正的偏序。

参考资料

Paul R. Halmos, Naive Set Theory, Dover, 2017, §7.
Daniel J. Velleman, How to Prove It, 3rd ed., Cambridge University Press, 2019, Chapter 8.
Thomas Jech, Set Theory, 3rd millennium ed., Springer, 2003, Chapter 1.

关系图谱47 个相邻概念 · 4 类关系

正在载入交互图谱…

前置三跳
前置二跳
前置一跳
当前条目
后续一跳
后续二跳
后续三跳

文字版关系按与当前条目的最短距离分组

分类位置

上位 / 更一般

关系定义

下位 / 直接特例

暂未标注直接特例。

类型化关系

被这些条目使用

限定层次等价

集合划分定义

Myhill–Nerode 定理

“它是等价关系，并且对右拼接稳定：若 $x\equiv Ly$，则对任意 $w$ 都有 $xw\equiv Lyw$。等价地，定义语言对前缀 $x$ 的左商（也称前缀残余）”

有限自动机最小化

“给定完整 DFA $M=(Q,\Sigma,\delta,q 0,F)$，在状态上定义等价关系”

同余闭包算法

“等式与未解释函数理论 EUF 的地面输入由等式 $s=t$ 和不等式 $s\ne t$ 的合取组成；函数符号除相等输入必须产生相等输出外没有额外语义。对输入中出现的有限项集合 $S$，同余关…”

强连通分量算法

“可达性的自反性与传递性，加上定义中的对称写法，使 $\sim$ 成为等价关系；它的极大等价类称为强连通分量（SCC）。分解由图唯一确定，与算法的搜索次序无关。”

后缀自动机

“非初态对应由等价关系划分出的子串 $endpos$ 类： [ x\sim {\mathrm{end}}y \quad\Longleftrightarrow\quad \operatornam…”

“α 等价是 λ 项上的等价关系：两个项若只在绑定变量标签上不同，而每个使用出现仍指向对应的绑定器，就记为 $t\equiv \alpha u$。以下默认变量名供应无限，因此每个有限项总能选到…”

“其中积分为 Lebesgue 积分；$L^p(X,\mu)$ 是全体满足 $ f p<\infty$ 的可测函数按"几乎处处相等"这一等价关系取商所得的空间。对 $p=\infty$，”

最小充分统计量

“对 $x,y\in\mathcal X +$，用不产生 $0/0$ 的交叉乘积定义等价关系：”

“两个状态词停顿等价，若它们的块标记序列 $B 0B 1B 2\cdots$ 相同，而每块重复次数可以不同。该关系在固定原子命题观察下是等价关系。”

“向量空间的非零向量按标量倍等价，经商拓扑得到射影空间。仿射图表把某坐标非零的区域识别为仿射空间，代数几何用齐次多项式描述射影簇；计算机视觉则用射影变换统一透视与无穷远点。”

“满射 $q$ 的纤维定义等价关系”

2 处

“商构造通过消除冗余表示产生模算术、商群、商环、商空间和语法等价类。等价关系与划分一一对应；函数若在每个等价类上取同值，便唯一下降到商集。语法的 α 等价等应用，都是在这副集合论骨架上增加相容…”

“给定 $A$ 上的等价关系 $\sim$，元素 $a$ 的等价类为 $$ [a]={x\in A:x\sim a}, $$ 商集为 $A/{\sim}={[a]:a\in A}$；这里的集合…”

“是等价关系，$g$ 的等价类正是 $gH$。因此全体左陪集构成 $G$ 的一个分划。右陪集也给出分划；两类陪集的个数相同，因为 $gH\mapsto Hg^{ 1}$ 给出双射。这个共同的个…”

“模同余是 $\mathbb Z$ 上的等价关系：自反性来自 $n\mid 0$，对称性来自 $n\mid(a b)$ 蕴含 $n\mid(b a)$，传递性来自整除对和的封闭。它的等价类称为…”

“等价关系与划分一一对应，第二类 Stirling 数计数固定块数的划分。所有划分按细化关系组成格，聚类、商集、并查集维护的连通分量都可用这一语言。若块带有顺序或标签，应转用满射计数或多项式系…”

环的局部化

“设 $R$ 为交换含幺环，$S\subseteq R$ 是一个子集，并且含 $1$ 且对乘法封闭，即 $s,t\in S$ 蕴含 $st\in S$。在 $R\times S$ 上定义等价关系”

“若存在包含 $(s,t)$ 的互模拟，称 $s,t$ bisimilar，记 $s\sim t$。在固定标号转移系统上，bisimilarity 是等价关系，可据此把状态空间商掉。”

“一般关系没有默认的反射性、对称性、传递性或函数性。等价关系加入反射、对称与传递，用等价类表达分类；偏序改用反对称性，表达可能存在不可比较元素的层级。”