等价关系及等价类

《等价关系及等价类》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、定义10.6.1对非空集合上的关系，如果是自反的、对称的和传递的，则称为上的等价关系。　　等价关系的例子很多，如平面上三角形集合中，三角形的相似关系是等价关系；上海市的居民的集合中，住在同一区的关系也是等价关系。　　等价关系的关系图具有以下特征：　　1．每个结点都由自回路，即R是自反的；　　2．两个结点a,b之间若有从a指向b的弧，就有从b指向a的弧，即R是对称的；　　3．若有从a指向b的弧，且有从b指向c的弧，就有从a指向c的弧，即R是传递的。　　第9章给出了用平面坐标系中的矩形表示笛卡儿积的图形表示法。显然可以用正方形表示，如图10.6.2(a)所示。A上的关系是的子集，因此可以用正方形的

2、子集表示。A上的等价关系可以用正方形的一条对角线和线上的若干正方形表示。如图10.6.2(b)所示。但图10.6.2(c)所表示的关系不是等价关系。它包括了对角线，所以有自反性。它以对角线为对称轴，所以有对称性。但它没有传递性。因为R中的a和b点对应的有序对，经传递得到c点对应的有序对应在R中，但c点不在R中。图10.6.2例1在非空集合A上的恒等关系和全关系都是等价关系。在所有谓词公式的集合上的等值关系也是等价关系。例2集合上的关系　　　　。　　其中表示可被3整除。　　对任意的可被3整除。若可被3整除，则也可被3整除。若和可被3整除，则可被3整除。所以，R具有自反性、对称性和传递性，R是A上

3、的等价关系。　　R的关系图如图10.6.1所示。在图中，A的元素被分成三组，每组中任两个元素之间都有关系，而不同组的元素之间都没有关系。这样的组称为等价类。图10.6.1　定义10.6.2R是非空集合A上的等价关系，对任意的，令　　　　　则称集合为x关于R的等价类，简称x的等价类，也可简记作[x]或。例3对例2的等价关系R,有三个不同的等价类:　　　，　　　，　　　。　　A的8个元素各有一个等价类。各等价类之间，或者相等，或者不相交。而且所有等价类的并集就是A。　　整数集合Z上的模n等价关系，即　　　　　可以根据任何整数除以n（n为正整数）所得余数进行分类，构成n个等价类，记作　　　　　即　　

4、　　　　﹒﹒﹒﹒﹒﹒　　定理10.6.1R是非空集合A上的等价关系，对任意的，成立　　（1）且，　　（2）若，则，　　（3）若，则，　　（4）。证明　　（1）对任意的，则，因此。由等价类定义，显然。　　（2）对任意的，有。由对称性，有和传递性，有，所以。类似可证→。因此，。　　（3）假设。则存在，使得且。即且，由对称性，由传递性。与已知矛盾。　　（4）对任意的。则有。反之，对任意的，则有。所以，。因此。　　由定理可知，对A上的等价关系R，所有等价类的集合具有很好的性质。定义10.6.3对非空集合A上的关系R，以R的不相交的等价类为元素的集合称为A的商集，记作。　　这个定义也可以写成　　　。例4

5、对例2的A和R，商集是　　　。