等价关系与集合的分类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
前页 前后页 前目页录 前返页回

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