集合论第三课等价关系与偏序关系ppt课件.ppt

《集合论第三课等价关系与偏序关系ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.6等价关系与划分定义2.12（划分）设A是一个集合。{Ai}是一组不同的集合,且Ai,i=1,…,n。若A1A2An=A，AiAj=（i,j=1,…n,ij），则称={A1,A2,…,An}是A的一个划分。其中每个Ai称为划分的一个块。显然，A的划分是2A的子集。例2.21设A={a,b,c}，A的子集组成的以下集合(是2A的子集)，哪些是A的划分？P={{a,b},{c}}S={{a},{b},{c}}T={{a,b,c}}U={{a},{c}}V={{a,b},{b,c}}W={{a,b}

2、,{a,c},{c}}P,S,T是A的划分，其余不是A的划分。2划分的块数可以是有限的或无限的例2.22：整数集I的划分:1={E,O}，其中E为偶数集，O为奇数集；2={{0},{-1,1},{-2,2},{-3,3},……}也是I的一个划分。定义2.13（等价关系）设R是A上的二元关系，若R是自反的、对称的和传递的，则称R是A上的等价关系。若aRb，则称a与b等价。例2.23设A是一个学生集合,定义A上二元关系R:R当且仅当a与b同年龄.R是等价关系.2.6等价关系与划分定义2.14（等价类）设R是

3、A上的等价关系，对于每个aA，与a等价的全体元素构成的集合称为由a生成的关于R的等价类，记为[a]R，即[a]R={x

4、xA，xRa}，a称为该等价类的代表元。根据上下文可以确定R时，将[a]R简记为[a]。定义2.15（商集）设R是A上的等价关系，关于R的全体等价类构成的集合称为A关于R的商集，记为A/R，即A/R={[a]

5、aA}。2.6等价关系与划分定理2.13设R是A上的等价关系，则（1）对任一aA，有a[a]；（2）对a,bA，如果aRb，则[a]=[b];（3）对a,bA，如果R，

6、则[a][b]=;（4）aA[a]=A。/*（1）根据等价类的定义进行证明；*/证明：由于R是自反的，即aRa，所以a[a]。/*（2）基本法证明；*/证明：/*先证明[a][b]*/对任一c[a]，有cRa，又由假设aRb，根据R的传递性，必有cRb，即c[b]，从而[a][b]；/*再证明[b][a]*/对任一c[b]，有cRb，又由假设aRb，根据R的传递性，必有cRa，即c[a]，从而[b][a]；所以[a]=[b]。/*（3）反证法证明；*/证明：已知R，如果[a][b

7、];假设c[a][b],则c[a]且c[b],从定义可知cRa，cRb。由R的对称性和传递性，必有aRb，导致矛盾。所以[a][b]=。/*（4）基本法证明*/证明：对任一caA[a]，存在bA使c[b]。而[b]A，从而cA，所以aA[a]A。反过来，再证AaA[a]。任一cA，[c]aA[a],由于c[c]，故caA[a]。定理2.13(1)说明:A中每个元素所产生的等价类都是非空的；(2)说明:互相等价的元素属于同一个等价类,(3)说明:不等价的元素所属的

8、等价类没有公共元素;(1)~(4)共同说明：A关于R的商集A/R就是A的一个划分。首先A/R={[a]

9、aA}是集合族，然后检查其是否符合A的划分的3个条件由(1)，A/R中每个集合都是非空的，(4)说明[a]A/R[a]=aA[a]=A任取[a],[b]A/R若[a]≠[b],必有R（否则由(2)可得[a]=[b]，矛盾），那么由(3)得[a][b]=2.6等价关系与划分定理2.14集合A上的任一划分={A1,A2,…,An}可以确定A上的一个等价关系，称为由导出的等价关系。由定义A

10、上的二元关系R=(A1A1)(A2A2)……(AnAn)证明R是一个等价关系，即证明R是自反、对称和传递的。例2.26设A={a,b,c,d,e,f}的一个划分={{a,b},{c,d},{e,f}},由确定A上的一个等价关系R:R=({a,b}{a,b})({c,d}{c,d})({e,f}{e,f})={,,,,,,,,,,,}定理2.15(1)对A上的等价关系R，A/R

11、导出的等价关系=R（请给出证明）(2)设R1和R2是A上的等价关系，R1=R2A/R1=A/R2。（左推右显然，根据(1)右推左）例：A={1,2,3},R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}A/R={{1,2},{3}}写出由A/R导出的等价关系{<1,1>,<1,2>,<2,1>,<2,2>,<3