等价关系

8
一、等价关系
定理5: 设R是A上的二元关系,设R′=tsr(R)是R的自反对称 传递闭包,那么 (a) R′是A上的等价关系,叫做R诱导的等价关系； (b) R′是包含R的最小等价关系。 证明： r(R)是自反的，所以sr(R)是自反的，对称的，所以 tsr(R)是自反的，对称的，传递的，即R’=tsr(R)是A上 的等价关系。 设R”是包含R的任意等价关系，即R⊆R”，因为R”是 自反的，所以r(R)⊆r(R”)=R”；因为R”是对称的，所以 sr(R)⊆s(R”)=R”;又因为R”是传递的，所以 tsr(R)⊆t(R”)=R”，即R”包含tsr(R)。
14
二、划分
定理9：设π是非空集合A上的划分,R是A上的等价关系,那么,
π诱导出R当且仅当R诱导出π。 证：（必要性）假设π诱导出R,R诱导出π′ 设a是A的任一元素,并设B和B′分别是π和π′的块, 使a∈B和B′，那么对任一b b∈B iff ［a］R =［b］R iff b∈B′ 所以,B=B′。 因为a是A的任一元素而π和π′都是A的覆盖,故π=π′。
若是划分，则必是覆盖；若是覆盖，则不一定是划分。
②设A是非空集合, ρ(A)-{∅ } 是A的一个覆盖,而不是A的划分,除非A是单元素集合。
11
二、划分
定理6 : 设A是非空集合,R是A上的等价关系。R的等价类集合 {［a］R ｜a∈A}是A的划分。 由上面定理2，3可得出。 定义5：设R是非空集合A上的等价关系,称划分{［a］R｜a∈A} 定理2：设R是集合A上的等价关系,则对所有a,b∈A,或者 ［a］=［b］,或者［a］∩［b］= ∅ 为商集A/R,也叫A模R。
10
二、划分
例4：①A={a,b,c}，则 S={{a,b},{b,c}}, Q={{a},{a,b},{a,c}}, D={{a},{b,c}}, G={{a,b,c}}, E={{a},{b},{c}}, F={{a},{a,c}}, 划分 最小划分 最大划分 既不是覆盖，也不是划分 覆盖 覆盖

3、传递性；
<x,y>∈R x mod 3=y mod 3 <y,z>∈R y mod 3=z mod 3
∴ x mod 3=z mod 3，从而<x,z> ∈R。
续上例Z上的模3同余关系
……～ -3 ～ 0 ～3 ～6 ～9 ～12 ～…… ……～-2 ～1 ～4 ～7 ～10 ～13 ～…… ……～-1 ～2 ～5 ～8 ～11 ～14 ～…… 即是：{3n}中的各元素相互等价， {3n+1}中的各元素相互等价， {3n+2}中的各元素相互等价。
[4]R＝{4,5 } ＝ [5]R
2
3
等价关系例1
5
[6]R＝{6}
例2：整数上的模3同余关系R
[0]R＝{……,-3,0,3,6,9,…… } ＝ [3]R ＝ [6]R ＝ …… ={3n | n∈Z}=3Z [1]R＝{……,-2,1,4,7,10,… } ＝ [4]R ＝ [7]R ＝ …… ={3n+1 | n∈Z}=3Z+1 [2]R＝{……,-1,2,5,8,11,…… } ＝ [5]R ＝ [8]R ＝ …… ={3n+2 | n∈Z}=3Z+2
划分块
设 A 为非空集合，若存在 A 的一个子集簇 CP(A)满足： 1. C； 2. 对于A的任意子集x, yC，若x y，则x y = ； 3. C = A。 则称C为A的一个划分，C中的元素称为 划分块。
等价关系和划分的对应
设A为非空集合，则： 1. 2. 设 R 为 A上的任意一个等价关系，则 设C是A的任意一个划分，则定义RC 商集A/R是A的一个划分； = {<x, y> | x, yA x, y属于C的同一划分块}， 则RC是等价关系。

例：A={52张扑克牌}， R1={<a，b>｜a与b同花，a，b是扑克}， R2={<a，b>｜a与b同点，a，b是扑克}， 即R1是同花关系， R2是同点关系，R1和R2都是等价关系。 R1把A分为四类同花类， R2把A分为13类同点类。 例：A={0，1，2，3，4，5}， R={<0，0>，<1，1>，<2，2>，<3，3>，<1，2>，<1， 3>，<2，1>，<2，3>，<3，1>，<3，2>，<4，4>，<4， 5>，<5，4>，<5，5>}，R把A分成了三个等价类： {0}，{1，2，3}，{4，5}。
2、定理3-10.1：设给定集合A上的等价关系R，对 于a，bA有aRbiff[a]R=[b]R。 证明：假定[a]R=[b]R，因为a[a]R，故a[b]R，即 aRb。 反之，若aRb，设c[a]RaRcbRcc[b]R 即[a]R[b]R 同理，若aRb，设c[b]RbRcaRcc[a]R 即[b]R[a]R 由此证得若aRb，则[a]R=[b]R。
三、商集 1、定义3-10.3：集合A上的等价关系R，其等价类 的集合{[a]R|aA}称为A关于R的商集，记作A/R。 如例题1中商集T/R={[1]R，[2]R}，例题3中商集 I/R={[0]R，[1]R，[2]R} 等价关系R把A的元素分为若干类，各类之间没 有公共元素。确定的R是对集合A进行的一个划分。
二、等价类 1、定义3-10.2：设R为集合A上的等价关系，对任何 aA，集合[a]R={x|xA，aRx}称为元素a形成的R 等价类。 显然，等价类[a]R非空，因为a[a]R。 例题3：设I是整数集，R是模3关系， 即R={(x，y)|xy(mod3)，x，yI}，确定由I的元素 所产生的等价类。 解：由I的元素所产生的等价类是 [0]R={…，-6，-3，0，3，6，…} [1]R={…，-5，-2，1，4，7，…} [2]R={…，-4，-1，2，5，8，…}

集合的等价关系与等势等价关系和等势是集合论中重要的概念，它们在研究集合的性质和关系时具有重要的应用。

本文将介绍等价关系和等势的定义、性质以及它们在数学中的具体应用。

一、等价关系的定义与性质等价关系是集合上的一种二元关系，满足自反性、对称性和传递性三个条件。

具体地说，对于集合A上的等价关系R，对任意元素x，都有自反性xRx；对于任意元素x和y，若xRy，则yRx，即对称性；对于任意元素x、y和z，若xRy且yRz，则xRz，即传递性。

等价关系将集合A划分成若干个非空子集，这些子集称为等价类。

等价类具有以下性质：1）等价类之间两两不相交；2）集合A中的每个元素都属于某个等价类；3）两个元素属于同一个等价类，当且仅当它们之间存在等价关系。

二、等势的定义与性质等势是集合之间的一种对应关系，表示两个集合具有相同的基数（元素个数）。

具体地说，对于集合A和B，若存在一个双射（一一对应）f: A→B，则称A与B等势。

等势具有以下性质：1）等势关系满足自反性、对称性和传递性；2）若集合A与B等势，集合B与C等势，则集合A与C等势；3）对于有限集合，等势关系等价于具有相同的基数；4）对于无限集合，存在真子集与原集合等势。

三、等价关系与等势的具体应用1. 等价关系的应用等价关系在数学中有广泛的应用。

在抽象代数中，等价关系可以用来定义商集，从而构造模结构；在拓扑学中，等价关系可以用来定义同伦等概念；在图论中，等价关系可以用来定义等价类，揭示图的结构等。

2. 等势的应用等势是研究集合基数的重要工具。

等势关系可以用来比较集合的大小，并且可以用来证明两个集合等势的方法有很多，例如通过构造双射、利用Cantor-Bernstein定理等。

除了应用于集合论和数学基础理论之外，等价关系和等势还在其他学科中起到重要的作用。

在计算机科学中，等价关系和等势广泛应用于数据库、图像处理和人工智能等领域。

在社会科学中，等价关系和等势常常用于建立分类系统、分析关系网络等。