等价关系与集合的分类18页PPT

[x]R=[y]R 证明： 证明： 若已知xRy，对任意a∈[x]R， 若已知 ，对任意 ∈ 由等价类定义xRa，由R的对称、 的对称、 由等价类定义 ， 的对称 传递性得到yRa，所以 ∈[y]R， 传递性得到 ，所以a∈ 同理可证[x] 故[x]R⊆[y]R。同理可证 R⊆[y]R 所以[x] 所以 R=[y]R。 反之， 反之，若[x]R=[y]R，
(4) 平面上直线集合 上的平行关 平面上直线集合L上的平行关 上的平行 系是等价关系 L上的垂直关系不是等价关系 上的垂直 上的垂直关系不是等价关系 (5) 集合的包含于关系非等价关系 集合的包含于 包含于关系非等价关系
整数集合Z上的关系 例 整数集合 上的关系 R={<x,y>|x,y∈Z∧x≡y(mod 3)}， ∈ ∧ ， 其中x≡y(mod 3)的含义就是 的含义就是x-y 其中 的含义就是 可以被3整除 验证R为等价关系 整除。 可以被 整除。验证 为等价关系 证明： 对任意x∈ ， 可以被3整除 对任意 ∈Z，x-x可以被 整除 可以被 所以<x,x>∈R，故R是自反的。 ∈ ， 所以 是自反的。
< 1, 4 > , < 1, 7 > , < 2, 5 > , < 2, 8 > , < 3, 6 > , < 4,1 > , < 4, 7 > , < 5, 2 > , < 5, 8 > , < 6, 3 > , < 7,1 > , < 7, 4 > , < 8, 2 > , < 8, 5 > }
对于全域关系，集合X上有 上有1个 对于全域关系，集合 上有 个 等价类，这个等价类就是X本身。 等价类，这个等价类就是 本身。 本身 对任一等价关系，集合X上每一元 对任一等价关系，集合 上每一元 生成的等价类必不为空， 素x生成的等价类必不为空， 生成的等价类必不为空 因为恒有x∈ 因为恒有 ∈[x]R。 集合X上不同元素的等价类可相同 集合 上不同元素的等价类可相同 是集合X上的等价关系 定理 设R是集合 上的等价关系 是集合 对任意x, ∈ ， 对任意 y∈X，xRy当且仅当 当且仅当

• • • • •
例：'={{1},{2},{3,4}}，={{1,2}, {3,4}} 因为{1}{1,2}，{2}{1,2}， {3,4}{3,4}， 所以'细分 若 ' 细分 , 则与它们对应的二元关系 R' 和R它们之间有何联系？
• (1)若 '细分 ,则与它们对应的二元关系 R'和R满足R'R。 • 证明：对任意(a,b)R‘，目标是(a,b)R • (2)若R'R，是否有'细分？ • 证明：对任意S‘’,目标是S • S‘S • 定理 2.17：设',是A的划分,它们确定A 上的等价关系分别为R,R',则'细分当 且仅当R'R。
• 三、等价关系与划分 • 定义 2.14：设R是A上的等价关系, 对于 每个aA,与a等价的元素全体所组成的集 合称为由 a 生成的关于 R 的等价类 , 记为 [a]R, 即[a]R={x|xA,xRa},a称为该等价类 的代表元。 • 在不会引起误解的情况下 , 可把 [a]R 简记 为[a]。 • 定义 2.15 ：设 R 是 A 上的一个等价关系 , 关于R的等价类全体所组成的集合族称为 A 上 关 于 R 的 商 集 , 记 为 A/R, 即 A/R={[a]|aA}。
• • • •
定理 2.13：设R是A上的等价关系, 则 (1)对任一aA,有a[a]; (2)若aRb, 则[a]=[b]; (3)对a,bA, 如果(a,b)R,则[a]∩[b]=;
(4) [a] A
aA
此定理的(1)说明A中每个元素所产生的等价类是非空的 定理的 (2)、 (3)说明：互相等价的元素属于同一个等价类， 而不等价的元素其所对应的等价类之间没有公共元素 定理的(4)说明：A上等价关系R所对应的等价类的并就等于 A. 由此定理说明 A 上等价关系 R 所对应的等价类集合是 A 的 一个划分。 该定理告诉我们，给定一个等价关系就唯一确定一个划分。

2
前页 前后页 前目页录 前返页回
例1 设S是一个非空集合，S 的所有子集组成的
集合记为P(S) ．因为对S 的任意两个子集A，B ，A B 或A B 有且仅有一个成立，所以集合的包含关系“ ”
是P(S ) 的一个关系．进一步讨论可以发，这个关系还
具有下面两条性质：
(1) 反身性，即对S 的任一子集 A，有A A；
a bmod m (读作“a 同余于b , 模m ”)．整数的同余关
系及其性质是初等数论的基础
8
前页 前后页 前目页录 前返页回
二、集合的分类
定义1.1.4 如果非空集合S 表成若干个两两不 相交的非空子集的并, 则称这些子集为集合S 的一种
分类 (partition),其中每个子集称为一个类 (class).如果
6
前页 前后页 前目页录 前返页回
例４ 易知, 三角形的全等,相似, 数域上n 阶 方阵的相等,相似等都是等价关系, 而例1,例2, 例3所述的关系都不是等价关系．
7
前页 前后页 前目页录 前返页回
例５ 设m 是正整数, 在整数集 中, 规定
ab m | a b,a,b 则 (1)对任意整数 a ,
前页 前后页 前目页录 前返页回
定义1.1.2 设 是S 非空集合的一个关系, 如 果 满足
(E1) 反身性, 即对任意的a S, 有aa ； (E2)对称性, 即若ab , 则 ba ； (E3) 传递性, 即若ab ,且 bc,则ac． 则 称是S 的一个等价关系(equivalence relation), 并且如果ab ,则称 a 等价于 b ,记作 a ~ b ．
13
前页 前后页 前目页录 前返页回

集合的等价关系与等价类等价关系是集合论中一种重要的关系概念，在数学、计算机科学等领域都有广泛的应用。

本文将介绍等价关系的概念、性质以及等价类的相关内容。

一、等价关系的定义在集合论中，等价关系是指具有自反性、对称性和传递性的二元关系。

具体来说，设A为一个集合，R为A上的一个二元关系，则R为A上的等价关系，当且仅当满足以下三个条件：1. 自反性：对于A中的任意元素x，都有xRx；2. 对称性：对于A中的任意元素x和y，若xRy，则yRx；3. 传递性：对于A中的任意元素x、y、z，若xRy且yRz，则xRz。

二、等价类的概念与表示如果R是集合A上的一个等价关系，对于A中的每个元素x，称[x]R为x关于等价关系R的等价类。

等价类是满足对称性和传递性的非空子集合。

一个集合A可以被等价关系R分割为若干个互不相交的等价类。

等价类的表示方式有多种，常见的有：1. 列举法：将等价类中的元素一一列举出来，用大括号{}括起来表示。

例如，对于集合A = {1, 2, 3, 4, 5}，若等价关系R={(1, 1), (2, 2), (1, 3), (3, 1), (2, 3), (3, 2)}，则有两个等价类：[1]R = {1, 3}和[2]R = {2}。

2. 描述法：用一个条件表达式来描述等价类中的元素。

例如，对于集合A = {1, 2, 3, 4, 5}，若等价关系R={(1, 1), (2, 2), (1, 3), (3, 1), (2, 3), (3, 2)}，则等价类可以表示为[1]R = {x | (x, 1)∈R}和[2]R = {x | (x,2)∈R}。

三、等价关系的性质等价关系具有以下性质：1. 自反性：等价关系R必定满足自反性，即对于A中的每个元素x，都有xRx。

2. 对称性：若等价关系R满足对称性，即对于A中的任意元素x和y，若xRy，则yRx。

3. 传递性：若等价关系R满足传递性，即对于A中的任意元素x、y、z，若xRy且yRz，则xRz。

2
对R求三种闭包共有6种顺序，问每种顺序的运算结 果是否一定为等价关系？
不一定。 由于对称闭包不一定保持关系的传递性，因此先求 传递闭包后求对称闭包得到的关系不一定是等价关系 例 A={1,2,3}，A上的关系R={<1,2>,<3,2>}
str(R)=IA{<1,2>,<2,1>,<3,2>,<2,3>} 显然str(R)不是等价关系 用闭包运算去构造等价关系时，传递闭包运算应该 放在对称闭包运算的后面
3
例 设AN，R={<x, y>|x, yA∧x≡y (mod 3)} 为A上的 关系，其中x≡y (mod 3)叫做x与y模3相等，其含义为x 除以3的余数与y除以3的余数相等。证明R为A上的等 价关系。 证明:
xA，有x≡x (mod 3)，即<x, x>R，所以R是自 反的。
x,yA，若x≡y (mod 3)，则有y≡x (mod 3)。所以 R是对称的。
π1={ { a，b，c }，{ d } } π2={ { a，b }，{ c }，{ d } } π3={ { a }，{ a，b，c，d } } π4={ { a，b }，{ c } } π5={ ，{ a，b }，{ c，d } } π6={ { a，{ a }}，{ b，c，d } } 其中π1,π2是A的划分，π3,π4,π5,π6不是A的划分
例 集 合 A={1,2,…,8} 上 的 等 价 关 系 R={<x, y>|x, yA∧x≡y（mod 3）}等价类是{1, 4, 7}、{2, 5, 8}、{3, 6}。
所以A在R下的商集为{{1, 4, 7}, {2, 5, 8}, {3, 6}}。 A在R下的商集也可写成{[1], [2], [3]}。 整数集Z在模n等价关系下的商集是 {{nz+i|zZ} | i=0,1,…n-1} 或{[0], [1], ..., [n-1]}

• 四、划分的积与和 • 1.划分的积 • 定理 2.16：设R1和R2是A上的等价关系,则 R1∩R2是A上的等价关系。 • 定义 2.16：设R1和R2是A上的等价关系, 由 R1和 R2确定的A的划分分别为 1和2,A上 的等价关系 R1∩R2 所确定的 A 的划分 , 称为 1与2划分的积,记为1· 2。 • 定义 2.17：设和'是A的划分, 若'的每 一块包含在的一块中, 称'细分,或称' 加细。
• 定理 2.18：设1,2是A的划分,则 • (1)1· 2细分1与2。 • (2) 设 ' 是 A 的划分 , 若 ' 细分 1 与 2 , 则 ' 细分 1· 2。 • 证明：(1)设1和2分别对应的A上关系是R1和R2， 则 1· 2对应的关系为R1∩R2。 • (2) 设'对应A上关系是R'，1和2分别对应的A 上关系是 R1 和 R2，则 1 · 2 对应的关系为 R1∩R2。
• A={1,2},画出A的幂集P(A)上的包含关系 的哈斯图 • P(A)={,{1},{2},{1,2}}
• 例A={2, 3, 6, 12, 24, 36}, 画出偏序集(A, /) 的哈斯图。
• 设A上的小于等于关系≦,A={1, 2, 3, 4, 5, 6},画出偏序集(A,≦)的哈斯图。
• 2．Hasse图 • 偏序集 (A,R) 可以通过图形表示 , 该图叫哈 斯图。是对关系图的简化。 • (1)由于偏序关系是自反的，即对每个元素a, 都有aRa，因此在图上省去自环 • (2) 由于偏序关系是传递的，即若有 aRb, bRc则必有aRc,因此省去a与c之间的连线 • (3)对于aRb,规定b在 a的上方，则可省去箭 头。 • 这样的图称为哈斯图。

( ( x) ( y)) ( ( x )) ( ( y ))
( )( x )( )( y )
从而，G G . 是G到G的同构映射。
例8 当A是一个平面上的所有三角形组成的集合时，
三角形的全等关系“ ”， 相似关系“~”， 等面积关系“”
但 2 | 4 2与4在同一类， 4不能整除2 4与2不在同一类中，
导出矛盾。
对于R5：aR5b (a, b) 1,R5不能将Z分类，
(2,6) 1 2与6在同一类，(6,3) 1 6与3在同一类， 但(2,3) 1 2与3不在同一类，这是不可能的。
R 定义 设R是非空集合A的一个关系，如果 满足
第一章
重点和难点：
等价关系和集合的分类是密切相关的两个重要概念，教材中 一些较复杂的理论常需用到它们。本节的重点和难点在于熟练 掌握利用已知的集合分类作出相应的等价关系及利用已知的等 价关系作出该集合相应的分类方法。
一、集合的分类
0，2， 4， 例1 设整数集Z {， 4， 3， 2， 1，1， 3， }，并令
Ⅱ对称性： .
若a与b同在一类，那么，b与a同在一类， 所以，a ~ b b ~ a
Ⅲ.传递性：
若a与b同在一类， 同在一类， b与c 那么，a与c同在一类， 所以，a ~ b, b ~ c a ~ c
定理2 集合A的元间的一个等价关系 决定A的一个分类 ~ . 证明： 利用给定的等价关系来 做一个 A的分类.
可知，R1就是例 中的“除以 同余”的关系 1 4 .
例5 在M 2 ( R )中，定义关系
R 2： b) 对，若秩a 秩b; (a,b) 错，若秩a 秩b. (a,

反证设a∈[b]R ，a∈[c]R,且[b]R ≠ [c]R，则bRa,cRa成立， 所以有aRc,所以bRc，即[b]R ＝ [c]R 所以A/R是A上对应于R的一个划分。
定理3 集合A的一个划分确定A的元素间 的一个等价关系。
证明：
设集合A的一个划分S＝｛S1,S2…Sm｝，现定义一个关系： aRb当且仅当a,b在同一个分块中。则R是一个等价关系。
主要内容
1
等价关系与等价类的基本概念
2
等价关系的基本性质
3
商集与集合的划分
一、定义
定义1:设R为定义在集合A上的一个关系，若 R是自反的，对称的和传递的，则称R为集 合A上的等价关系。
例如
平面上三角形集合中，三角形的相似关 系；
同学集合A={a,b,c,d,e,f,g},A中的关系 R：住在同一宿舍；
。2020年11月11日星期三2020/11/112020/11/112020/11/11
15、会当凌绝顶，一览众山小。2020年11月2020/11/112020/11/112020/11/1111/11/2020
16、如果一个人不知道他要驶向哪头，那么任何风都不是顺风。2020/11/112020/11/11November 11, 2020
二元关系R是自反的。
对称性（ symmetric ）
定义：设R为定义在集合A上的二元关系，如果 对于每个x，y∈A，每当<x,y>∈R，就有 <y,x>∈R，则称集合A上关系R是对称的。
传递性（ transitive ）
定义:设R为定义在集合A上的二元关系， 如果对于任意x，y，z∈A， 每当<x,y> ∈ R且<y,z> ∈R，就有 <x,z> ∈ R，称关系R在A上是传递的。

传递性 设R是一个等价关系，若x,yA，且<x,y> R ， 则称x等价于y。 显然，若R是等价关系，则R=r(R)=s(R)=t(R)
第3 页

例3-10.1

在全体中国人所组成的集合上定义的“同姓” 关系 是等价关系。 三角形的相似关系 非空集合上的完全关系 是等价关系。 是等价关系。 “朋友”关系，“父子”关系 不是等价关系。 整数集合上的“小于”关系 不是等价关系。
第5 页
关系图
2 1 6
5

9
3


从图中可知： （1）R中每个结点都有自回路，即R是自反的； （2）R中两个结点x和y，若有从x指向y的边，则 有y指向x的边，即R是对称的； （3）若有x指向y的边，y指向z的边，则有x指向z 的边，即R是传递的。 由（1）、（2）和（3）知，R是等价关系。
1 2
6
4 7 9 5 10 14 [1]R=[5]R=[9]R={1,5,9} [2]R=[6]R=[10]R=[14]R={2,6,10,14} [3]R=[7]R={3,7} [4]R={4}
3
第14页
2、等价类性质的证明
R是A上等价关系，任意a,b,c∈A
⑴同一个等价类中的元素，彼此有等价关系R。
即任意x,y∈[z]R，必有<x,y>∈R。 证明：


任取x,y∈[z]R，由等价类定义得，
<z,x>∈R，<z,y>∈R，
由R的对称性得，<x,z>∈R，
又由R的传递性得，<x,y>∈R。 所以，同一个等价类中的元素，彼此有等价关系R。
第15页
பைடு நூலகம்

17
划分(举例,续)
~Ai Ai
18
等价关系与划分是一一对应的
定理28: 设A, 则 (1) R是A上等价关系 A/R是A的划分 (2) A是A的划分 RA是A上等价关系,其中
xRAy z(zA xz yz) RA称为由划分A 所定义的等价关系(同块关系). #
x
8
定理27(证明(2))
(2) xRy [x]R=[y]R ; 证明: (2) 只需证明[x]R[y]R和[x]R[y]R. () z, z[x]RxRy zRxxRy
zRy z[y]R . [x]R[y]R. () 同理可证. z
x
y
9
定理27(证明(3))
k 0
k 0
23
Bell数表
n
Bn
1
1
2
2
3
5
4
15
5
52
6
203
7
877
n
Bn
8
4,140
9
21,147
10
115,975
11
678,570
12
4,213,597
13
27,644,437
14
190,899,322
24
第二类Stirling数表
n\k 0 1 2 3
4
5
6
7
89
01
1 01
2 01 1
subset
number)
: n
k

把n个对象分成k个非空子集的分法个数.
递推公式:
n 0

0,
n 1

1,
n 2

子集
定义：如果集合A中的每一个元素都是集合B中 的元素，则称集合A为集合B的子集。
符号表示：A ⊆ B
例子：集合{1, 2, 3}是集合{1, 2, 3, 4}的子集， 但{1, 2, 3, 4}不是{1, 2, 3}，并且集合A和集合 B不相等，则称集合A为集合B的真子集。
集合的表示方法
列举法
将集合中的所有元素一一列举出来， 用逗号分隔。
描述法
通过描述集合中元素所具有的共同特 征，来表达集合。
集合的元素
元素是构成集合的基本单位。
元素具有无序性，即元素的排 列顺序不影响集合的性质。
元素具有可替代性，即在一个 集合中，任何一个元素都可以 被另一个相同的元素所替代。
02 集合之间的关系
集合的关系
目录
• 集合的基本概念 • 集合之间的关系 • 集合的运算性质 • 集合的特殊关系 • 集合的应用
01 集合的基本概念
集合的定义
1
集合是由确定的、不同的元素所组成的总体。
2
集合中的元素具有互异性，即集合中不会有重复 的元素。
3
集合中的元素具有确定性，即集合中的元素是明 确的，不会存在模糊不清的情况。
集合的分配律是指一个集合与另外两 个集合的交集或并集进行运算时，可 以将该集合分别与两个集合进行运算 后再进行合并或交集运算。
详细描述
在集合运算中，如果一个集合M与另 外两个集合N和P进行运算，可以使用 分配律将M与N和P分别进行运算后再 进行合并或交集运算。例如， M∪(N∩P)等于(M∪N)∩(M∪P)。
符号表示：A ⫋ B
例子：集合{1, 2, 3}是集合{1, 2, 3, 4}的真子集，但{1, 2, 3, 4}不是{1, 2, 3}的真子集。

4.4 等价关系与划分等价关系：同时具有自反、对称和传递性。

等价关系是最重要、最常见的二元关系之一。

4.4 等价关系与划分定义4.13设R为非空集合A上的关系，如果R是自反的、对称的和传递的定义4.13，则称R为A上的等价关系。

设R为等价关系，如果<x,y> R，称x等价于y，记作x~y。

例如，实数集上的相等关系、幂集上的各子集间的相等关系，三角形集合上的三角形的相似关系都是等价关系。

因为等价关系是自反、对称和传递的，可以通过关系矩阵和关系图判断某关系是否是等价关系。

设A ={1, 2, …, 8}，A 上的关系R 定义如下：R={<x, y> | x, y ∈A ∧x ≡y(mod 3)}其中x ≡y(mod 3)叫做x 与y 模3相等，即x 除以3的余数与y 除以3的余数相等或x −y 可被3整除。

可以验证R 为A上的等价关系：例4.21 4.4 等价关系与划分（1）自反：∀x∈A，x ≡x(mod 3)，即<x, x>∈R。

（2）对称：∀x, y∈A，若x ≡y(mod 3)即<x, y>∈R，则y ≡x(mod 3)即<y, x>∈R。

（3）传递：∀x, y, z∈A，若x ≡y(mod 3)且y ≡z(mod 3)，则x ≡z(mod 3)。

该关系的关系图如下：Sed ut perspiciatis unde omnis.68%定义4.14设R 为非空集合A 上的等价关系， x ∈A ，令[x]R ={y | y ∈A ∧xRy}称[x]R 为x 关于R 的等价类，简称为x 的等价类，简记为[x]。

x 的等价类就是A 中所有与x 等价的元素构成的集合。

如例4.21中的等价类有：[1] = [4] = [7] = {1, 4, 7}[2] = [5] = [8] = {2, 5, 8}[3] = [6] = {3, 6}4.4 等价关系与划分定理4.144.4 等价关系与划分定理4.19设R 是非空集合A 上的等价关系，则（1）∀x∈A，必定有[x]≠∅且[x]⊆A 。

本节在偏序的基础上, 介绍偏序集中的特殊 元素.
1.偏序关系 Def 设R A A, 若R具有自反性、反对称
性和传递性, 则称R为A上的偏序.
例2-57 R, ?
例2-58 P(X), ? Remark 借用数的 表示偏序(理由?), 可读作
“小于等于”, (A, ) 称为偏序集. 例 N+, |?
set
set
algebra
algebra
logic
logic
graph
graph
2.相容类 Def 2-21 设R是集合A上的相容关系,
C A,若对于任意x, y C, 均有(x, y) R, 则 称C是由相容关系R产生的相容类. 在前例中, {set}, {set, algebra}, {logic}, {logic, algebra}, {logic, graph}, {logic, algebra, graph}等是由相容关系R产生的相容 类, 而{set, logic}, {set, graph}等不是.
c), (b, c), (c, b)}, 则R具有自反性、对称性以 及传递性, 因此R为A上的等价关系.
[a]R {x | x A,(a, x) R} {a}.
[b]R {b, c}.
[c]R {b, c}.
例2-48 Z上的模3同余关系R:
R {( x, y) | x, y Z,3 | (x y)}.
S的最小元b: b S,x S : b x.
存在性? (R, ), S = Z? (P(X), ), S = P(X)?
z [x]R (x, z) R. (x, y) R ( y, x) R. ( y, z) R z [ y]R.
同理可证, [ y]R [x]R ?

[3]R={3,7}
=[7]R
余数为3的等价类
[4]R={4}
余数为0的等价类
总结：
（1）集合中的10个元素都有一个等价类。
（2）各等价类之间或者完全相等或者不相交。
（3）所有等价类的并集就是A。
第12页
2
6
1
59
10 14
37
4
[1]R=[5]R=[9]R={1,5,9} [2]R=[6]R=[10]R=[14]R={2,6,10,14} [3]R=[7]R={3,7} [4]R={4}
整数集合上的“小于”关系 不是等价关系。
第4页
例3-10.2 集合A={1,2,3,4,5,6,7,9,10,14}，R是A上的模4同 余关系，试通过关系图说明R是等价关系。
分析：R={<x,y>|x除以4与y除以4的余数相同}
<x,y>∈R x(mod 4)=y(mod 4)或x≡y(mod 4)
每个关系子图即为一个等价类，位于此子图中的元 素的等价类相同，等于该子图中的所有元素构成的 集合。
第13页
2、等价类性质
R是A上等价关系，任意x,y,z∈A
⑴同一个等价类中的元素，彼此有等价关系R。
第9页
二
元 关
性 质
系
自反 对称 传递 反对称 反自反
等价关系
有 向 图
等 价 类
商 集
划 分
第10页
二、 等价类
1、定义3-10.2 : x的等价类 R是A上的等价关系，对任何x∈A，集合[x]R称为 由x生成的R等价类，简称x的等价类： [x]R={y|y∈A∧xRy} 简化写法：y∈[x]R xRy 讨论： （1）等价类[x]R是一个集合，且[x]R A。 （2）[x]R中的元素是在等价关系R中，与x有 等价关系R的所有元素组成的集合。 （3）[x]R Φ， x∈[x]R。