RR1,R,R3,.是否互不相等? Ro R1 R2 R3 R4 R5 R6 R RS R0R1R2R3R4R5=R19=R3=R47= R6=R20=R34=R48= R7=R21=R35=R49= R17 R8=R2236 R164 15 R10 R R11 《集合论与图论》第7讲
《集合论与图论》第7讲 11 R0,R1,R2,R3,…是否互不相等? R0 R1 R2 R3 R4 R5 R6 R7 R8 R0 R1 R2 R3 R4 R5=R19=R33=R47=… R6=R20=R34=R48=… R7=R21=R35=R49=… R8=R22=R36 =… R15 R9 R10 R R11 14 R16 R17
定理16 鲁定理16:设A=n,RAxA,则彐steN,并 且0<s<t<2n,使得Rs=Rt 秦证明:P(AXA)对幂运算是封闭的,即 VR,R∈P(AA)→R∈P(AXA),keN) P(AxA川|=2",在RQR1,R2,…,R2这 2"+1个集合中,必有两个是相同的 所以彐s,t∈N,并且0<s<t≤2", 使得RS=R.# 《集合论与图论》第7讲
《集合论与图论》第7讲 12 定理16 定理16: 设 |A|=n, R⊆A×A, 则 ∃s,t∈N, 并 且 , 使得 Rs = Rt. 证明: P(A×A)对幂运算是封闭的, 即 ∀R, R∈P(A×A) ⇒ Rk∈P(A×A), (k∈N). |P(A×A)| = , 在R0,R1,R2,…, 这 个集合中, 必有两个是相同的. 所以 ∃s,t∈N, 并且 , 使得 Rs = Rt. # 2 n 0 ≤ s < t ≤ 2 2 n 2 2 n2 R 2 1 2 n + 2 n 0 ≤ s < t ≤ 2
鸽巢原理(p igeonhole principle 鸽巢原理( pigeonhole principle):若把n+1 只鸽子装进n只鸽巢,则至少有一只鸽巢 装2只以上的鸽子 又名抽屉原则 Dirichlet drawer principle) Peter Gustav Lejeune Dirichlet, 1805-1859) 推广形式:若把m件物品装进k只抽屉,则 至少有一只抽屉装只以上的物 「18=2,.1.8}=1,「-18-1,-18=2 《集合论与图论》第7讲 13
《集合论与图论》第7讲 13 鸽巢原理(pigeonhole principle) 鸽巢原理(pigeonhole principle): 若把n+1 只鸽子装进n只鸽巢, 则至少有一只鸽巢 装2只以上的鸽子. 又名抽屉原则(Dirichlet drawer principle), (Peter Gustav Lejeune Dirichlet,1805~1859) 推广形式: 若把m件物品装进k只抽屉, 则 至少有一只抽屉装 只以上的物品. ⎡1.8⎤=2, ⎣1.8⎦=1, ⎡-1.8⎤=-1, ⎣-1.8⎦=-2. ⎥⎥⎤ ⎢⎢⎡ km
定理18 定理18:设RcA×A,若steN(s<t,使得 RS=Rt,则 (1)R+=R; (2)Rp+=R,其中k∈N,p=ts; 3)令S={R0R,R(1]则vqeN,Rq∈S 《集合论与图论》第7讲
《集合论与图论》第7讲 14 定理18 定理18: 设 R⊆A×A, 若 ∃s,t∈N (s<t),使得 Rs = Rt, 则 (1) Rs+k = Rt+k ; (2) Rs+kp+i = Rs+i, 其中k,i∈N, p=t-s; (3) 令S={R0,R1,…,Rt-1}, 则∀q∈N, Rq∈S.
定理18(说明 泵 pumping RS++i= RS+ 《集合论与图论》第7讲 15
《集合论与图论》第7讲 15 定理18(说明) s p 泵 i (pumping): Rs+kp+i = Rs+i