等价关系(英语:Equivalence relation),也称为同值关系,是集合上的一种特殊的
二元关系,它同时具有自反性、对称性和传递性。等价关系在数学中有广泛的应用,例如整数集上的同余、欧氏几何中的等量以及平凡的
相等关系。通过等价关系可以将
集合划分为不相交的等价类,从而简化问题的复杂度。在
软件测试中,等价关系可用于选择测试用例。
定义
设R是集合A上的一个二元关系,若R满足以下条件:
自反性:∀a∈A, (a,a)∈R
对称性:∀a,b∈A, (a,b)∈R ∧ a≠b =\u003e (b,a)∈R
传递性:∀a,b,c∈A, (a,b)∈R ∧ (b,c)∈R =\u003e (a,c)∈R
则称R是定义在A上的一个等价关系。若(a,b)∈R,则称a等价于b,记作a~b。等价关系通常用符号~表示。
应用
等价关系可以用于划分集合,形成等价类,并通过等价类简化问题。
例一:
同班同学关系、同乡关系是等价关系。
平面几何中三角形间的相似关系、
全等关系都是等价关系。
平面几何中直线间的平行关系是等价关系。
例二:
设A={1,4,7},定义A上的关系R如下:
R={(a,b)|a,b∈A ∧ a≡b
MOD 3}
其中a≡b mod 3表示a与b模3同余,即a除以3的
余数与b除以3的余数
相等。R为A上的等价关系。另外,若f是从A到B的函数,定义A上的关系R:aRb当且仅当f(a)=f(b),则R也是A上的等价关系。
例三:
设R为定义在集合A上的一个关系,若R是自反的、对称的和传递的,则称R为等价关系。设R为集合A上的等价关系,对任何a∈A,集合[a]={b|(a,b)∈R}称为元素a形成的等价类,其等价类集合{[a]|a∈A},称作A关于R的商集,记作A/R。
定理3.7.1设给定非空集合A上等价关系R,对于a,b∈A,有aRb当且仅当[a]=[b]。定理3.7.2集合A上的等价关系R,确定了A的一个划分,该划分就是商集A/R。定理3.7.3集合A的一个划分,确定A的元素间的一个等价关系。
事例
等价关系的例子
例如,设A={1,2,...,8},定义A上的关系R如下:
xRy ⇔ ∀x,y∈A, x≡y (mod 3)
其中x≡y (mod 3)表示x与y模3同余。例子有1R4, 2R5, 3R6。R为A上的等价关系。
不是等价关系的关系的例子
并非所有的
二元关系都是等价关系。例如,
实数之间的"≥"关系满足自反性和传递性,但不满足对称性。例如,7 ≥ 5 无法推出 5 ≥ 7,因此"≥"不是等价关系。它是一种
全序关系。另一个
反例是比较两个数中哪个较大的关系,它既没有自反性(任何一个数不能比自身为较大)也没有对称性(如果m\u003en,则不能有n\u003em)。