集合的一个划分怎样确定一个等价关系?
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/19 11:32:09
集合的一个划分怎样确定一个等价关系?
集合的一个划分怎样确定一个等价关系?
集合的一个划分怎样确定一个等价关系?
等价关系 设R为定义在集合A上的一个关系,若R是自反的、对称的和传递的.则称R为等价关系.
划分 给定非空集合A,若有集合S={S ,S ,…,S },其中S A,S （i=1,2,…,m）,且S S = (i j)同时有 S =A,称S是A的划分.
等价类 设R为集合A上的等价关系,对任何a A,集合[a] ={x|x A,aRx}称为元素a形成的等价类.
商集 设集合A上的等价关系,其等价类集合{[a] |a A},称作A关于R的商集,记作A/R.
定理3.7.1 设给定非空集合A上等价关系R,对于a,b A,有aRb iff [a] = [b] .
定理3.7.2集合A上的等价关系R,确定了A的一个划分,该划分就是商集A/R.
定理3.7.3集合A的一个划分,确定A的元素间的一个等价关系.
集合上每个等价关系对应集合的一种划分,集合的每一种划分又对应于该集合的一/((n 1)n!n!),如4个元素的集合，可以确定14种等价关系.
划分的每一个子集确定一个等价类，不同子集不等价
易验证满足等价关系的三个条件。
问题是“怎样”，所以用算法来回答。
限定条件：有限离散集合
算法：
（1）设定集合R为空集：R = {}
（2）对划分中的每一个子集s[i]，假设它有ni个元素：
（2.1）枚举s[i]的2元组，得集合Ri={
（2.2）把Ri并入R，即R=R∪Ri；
（3）算法结束，R即为所求的...
全部展开
问题是“怎样”，所以用算法来回答。
限定条件：有限离散集合
算法：
（1）设定集合R为空集：R = {}
（2）对划分中的每一个子集s[i]，假设它有ni个元素：
（2.1）枚举s[i]的2元组，得集合Ri={
（2.2）把Ri并入R，即R=R∪Ri；
（3）算法结束，R即为所求的等价关系；
举例说明：
集合S={1,2,3,4}，它的一个划分B={{1},{2,3},{4}}，则各s[i]和对应的Ri列表如下：
i s[i] Ri
0 {1} {<1,1>}
1 {2,3} {<2,2>,<2,3>,<3,2>,<3,3>}
2 {4} {<4,4>}
按以上算法，得到的等价关系R=R0∪R1∪R2={<1,1>,<2,2>,<2,3>,<3,2>,<3,3>,<4,4>}
收起