3、b>,,}=R1,bacbacG(R)G(R3)2021/7/306《集合论与图论》第7讲关系幂运算(举例,续3)解(续):R4=R3○R=R1○R=R2,R5=R4○R=R2○R=R3=R1,一般地,R2k+1=R1=R,k=0,1,2,…,R2k=R2,k=1,2,…,.#bacbacG(R)G(R5)bacG(R4)2021/7/307《集合论与图论》第7讲关系幂运算是否有指数律?指数律:(1)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.说明:对实数R来说,m,nN,Z,Q,R.对一般关系R来说,m,
4、nN.对满足IAR且AdomRranR的关系R来说,m,nN,Z,例如R2○R-5=R-3,因为可以定义R-n=(R-1)n=(Rn)-1?2021/7/308《集合论与图论》第7讲定理17定理17:设RAA,m,nN,则(1)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.说明:可让m,nZ,只需IAdomRranR(此时IA=R○R-1=R-1○R)并且定义R-n=(R-1)n=(Rn)-1.回忆:(F○G)-1=G-1○F-1(R2)-1=(R○R)-1=R-1○R-1=(R-1)22021/7/309《
5、集合论与图论》第7讲定理17(证明(1))(1)Rm○Rn=Rm+n;证明:(1)给定m,对n归纳.n=0时,Rm○Rn=Rm○R0=Rm○IA=Rm=Rm+0.假设Rm○Rn=Rm+n,则Rm○Rn+1=Rm○(Rn○R1)=(Rm○Rn)○R1=Rm+n○R=R(m+n)+1=Rm+(n+1).(2)同样对n归纳.#2021/7/3010《集合论与图论》第7讲R0,R1,R2,R3,…是否互不相等?R0R1R2R3R4R5R6R7R8R0R1R2R3R4R5=R19=R33=R47=…R6=R20=R34=R48=…R7=R21
6、=R35=R49=…R8=R22=R36=…R15R9R10R11R14R16R172021/7/3011《集合论与图论》第7讲定理16定理16:设
7、A
8、=n,RAA,则s,tN,并且,使得Rs=Rt.证明:P(AA)对幂运算是封闭的,即R,RP(AA)RkP(AA),(kN).
9、P(AA)
10、=,在R0,R1,R2,…,这个集合中,必有两个是相同的.所以s,tN,并且,使得Rs=Rt.#2021/7/3012《集合论与图论》第7讲鸽巢原理(pigeonholeprinciple)鸽巢原理(pigeonh
11、oleprinciple):若把n+1只鸽子装进n只鸽巢,则至少有一只鸽巢装2只以上的鸽子.又名抽屉原则(Dirichletdrawerprinciple),(PeterGustavLejeuneDirichlet,1805~1859)推广形式:若把m件物品装进k只抽屉,则至少有一只抽屉装只以上的物品.1.8=2,1.8=1,-1.8=-1,-1.8=-2.2021/7/3013《集合论与图论》第7讲定理18定理18:设RAA,若s,tN(s12、+i=Rs+i,其中k,iN,p=t-s;(3)令S={R0,R1,…,Rt-1},则qN,RqS.2021/7/3014《集合论与图论》第7讲定理18(说明)spi泵(pumping):Rs+kp+i=Rs+i2021/7/