等势关系是等价关系 自反:AA IA:A->A双射 秦对称:A≈B→B≈A fA→>B双射→f1B→A双射 传递:AB∧BC→AC f:A>B,g:B>C双射→gfA>C双射 《集合论与图论》第11讲
《集合论与图论》第11讲 6 等势关系是等价关系 自反: A≈A IA :A→A双射 对称: A≈B ⇒ B≈A f :A→B双射 ⇒ f -1:B→A双射 传递: A≈B ∧ B≈C ⇒ A≈C f :A→B, g:B→C双射 ⇒ g○f:A→C双射
证明等势兮构造双射 癱直接构造双射: NXNN,R≈(0,1),[0.1(0,1,(0,1)≈2N P(A)≈2A,A>(B→)C≈(AXB)>C 癱间接构造双射: 传递性:A≈B∧B≈C→AC SB定理:A<B∧B≤A→AB 《集合论与图论》第11讲
《集合论与图论》第11讲 7 证明等势 ⇔ 构造双射 直接构造双射: N×N≈N, R≈(0,1), [0,1]≈(0,1), (0,1)≈2N P(A)≈2A, A→(B→C)≈(A×B)→C 间接构造双射: 传递性: A≈B ∧ B≈C ⇒ A≈C S-B定理: A≤•B ∧ B≤•A ⇒ A≈B
R≈(0,1) 《集合论与图论》第11讲
《集合论与图论》第11讲 8 R≈(0,1)
0,1]≈(0,1) N>N0,12},{2,-1yNN 《集合论与图论》第11讲
《集合论与图论》第11讲 9 [0,1]≈(0,1) N→N-{0,1,2}, {-2,-1}∪N→N 012345678 012 345678 012345678 012345678 -1 -2
0,1]≈(0,1) Y 00 HH+ 《集合论与图论》第11讲
《集合论与图论》第11讲 10 [0,1]≈(0,1)