定理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