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

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},{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:a,bR当且仅当a与b同年龄.R是等价关系.2.6等价关系与划分•定义2.14（等价类）•设R是A上的等价关系，对于每个aA，与a等价的全体元素构成的集合称为由a生成的关于R的等价类，记为[a]R，即[a]R={x|xA，xRa}，a称为该等价类的代表元。根据上下文可以确定R时，将[a]R简记为[a]。•定义2.15（商集）•设R是A上的等价关系，关于R的全体等价类构成的集合称为A关于R的商集，记为A/R，即A/R={[a]|aA}。2.6等价关系与划分•定理2.13设R是A上的等价关系，则（1）对任一aA，有a[a]；（2）对a,bA，如果aRb，则[a]=[b];（3）对a,bA，如果a,bR，则[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）反证法证明；*/证明：已知a,bR，如果[a][b];假设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)说明:不等价的元素所属的等价类没有公共元素;•(1)~(4)共同说明：A关于R的商集A/R就是A的一个划分。首先A/R={[a]|aA}是集合族，然后检查其是否符合A的划分的3个条件–由(1)，A/R中每个集合都是非空的，–(4)说明[a]A/R[a]=aA[a]=A–任取[a],[b]A/R若[a]≠[b],必有a,bR（否则由(2)可得[a]=[b]，矛盾），那么由(3)得[a][b]=2.6等价关系与划分•定理2.14集合A上的任一划分={A1,A2,…,An}可以确定A上的一个等价关系，称为由导出的等价关系。–由定义A上的二元关系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})•={a,a,a,b,b,a,b,b,c,c,c,d,d,c,d,d,e,e,e,f,f,e,f,f}•定理2.15–(1)对A上的等价关系R，A/R导出的等价关系=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,3}=R•定理2.13和定理2.15:任一等价关系R确定一个划分,即A/R.•定理2.14和定理2.15:任一划分确定一个等价关系,即(A1A1)……(AnAn).•并且在给定R时，将A/R取作，有(A1A1)……(AnAn)=R；或者给定，将(A1A1)……(AnAn)取作R，则A/R=（的每个划分块都是R的一个等价类）。从而A的划分和A上的等价关系是一一对应的。•定理2.16设R1和R2是A上的等价关系，则R1R2是A上的等价关系。•例：设A={1,2,3,4,5}，A上的二元关系R中，有多少个是等价关系？•因为等价类划分和等价关系是一一对应的，所以A上的二元关系中等价关系的个数等于A的划分个数。•西安交通大学1998考研•解：对于A的划分可分为如下几种情况：•（1）划分成5个都只含1个元素的块，共有1种；•（2）划分成1个都只含2个元素，3个都只含1个元素的块，共有10种；•（3）划分成2个都只含2个元素，1个都只含1个元素的块，共有15种；•（4）划分成1个都只含3个元素，2个都只含1个元素的块，共有10种；•（5）划分成1个都只含3个元素，1个都只含2个元素的块，共有10种；•（6）划分成1个都只含4个元素，1个都只含1个元素的块，共有5种；•（7）划分成1个都只含5个元素的块，共有1种；•综上所述，A上的等价关系共有1+10+15+10+10+5+1=52•定义2.17(加细)设和’是A的划分，若’的每一块都包含在的某一块中，则称’细分，或’是的加细。•例：A是学生集合，是在A中按学院的划分，’是在A中按专业的划分。•定理2.17设和’是A的划分，它们确定A上的等价关系R和R’，则’细分当且仅当R’R。例：A是学生集合，是在A中按学院的划分，’是在A中按专业的划分。和’确定A上的等价关系R:同学院同学关系和R’:同专业同学关系，显然R’R。•证明：•/*’细分R’R，基本法*/•对于任一a,bR’，存在'的某块S’，使a,bS’。因为’细分，所以必存在的块S，使S’S。因此a,bS，从而a,bR。•/*R’R’细分*/•设S’是‘的一块，aS’则[a]R’={x|xR’a}=S’（请展开证明）。由于R’R，若xR’a必有xRa。因此{x|xR’a}{x|xRa}，即[a]R’[a]R。’的一块包含在的一块中，所以’细分。2.7次序关系•一偏序关系、偏序集•定义2.19(偏序关系)设R是A上的二元关系，若R是自反的、反对称的和传递的，则称R是A上的偏序关系。又记为。（借用了数的小于等于符号，但涵义更广）常见的偏序关系：,……•定义2.20(偏/半序集)若集合A具有偏序关系R（或），则称A为偏序集，记为（A,R）或（A,）。•哈斯图：常用来表示偏序集，画法如下–位置关系：若ab，则结点a在b之下；–连线规则：若a与b之间不存在其他元素c，使ac，cb则在a与b之间用一线相连。2.7次序关系•例题：Rosen《离散数学及其应用（本科教学版）》p225例13、例14、P226例18•判断是否正确，并说明理由。•设A为集合，R是A的幂集P(A)上的二元关系，对所有S,TP(A)，(S,T)R当且仅当|S||T|。那么，R是一个偏序关系。•/*复旦大学1999考研*/•证明整除关系是正整数集合上的偏序关系。•/*北京师范大学1999考研*/2.7次序关系•四最大元、最小元、极大元、极小元•定义2.21（最大元、最小元、极大元、极小元）设偏序集(A,)，BA，(1)最大元、最小元若存在一个元素bB，对所有b’B都有b’b，则称b是B的最大元；若都有bb’，则称b是B的最小元；(2)极大元、极小元若存在一个元素bB，在B中不存在元素b’b使得bb’，则称b是B的极大元；若在B中不存在元素b’b使得b’b，则称b是B的极小元；2.7次序关系(3)上界、下界若存在一个元素aA，对所有b’B都有b’a，则称a是B的上界；对所有b’B都有ab’，则称a是B的下界；(4)上确界、下确界若aA是B的上界且对B的每个上界a’都有aa’，则称a是B的上确界（最小上界，也就是B的上界集合中的最小元，故不一定存在）；若aA是B的下界且对B的每个下界a’都有a’a，则称a是B的下确界（最大下界）。2.7次序关系•定理2.22设偏序集(A,)，BA，若在B中存在最大元（最小元），则必唯一。•证明：（反证）•定理2.23设偏序集（A,）,BA，在B中存在最大元（最小元）必为极大元（极小元）。•写出集合A={a,b,c}的幂集P(A)，并画出偏序集(P(A),)的哈斯图。•/*北京航空航天大学1996考研试题*/2.7次序关系•二拟序关系•定义2.22（拟序关系）A上的二元关系R是反自反的和传递的，称R为A上的拟序关系。称(A,R)为拟序集，或记为(A,)。（不意味着小于）•定理2.24A上的二元关系R是拟序的，则R必为反对称的。证明：反证法2.7次序关系•定理2.25设R是A上的二元关系，则(1)若R是A上的拟序关系，则r(R)=RIA是A上的偏序关系；(2)R是A上的偏序关系，则R-IA是A上的拟序关系；•证明方法：根据定义给出的性质证明。2.7次序关系•三全序关系•定义2.23（全序关系）设是集合A上的二元关系，如果对于A中任意两个元素a,bA，必有ab或ba，则称是A上的全序关系（或线性次序关系）。•定义2.24（全序集）若集合A具有全序关系或R，则称A为全序集或线性次序集，记为(A,)或(A,R)。实例：字典序第3次作业•1.设R是A上的等价关系，S={(a,b)|存在cA使得aRc且cRb}，证明S也是A上的等价关系。•2.设R是A上的传递和自反关系,设T是A上的二元关系：(a,b)T当且仅当(a,b)和(b,a)都属于R,证明T是一个等价关系。•3.配套教材230页习题17