集合の対等性についての補足 1 年次演習 (数学) (新國担当分) 2014 年 6 月 25 日 (水) 以下で, 講義における §3.2 で時間の都合上述べなかった, 集合の対等性に関する定理 3.2.1(Bernstein の定理) の証明を述べる. ✓ ✏ 定理 3.2.1. (Bernstein の定理) 集合 A, B に対し, A から B への単射が存在し, 更に B から A への単射も存在するならば, A と B は対等である. ✒ ✑ (証明) φ : A → B を A から B への単射の 1 つとし, ψ : B → A を B から A への単射の 1 つとする. このとき, 我々の目標は, ある全単射 f : A → B の存在を示すことである. 以下, φ が全射かどうかで場合を 2 つに分けよう. φ が全射であるとき: もともと φ は単射なので, φ は全単射である. 即ち, A と B は対等である (即ち f = φ). φ が全射でないとき: B の部分集合 B0 を B0 = B − φ (A) (i) で定義すると, φ が全射でないので φ (A) B であるから, B0 ̸= ∅ となる. そこで A の部分集合 Ai , 及び B の部分集合 Bi (i = 1, 2, . . . ) を, それぞれ A1 = ψ (B0 ) , A2 = ψ (B1 ) , . . . , Ai = ψ (Bi−1 ) , . . . , B1 = φ (A1 ) , B2 = φ (A2 ) , . . . , Bi = φ (Ai ) , . . . , で定義し, 更に A∗ = ∞ ∪ Ai , B∗ = i=1 ∞ ∪ Bi , i=0 A∗ = A − A∗ , B ∗ = B − B∗ とおく. このとき, φ (A∗ ) = B ∗ , (ii) ψ (B∗ ) = A∗ (iii) となることを示そう. まず, (ii) を示す. いま φ は単射なので, φ (A − A∗ ) = φ (A) − φ (A∗ ) (iv) が成り立つことに注意する.1 更に (i) から, B0 は B における φ (A) の補集合であり, 従って φ (A) は B における B0 の補集合である. 即ち φ (A) = B − B0 (v) である. このとき, (iv), (v) から (iv) φ (A∗ ) = φ (A − A∗ ) = φ (A) − φ (A∗ ) (v) = (B − B0 ) − φ (A∗ ) = B − (B0 ∪ φ (A∗ )) である.2 ここで φ (A∗ ) = φ (∞ ∪ ) Ai = i=1 であり, 従って B0 ∪ φ (A∗ ) = B0 ∪ ∞ ∪ φ (Ai ) = i=1 (∞ ∪ Bi i=1 ) Bi ∞ ∪ (vi) = i=1 ∞ ∪ (vii) Bi = B∗ i=0 となる. 故に (vi), (vii) から φ (A∗ ) = B ∗ となる. 即ち, (ii) が示された. 一方, (∞ ) (∞ ) ∞ ∞ ∪ ∪ ∪ ∪ ψ (B∗ ) = ψ Bi = ψ Bi−1 = ψ (Bi−1 ) = Ai = A∗ i=0 i=1 i=1 i=1 であるので, (iii) も示された. そこでいま, φ は単射で φ (A∗ ) = B ∗ なので, φ の定義域を A∗ に制限して得られる写像を f ∗ : A∗ → B ∗ とすれば, f ∗ は全単射である. 同様に, ψ は単射で ψ (B∗ ) = A∗ なので, ψ の定義域を B∗ に制限して得られる写像を g∗ : B∗ → A∗ とすれば, g∗ は全単射である. この g∗ の逆写像を f∗ とおく. 即ち, f∗ = g∗−1 : A∗ → B∗ は全単射である. このとき写像 f : A → B を, a ∈ A に対し { f ∗ (a) (a ∈ A∗ ) f (a) = f∗ (a) (a ∈ A∗ ) で定義すると, これは A から B への全単射である. 即ち, A と B は対等である. 1 写像 f : A → B 及び P, P , P ⊂ A, Q, Q , Q ⊂ B に対し, 一般に次が成り立つことを定理 1.4.5 で述べた: 1 2 1 2 (1) P1 ⊂ P2 ならば f (P1 ) ⊂ f (P2 ), (2) f (P1 ∪ P2 ) = f (P1 ) ∪ f (P2 ), (3) f (P1 ∩ P2 ) ⊂ f (P1 ) ∩ f (P2 ), (4) f (A − P ) ⊃ f (A) − f (P ), (5) Q1 ⊂ Q2 ならば f −1 (Q1 ) ⊂ f −1 (Q2 ), (6) f −1 (Q1 ∪ Q2 ) = f −1 (Q1 ) ∪ f −1 (Q2 ), (7) f −1 (Q1 ∩ Q2 ) = f −1 (Q1 ) ∩ f −1 (Q2 ), (8) f −1 (B − Q) = A − f −1 (Q), (9) f −1 (f (P )) ⊃ P , (10) f (f −1 (Q)) ⊂ Q. 更に, もし f が単射であれば (3), (4), (9) において等号が成立し, f が全射であれば (10) において等号が成立する. 詳細は演習問題とする. 2 一般に集合 A, B, C に対し, (A − B) − C = A − (B ∪ C) が成り立つ. これも演習問題とする. (vi) の最後の等号は, この事実から示される. 2