离散数学 课件 3.9 等价关系

CHAPTER03集合与关系3.9等价关系集合元素的精确分类本节内容概览等价关系的概念•关系的分类回顾：自反、对称与传递性•等价关系的严格定义与生活范例•数学实例：整数集合上的同余关系证明等价类•等价类的数学定义与直观理解•典型实例：模n剩余类集合的构造•核心性质：等价类的“不交性”与“完全覆盖性”商集•商集的定义：所有等价类构成的集合•商集与集合划分的等价性证明•总结：从“关系”到“划分”的数学桥梁3.9.1等价关系的概念关系的分类回顾本节开始学习三个非常重要的关系：等价关系、相容关系、偏序关系。它们都是基于关系的五种基本性质（自反、对称、反对称、传递）组合而成的。设R为定义在集合A上的关系：等价关系(Equivalence)若R是自反的、对称的、传递的，

则称R为A上的等价关系。相容关系(Compatibility)若R是自反的、对称的，

则称R为A上的相容关系。偏序关系(PartialOrder)若R是自反的、反对称的、传递的，

则称R为A上的偏序关系。定义3.34：等价关系的定义定义内容：设R为定义在集合A上的一个关系，若R是自反的、对称的、传递的，则R称为等价关系(EquivalentRelation)。核心目标将集合中的元素，依据某种共同属性进行分类，使其归属于互不相交的等价类。这一过程可实现元素的精确分类与复杂系统的简化建模，是解决复杂分类问题的重要数学工具。生活实例1.新生注册分组：按学号区间段分组，定义关系R为“学号在同一段”，该关系满足自反、对称与传递性。2.无线通信网络：基站间的通信兼容性构成等价关系。利用此特性可将基站划分为等价类，用于优化网络拓扑结构，提升通信效率。典型范例：等价关系与非等价关系是等价关系•同姓关系

一个人肯定和自己同姓（自反），如果A和B同姓，那么B和A也同姓（对称），如果A和B同姓，B和C同姓，那么A和C也同姓（传递）。•等于关系

满足a=a（自反），若a=b则b=a（对称），若a=b且b=c则a=c（传递）。•同色关系

在一个包含各种颜色球的集合中，关系aSb成立，当且仅当球a和球b的颜色完全相同。不是等价关系•朋友关系

通常不满足传递性。例如，A是B的朋友，B是C的朋友，但A和C之间不一定认识，更不一定互为朋友。•包含关系

集合论中的包含关系不满足对称性。例如，集合A是集合B的子集（A⊆B），但这并不意味着集合B也是集合A的子集。例题3.40：以4为模的同余关系问题：设集合A={0,4,8,1,5,9,2}，定义关系R={<x,y>|4|(x−y)}（即x与y模4同余）。请：(1)写出关系R的序偶集合；(2)描述关系图与关系矩阵的特征；(3)证明R是等价关系。1.序偶集合R{<0,0>,<0,4>,<0,8>,<4,0>,<4,4>,<4,8>,

<8,0>,<8,4>,<8,8>,<1,1>,<1,5>,<1,9>,

<5,1>,<5,5>,<5,9>,<9,1>,<9,5>,<9,9>,

<2,2>}2.关系图&矩阵•同余类划分：

余数0:{0,4,8}|余数1:{1,5,9}|余数2:{2}•关系图特征：

由三个互不连通的完全子图(clique)构成。•关系矩阵特征：

为分块对角矩阵，每块是对应同余类的全1子矩阵。3.等价关系验证✅自反性：

对任意x∈A，x-x=0，4|0，故<x,x>∈R。✅对称性：

若4|(x-y)，则4|(y-x)，故若<x,y>∈R，则<y,x>∈R。✅传递性：

若4|(x-y)且4|(y-z)，则4|(x-z)，故若<x,y>、<y,z>∈R，则<x,z>∈R。例题3.40：关系图与关系矩阵关系图结构特征该关系图可划分为三个互不连通的子图：•第一子图：节点0,4,8两两互相连接，形成一个完全子图。•第二子图：节点1,5,9两两互相连接，形成一个完全子图。•孤立点：节点2仅存在自环，与其他所有节点均无边相连。关系矩阵MR矩阵被划分为互不干扰的对角块，对应关系图中的独立连通分量。性质与最终结论✓自反性：矩阵主对角线元素全为1，满足自反性定义。✓对称性：矩阵沿主对角线对称，满足对称性定义。✓传递性：图中任意两点间存在路径则必有直达边，满足传递性。结论：关系R是等价关系例题3.41：证明同余关系是等价关系问题：设n为正整数，定义整数集合Z上的以n为模的同余关系R={<x,y>|n|(x−y)}，证明R是一个等价关系。1.自反性(Reflexivity)对任意整数x∈Z，因为x−x=0。

而正整数n整除0恒成立(n|0)，

故<x,x>∈R。因此R满足自反性。2.对称性(Symmetry)若<x,y>∈R，则n|(x−y)。

由于(x−y)=−(y−x)，故n|(y−x)。

从而<y,x>∈R。因此R满足对称性。3.传递性(Transitivity)若<x,y>∈R且<y,z>∈R，则n|(x−y)且n|(y−z)。

因为(x−z)=(x−y)+(y−z)，故n|(x−z)。

从而<x,z>∈R。因此R满足传递性。结论：由自反性、对称性和传递性可知，R是整数集合Z上的一个等价关系。3.9.2等价类定义3.35：等价类的定义设R为集合A上的等价关系，对任何a∈A，集合[a]R={x|x∈A，aRx}称为元素a关于R的等价类(EquivalenceClass)，也称由元素a生成的R等价类。核心前提只有关系具备自反性、对称性、传递性的等价关系，才具有等价类。这是讨论的基础。集合本质一个等价类本质上是一个集合，它包含集合A中所有与元素a具有相同性质或关系的元素。集合划分非空集合A上的一个等价关系R，可将集合A划分为若干个互不相交的等价类，且这些类的并集就是A。等价类实例同姓关系在人类集合中，定义“同姓”关系，那么所有姓张的人构成一个等价类，所有姓王的人构成另一个，依此类推。例如集合：{张},{王},{李}以n为模的同余关系整数集Z按除以n的余数被划分成n个互不相交的等价类，即“模n剩余类”。典型的剩余类结构如下：•[0]={...,-3n,-2n,-n,0,n,2n,3n,...}|[1]={...,-3n+1,...,n+1,...}•...•[n-1]={...,-3n-1,...,-1,n-1,2n-1,...}图示：集合划分与等价类结构例题3.42：求解等价类问题：在集合A={0,1,2,4,5,8,9}上定义的以4为模的同余关系中，求所有元素的等价类。[0]ₐ=[4]ₐ=[8]ₐ{0,4,8}除以4，余数均为0[1]ₐ=[5]ₐ=[9]ₐ{1,5,9}除以4，余数均为1[2]ₐ{2}除以4，余数为2观察：这三个子集互不相交，且它们的并集就是集合A。在关系图或关系矩阵中，可以非常直观地观察到这些互不相交的等价类划分。等价类的性质（定理3.19&3.20）定理3.19：等价类的判定对于任意元素a,b∈A，有aRb当且仅当[a]R=[b]R。(两个元素有关系，当且仅当它们的等价类完全相同)1.自含性(Reflexivity)必有x∈[x]R，且[x]R≠∅。

由等价关系的“自反性”直接推导得出。2.代表元任意性(Arbitrariness)若y∈[x]R，则必有[y]R=[x]R。

等价类中的任何一个元素都可以作为该类的“代表”。3.互不相交性(Disjointness)若y∉[x]R，则必有[x]R∩[y]R=∅。

任意两个不同的等价类之间没有公共元素。4.全域覆盖性(Coverage)所有元素的等价类的并集等于集合X。

即⋃(x∈X)[x]R=X，无遗漏。例题3.43：从关系图求等价类▍问题描述设集合A={a,b,c,d}上的二元关系R定义为：

R={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>}

请根据关系图的特征，求关系R的所有等价类。▍关系图特征分析•元素a与b之间存在双向边，且各自均有自环，构成一个连通子图。

•元素c与d之间存在双向边，且各自均有自环，构成另一个连通子图。

•两个子图之间没有任何边相连，相互独立。▍等价类求解结论根据连通子图划分规则，R是一个等价关系，集合A上的元素被划分为两个互不相交的等价类：

•第一类（由a,b生成）：

[a]R=[b]R={a,b}

•第二类（由c,d生成）：

[c]R=[d]R={c,d}3.9.3商集定义3.36：商集的定义设R为集合A上的等价关系，其等价类集合{[a]ₐ|a∈A}称作A关于R的商集(QuotientSet)，记作A/R。即：A/R={[a]ₐ|a∈A}集合属性商集本质上是一个集合。它的构成元素，不是原集合A中的元素，而是等价关系R在A上产生的各个互不相交的等价类。集合划分商集A/R是集合A的一个划分。这一划分是由等价关系R诱导产生的，体现了集合A被“切割”为互不相交的子集的过程。一一对应集合A上的所有等价关系，与集合A的所有划分之间，存在着一种严格的一一对应的数学关系。商集与划分思考：如何求一个集合上有多少个等价关系？答案：只要求出此集合有多少个不同的划分即可。（等价关系与集合划分一一对应）例题3.44：设集合A={0,1,2,4,5,8,9}•在以4为模的同余关系R中，商集是：

A/R={[0]R,[1]R,[2]R}={{0,4,8},{1,5,9},{2}}•在以3为模的同余关系S中，商集是：

A/S={[0]S,[1]S,[2]S}={{0,9},{1,4},{2,5,8}}例题3.45：求所有等价关系问题：设集合A={1,2,3}，试求集合A上所有的等价关系，并写出它们对应的商集。01划分S₁={{1,2,3}}对应关系：全域关系R₁=A×A|商集：A/R₁={{1,2,3}}02划分S₂={{2},{1,3}}对应关系：({1,3}×{1,3})∪({2}×{2})|商集：A/R₂={{2},{1,3}}03划分S₃={{3},{1,2}}对应关系：({1,2}×{1,2})∪({3}×{3})|商集：A/R₃={{3},{1,2}}04划分S₄={{1},{2,3}}对应关系：({2,3}×{2,3})∪({1}×{1})|商集：A/R₄={{1},{2,3}}05划分S₅={{1},{2},{3}}对应关系：恒等关系R₅=I_A|商集：A/R₅={{1},{2},{3}}结论：集合A={1,2,3}上共有5个不同的等价关系。重要定理：等价关系与划分的一一对应定理3.21集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。💡证明思路：只需证明商集满足划分的三个核心条件：覆盖性、非空性和互不相交性。定理3.22集合A的一个划分，唯一确定了A的元素间的一个等价关系。💡证明思路：定义关系R为“两个元素在同一个分块中”，验证该关系满足自反性、对称性和传递性。定理3.23设R₁和R₂为非空集合A上的等价关系，则R₁=R₂，当且仅当A/R₁=A/R₂。💡证明思路：两个等价关系相等，当且仅当它们所诱导的集合划分完全一致。这揭示了两者之间严格的一一对应关系。本节核心概念回顾等价关系一种满足自反性、对称性、传递性的二元关系。它是集合论中用于对元素进行分类的基础工具。等价类包含与元素a等价的所有元素的