(0,1)≈2N N0,1,2,3, S10,1,1,0. S21,0,1,0, 0.0.0.0 "" N1,1,1,1, 0.0110.,0.1010.,0.0000.,0.1111 婚问题:0.01111110100,0非单射! 解决:? 《集合论与图论》第11讲
《集合论与图论》第11讲 11 (0,1)≈2N N 0, 1, 2, 3, … S1 0, 1, 1, 0, … S2 1, 0, 1, 0, … ∅ 0, 0, 0, 0, … N 1, 1, 1, 1,… 0.0110…, 0.1010…, 0.0000…, 0.1111… 问题: 0.0111111…=0.1000…, 非单射! 解决: ?
P(A)≈2A 证明:令fP(A)→)2A,f(B)=g,其中X是B 的特征函数,xg:A(0,1xx)=1XEB (1)是单射.设A≠A2,则X∈A,使得 X1(x)=x2×),枚1x a2 (2){是满射任给x:A-{0,1,令 B=XEA()=1sA, BxbX.# 回忆:2A=A→)2={f|fA2}(全函数) 《集合论与图论》第11讲
《集合论与图论》第11讲 12 P(A)≈2A 证明: 令f:P(A)→2A, f(B)=χB, 其中χB是B 的特征函数, χB:A→{0,1}, χB(x)=1⇔x∈B. (1) f是单射. 设A1≠A2, 则∃x∈A, 使得 χA1(x)≠χA2(x), 故χA1≠χA2. (2) f是满射. 任给χ:A→{0,1}, 令 B = { x∈A | χ(x)=1 }⊆A, 则χB=χ. # 回忆: 2A = A→2 ={ f | f:A→2 } (全函数)
A->(B->C)≈(AXB)→>C 证明:令F:(A→(B)C)→>(AXB)>C) F(=9,其中 fA-→(B→C), (AxXB)→>C, g(<a,b>)=f(a)(b) 注意f(a)B→>C. 《集合论与图论》第11讲 13
《集合论与图论》第11讲 13 A→(B→C) ≈ (A×B)→C 证明: 令F: (A→(B→C)) → ((A×B)→C), F(f)=g, 其中 f:A→(B→C), g:(A×B)→C, g(<a,b>)=(f(a))(b), 注意 f(a):B→C.
A->(B->C)≈(AXB)→>C 证明(续):(1)F是单射 设f12F(f)=91F()=92下证9192 因f+42,故a∈A,使得f)f2(2,故又 b∈B,使得(f1 (a)(b)≠(f(a)/b)即 91(ab>)=92(≤ab),所以9192 《集合论与图论》第11讲
《集合论与图论》第11讲 14 A→(B→C) ≈ (A×B)→C 证明(续): (1) F是单射. 设f1≠f2, F(f1)=g1, F(f2)=g2. 下证g1≠g2. 因f1≠f2, 故∃a∈A, 使得f1(a)≠f2(a), 故又 ∃b∈B, 使得 (f1(a))(b)≠(f2(a))(b), 即 g1(<a,b>)≠g2 (<a,b>), 所以g1≠g2.
A->(B->C)≈(AXB)→>C 证明(续)冫(2)F是满射 任给g(AB)>C,下证fA>(B→>C,使得 F(6)=g 令fA→(B)C),va∈A,f白)B→C,Wx∈B, (fa)(×)=g(<aX>),则F(①)=g.# 《集合论与图论》第11讲 15
《集合论与图论》第11讲 15 A→(B→C) ≈ (A×B)→C 证明(续): (2) F是满射. 任给g:(A×B)→C, 下证∃f:A→(B→C),使得 F(f)=g. 令f:A→(B→C), ∀a∈A, f(a):B→C, ∀x∈B, (f(a))(x) =g(<a,x>), 则F(f)=g. #