等价关系和集合分类.doc

§8等价关系和集合分类
设，只含两个元，不妨设＝{0,1}或={对，错}
定义：称一个×到的映射为的元间的一个关系。
若（，b）＝1则称和b符合关系，记b
若（，b）＝0则称和b不符合关系，记为b.
定义：称×的任何子集为上的一个关系。
其实，以上两个定义是等价的。
例＝{所有实数}
：×→为（，b）＝对，若b->0
（，b）＝错，若b->0不成立。
则是上的一个关系。其实，就是上的“<”关系。
从的元间的关系的定义可看，当给定一个集合后，该集合上有很多不同的关系，其中有一些是重要的，有些是并非重点。
现给出若干重要关系。设有的元间关系
（Ⅰ）若对，，则称为自反关系
（Ⅱ）若b，则b，则称为对称关系
（Ⅲ）若b，则b，则称为反对称关系
（Ⅳ）若b，若bc，则c，则称为传递关系
特别，满足（Ⅰ）（Ⅱ）（Ⅲ），则称为等价关系，此时用～表示。
Ex：“等于”这个关系是一个等价关系
Ex：＝{平面上直线}，定义的上关系为：，∈时
∥（＝认为平行）
则易证为等价关系。
定义：若把一个集合分成若干个叫做类的子集，使得的每个元属于而且只属于一个类，则称这些类的全体为集合的一个分类。
注：分类也可以如下定义，为的非空子集族，满足
（ⅰ）＝（要求）
（ⅱ）
*等价关系与集合的分类的关系有如下重要结果。
定理1：集合的一个分类决定的元间的一个等价关系。
（证明）：设、，定义
b，如果,b在同一个类中
则（Ⅰ）因和一定在同一个分类中，于是，
（Ⅱ）若b，说明，b在同一个类中，于是b，
（Ⅲ）若b，bc，则，b在同一类中，b，c在同一个类。因为该类有公共元素c，于是该两类其实是相同的。于是，c在同一类中，所以c，
由（Ⅰ）（Ⅱ）（Ⅲ）知为的元间的等价关系。
定理2：集合的元间的一个等价关系决定一个分类。
（证明）：对给定，记[]＝｛∣～b｝,考查｛[]∣｝。
（ⅰ）若～b，则[]＝[b]。事实上，当c[]，则c～，于是c～b
∴c[b]，故[][b]。同理可证[b][]。∴[]＝[b]。
（ⅱ）若[b][c]，则～b且～cb～c[b]＝[c]
于是[b][c]＝[b]或
（ⅲ）对，～，于是[]。所以＝
由（ⅰ）（ⅱ）（ⅲ）可知｛[]∣｝是的一个分类。
定义：一个集合的一个分类的每一个元素中的任何元素叫做该类的一个代表，
刚好由每一类的一个代表做成的集合叫做一个全体代表团。
例＝，取，对,b，定义
b，如果.
易证为的一个等价关系.
若，其中0≤，＜，则
，于是可知＝
而＝说明≡(n).于是上述等价关系叫做模n的同于关系。
由于的等价关系，因此带来一个分类，易求每一个分类为
[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,…｝.