等价关系和集合分类
- 格式:doc
- 大小:239.00 KB
- 文档页数:2
§8 等价关系和集合分类
设A ≠∅,D 只含两个元,不妨设D ={0,1}或D ={对,错}
定义:称一个A ×A 到D 的映射R 为A 的元间的一个关系。
若R (a ,b )=1则称a 和b 符合关系R ,记a R b
若R (a ,b )=0则称a 和b 不符合关系R ,记为a R b.
定义:称A ×A 的任何子集为A 上的一个关系。
其实,以上两个定义是等价的。
例 A ={所有实数}
R :A ×A →D 为R (a ,b )=对,若b-a >0
R (a ,b )=错,若b-a >0不成立。
则R 是A 上的一个关系。其实,R 就是 上的“<”关系。
从 A 的元间的关系的定义可看,当给定一个集合后,该集合上有很多不同的关系,其中有一些是重要的,有些是并非重点。
现给出若干重要关系。设有A 的元间关系R
(Ⅰ)若对a ∀,a R a ,则称R 为自反关系
(Ⅱ)若a R b ,则b R a ,则称R 为对称关系
(Ⅲ)若a R b ,则b R a ,则称R 为反对称关系
(Ⅳ)若a R b ,若b R c ,则a R c ,则称R 为传递关系
特别, R 满足(Ⅰ)(Ⅱ)(Ⅲ),则称R 为等价关系,此时用~表示R 。
Ex :“等于”这个关系是一个等价关系
Ex :A ={平面上直线},定义A 的上关系R 为:1l ,2l ∈A 时
1l R 2l ⇔1l ∥2l (1l =2l 认为平行)
则易证R 为等价关系。
定义:若把一个集合A 分成若干个叫做类的子集,使得A 的每个元属于而且只属于一个类,则称这些类的全体为集合A 的一个分类。
注:分类也可以如下定义,{}i i x ∈∧为x 的非空子集族,满足
(ⅰ)i
i x ∈∧
=x (要求∧≠∅) (ⅱ),,i i j x i j x x i j
=⎧⋂=⎨∅≠⎩ *等价关系与集合的分类的关系有如下重要结果。
定理1:集合A 的一个分类决定A 的元间的一个等价关系。
(证明):设a 、b A ∈,定义
a R
b ,如果a ,b 在同一个类中
则 (Ⅰ)因a 和a 一定在同一个分类中,于是a R a ,
(Ⅱ)若a R b ,说明a ,b 在同一个类中,于是b R a ,
(Ⅲ)若a R b ,b R c ,则a ,b 在同一类中,b ,c 在同一个类。因为该类有公共元素c ,于是该两类其实是相同的。于是a ,c 在同一类中,所以a R c ,
由(Ⅰ)(Ⅱ)(Ⅲ)知R 为A 的元间的等价关系。
定理2:集合A 的元间的一个等价关系决定一个分类。
(证明):对∀给定 a ∈A ,记[a ]={b A ∈∣a ~b },考查{[a ]∣a ∈A }。 (ⅰ)若a ~b ,则[a ]=[b]。事实上,当c ∈[a ],则c ~a ,于是c ~b ∴c ∈[b],故[a ]⊂ [b]。同理可证[b] ⊂[a ]。∴[a ]=[b]。
(ⅱ)若a ∈[b] ⋂[c],则a ~b 且a ~c ⇒b ~c ⇒[b]=[c]
于是 [b] ⋂[c] =[b]或∅
(ⅲ)对∀a ∈A ,a ~a ,于是a ∈[a ]。所以A =
[]a a ∈∧
由(ⅰ)(ⅱ)(ⅲ)可知{ [a ]∣a ∈A }是A 的一个分类。
定义:一个集合的一个分类的每一个元素中的任何元素叫做该类的一个代表, 刚好由每一类的一个代表做成的集合叫做一个全体代表团。
例 A =Z ,取n N ∈,对a ,b N ∈,定义
a R
b ,如果|n a b -.
易证R 为A 的一个等价关系.
若11a p n q =+,22a p n q =+其中0≤1q ,2q <n ,则
a b -1212()()p p q q =-+-,于是可知|n a b -⇔1q =2q
而1q =2q 说明a ≡b (n).于是上述等价关系叫做模n 的同于关系。
由于R 的等价关系,因此带来一个分类,易求每一个分类为
[0]={…,-2n,-n,0,n,2n,…}
[1]={…,-2n+1,-n+1,1,n+1,2n+1,…}
……
[n-1]={…,-n-1,-1, n-1,2n-1,…}.