集合論

花木章秀

目次

5 難しいこと
5.1 集合の濃度
5.2 選択公理、整列可能定理、Zorn の補題
5.3 演習問題

Chapter5
難しいこと

5.1 集合の濃度

集合 S が有限集合である場合、 S に含まれる要素の数を S の濃度という。すなわち、既に定義した記号で |S | が S の濃度である。無限集合に対しても濃度を考えよう。前の定義では、無限集合 S に対してはすべて |S | = ∞ と書いた。すべての無限は同じであろうか。これを考えるために、二つの集合に対して濃度が大きい、小さいという概念を定義する。

簡単のために二つの有限集合 A , B を考える。 A と B から同時に一つずつ元を取っていき、先に元がなくなった方が濃度は小さいといえる。例えば A が先になくなったとしよう。このとき A の元 a に対して、 a と同時に取った B の元 ba を対応させれば写像 f : A → B が得られる。また一つの f(a) に対して a と異なる c ∈ A で f(c) = f(a) となることはないからこの写像は単射である。一般に単射 f : A → B が存在するとき A の濃度は B の濃度以下である。これを無限集合に対しても適用する。この節では無限集合 S に対して、その濃度を |A | で表すが |A | = ∞ という記号は用いないで、無限を区別することにする。

定義5.1.1. 二つの集合 A , B に対して単射 f : A → B が存在するとき |A | ≤ |B | と定義する。また |A| ≤ |B| であって |B | ≤ |A | でないとき |A| < |B| と表す。

全単射 f : A → B が存在するとき |A | = |B | と定義する。

このようなときに集合の濃度が大きい、小さい、等しいなどということにする。

二つの有限集合 A , B に対して A ⊊ B であるならば |A | < |B | であることは感覚的に理解できるであろう。では無限集合ではどうだろうか。 ℕ を自然数全体の集合として 2 ℕ を偶数である自然数全体の集合とする。このとき 2ℕ ⊊ ℕ である。しかし写像 f : ℕ → 2ℕ を f (a ) = 2a で定めれば、これは全単射である。よって |ℕ| = |2ℕ| が成り立つ。したがって無限集合に対しては A ⊊ B であっても |A | < |B | とは限らないことになる。

例5.1.2. a,b ∈ ℝ , a < b に対して開区間 I = (a,b) a,b を考える。 a < b , c < d に対して |Ia,b| = |Ic,d| である。実際 f : Ia,b → Ic,d を

f (x) = c --dx + ad---bc- a - b a - b
で定めれば、これは全単射である。

例5.1.3. |I-1,1| = |ℝ | である。実際 f : I- 1,1 → ℝ を

--x----f (x) = 1 - x2
で定めれば、これは全単射である。前の例と合わせると、任意の開区間は ℝ と同じ濃度をもつ。

定理5.1.4 (Bernstein の定理). |A | ≤ |B | かつ |B | ≤ |A | のとき |A | = |B | である。すなわち二つの単射 f : A → B と g : B → A が存在するとき、全単射 h : A → B が存在する。

証明. A0 = A , B0 = B とおいて、帰納的に

A = g(B ), B = f(A ) n+1 n n+1 n
とする。また
∞⋂ ∞⋂A ∞ = An, B ∞ = Bn n=0 n=0
とする。このとき
A = A ∞ ∪ (A0 - A1 ) ∪ (A1 - A2 ) ∪ ⋅⋅⋅ , B = B ∞ ∪ (B0 - B1 ) ∪ (B1 - B2 ) ∪ ⋅⋅ ⋅
は共通部分のない和集合である。

g : B → A は単射であるから g : B → g(B ) = A1 と見ればこれは全単射である。よって a ∈ A1 に対して - 1g (a ) ∈ B が定義される。

f(A ∞) = B ∞ を 示 す。 まず、任意の n に対して A ∞ ⊂ An であるから f (A ∞ ) ⊂ f(An ) = Bn+1 であり、よって f (A ∞ ) ⊂ B∞ である。また B ∞ ⊂ Bn+1 = f (An) であるから B ∞ ⊂ f (A∞ ) も成り立つ。よって f(A ) = B ∞ ∞ である。

h : A → B を

( |{ f(x) あ る 非 負 整 数 n に 対 し て x ∈ A2n - A2n+1 の と き -1h (x) = | g (x) あ る 非 負 整 数 n に 対 し て x ∈ A2n+1 - A2n+2 の と き ( f(x) x ∈ A ∞ の と き
と定める。このとき
f |A2n-A2n+1 : A2n - A2n+1 → B2n+1 - B2n+2, -1g |A2n+1-A2n+2 : A2n+1 - A2n+2 → B2n - B2n+1, f |A ∞ : A∞ → B∞
がすべて全単射であることから h は全単射となる。

例5.1.5. 閉区間 A = [- 1,1 ] と開区間 B = (- 1,1) を考える。

( ) 1-f : A → B f(x) = 2 x , g : B → A (g(x) = x)
とすれば f,g は共に単射であり、よって |A | ≤ |B | かつ |A| ≥ |B | となる。 Bernsteinの定理はこのとき |A | = |B | であることを主張している。すなわち、全単射 h : A → B が存在することを意味している。実際にこの全単射を構成してみよう。

A′ = {1∕2ℓ | ℓ は 非 負 整 数 } とおく。 h : A → B を

{ x ∕2 x ∈ A ′の と きh(x ) = ′ x x ⁄∈ A の と き
で定める。すぐにわかるように h | ′(A ′) = A ′ - {- 1,1} A であり、また h| ′ A は単射である。また h|A- A′ が全単射であることは明らかである。よって h は A から B = A - {- 1,1} への全単射となる。

注意. 全射 A → B が存在すれば |A| ≥ |B| のように思えるが、これは後で紹介する選択公理を用いなければ示すことができない。

任意の二つの集合 A , B に対して |A | < |B | , |A | = |B | , |A| > |B | のいずれかが成り立つように思われる。しかしこれも選択公理を用いなければ示すことができない (濃度の比較可能定理)。

自然数全体の集合 ℕ と同じ濃度をもつ集合を可算無限集合という。可算無限集合の濃度を aleph 0 と書きアレフゼロと読む。可算無限集合は無限集合の中で最も小さいものであるといえる。よって aleph 0 は無限濃度のうちで最も小さいものである。可算無限集合と有限集合を合わせて可算集合という。

例5.1.6. 以下の集合はすべて可算無限集合である。「自然数全体の集合 ℕ 」、「偶数全体の集合」、「奇数全体の集合」、「直積集合 ℕ × ℕ 」「整数全体の集合 ℤ 」、「有理数全体の集合 ℚ 」、「可算無限集合の無限部分集合」

可算集合でない無限集合は存在するのであろうか。以下の命題が可算集合でない無限集合の例を示している。

命題5.1.7. |ℕ | < |ℝ| が成り立つ。

実数全体の集合 ℝ の濃度 |ℝ| を連続体濃度といい aleph と表す (アレフと読む) 。「 |ℕ | < |S| < |ℝ| となるような集合 S が存在するか 」という問題は連続体仮説などと呼ばれ数学的に証明できないことが証明されている。では無限集合の濃度は他にあるのだろうか。これには明快に答えることができて、無限集合の濃度はいくらでも存在する。

命題5.1.8. 任意の集合 A に対して、そのべき集合 2A を考えれば |A| < |2A| が成り立つ。特に A として無限集合 (例えば可算無限集合) をとれば、無限濃度の列

A (2A)|A | < |2 | < |2 | < ⋅⋅⋅
が得られる。

証明. 2A は A の部分集合全体の集合である。よって元の数が 1 である部分集合全体の集合を考えれば、それと A との間に全単射が存在し、よって |A | ≤ |2A | である。

A|A | = |2 | と仮定する。このとき全単射 Af : A → 2 が存在する。

R := {x ∈ A | x ⁄∈ f(x)}
とおく。 R は A の部分集合なので R ∈ 2A である。 f は全単射なので、ある r ∈ A があって f(r) = R である。ここで

よって、このような全単射は存在しない。

これを対角線論法という。 |ℕ | < |ℝ | もこれを使って証明される。 I = (0,1) (開区間) として |ℕ| < |I| を示そう。例 5.1.3 より |I| = |ℝ | であるから、このことによって |ℕ| < |ℝ| が示される。 I の任意の元 a は 0.a1a2 ⋅⋅⋅ という無限小数として表すことができる。 f : ℕ → I が全単射であるとする。

(1) (1) (1)f(1) = 0.a 1 a2 a3 ⋅⋅⋅f(2) = 0.a (21)a(22)a(32)⋅⋅⋅ (3) (3) (3)f(3) = 0.a 1 a2 a3 ⋅⋅⋅ ⋅⋅⋅
と表すことにする。このとき、 b ∈ I を少数第 i 位が f (i) と異なるように作る。そうすれば b は、どの f(i) とも異なるので f が全単射であることに矛盾する。これが対角線論法と呼ばれる理由も分かって頂けたであろうか。

さて集合の濃度にはいくらでも大きなものが存在し、濃度が一番大きな集合というものは存在しない。「集合すべての集合」というのが存在するとすれば、それは濃度が一番大きな集合となり、ラッセルのパラドックスと同様に矛盾が生じる。

以下のことは証明なしに結果だけ紹介しておく。 (証明には以下に述べる選択公理を必要とするものもある。)

命題5.1.9. A が 有 限 集 合で B が無限集合であるとき |A ∪ B | = |B | , |A × B | = |B| である。また A , B ともに無限集合であるとき |A ∪ B | = max {|A |,|B |} , |A × B | = max { |A |,|B |} である。すなわち、和集合や直積集合を作っても、濃度の大きな集合を作ることはできない。

5.2 選択公理、整列可能定理、 Zorn の補題

{A1, A2, ⋅⋅⋅ ,An } を有限個の空でない集合の族とする。このとき各 Ai から一つずつ元 xi を選ぶことはできる。有限とは限らない集合の族 {A λ | λ ∈ Λ } の場合はどうであろうか。実はこれは他の公理からは証明できないことが知られている。しかしこれは感覚的に正しいように思われる。そこで、これを公理として採用し選択公理 (または選出公理) と呼ぶ。

選択公理. 集合の族 {A λ | λ ∈ Λ} において、どの A λ も空でないとする。このとき各 A λ から一つずつ元 xλ を選ぶことができる。

これは次のように言い換えることもできる。

選択公理. 集合の族 {A λ | λ ∈ Λ} において、どの A λ も空でないとする。このとき直積集合 Π A λ∈Λ λ も空でない。

数学の多くの部分で選択公理が利用されているが、選択公理を仮定しない数学もある。 (実は写像のところで既に選択公理を利用しているところがあった。探してみるといいだろう。) 選択公理は以下のツォルンの補題、ツェルメロの整列可能定理と同値であることが知られている。したがって選択公理を仮定している場合には、これらも成り立つとしてよい。

ツォルン(Zorn) の補題. 順序集合 A が帰納的ならば A に少なくとも一つの極大元が存在する。

ツェルメロ(Zermelo) の整列可能定理. 任意の集合 A 上に整列順序が定義できる。

整列順序とは、任意の空でない部分集合に最小元が存在する、ということであった。例えば ℝ は通常の順序で整列集合ではない。整列可能定理は、うまく順序を入れれば ℝ も整列順序にできる、ということを主張している。これは明らかとは言えないだろう。

以下のことは選択公理を仮定して証明される。

定理5.2.1 (濃度の比較可能定理). 任意の二つの集合 A , B に対して |A | < |B | , |A | = |B | , |A| > |B | のいずれかが成り立つ。

定理5.2.2. 全射 f : A → B が存在すれば |A| ≥ |B | である。

証明. 任意の b ∈ B に対して f- 1(b) ⁄= ϕ である。各 b ∈ B に対して f-1(b) から一つ元を取り、それを g(b) とする (ここで選択公理を使っている)。このとき g : B → A は単射であり |A | ≥ |B | となる。

5.3 演習問題

  1. f : ℕ × ℕ → ℕ を f(a,b) = 2a-1(2b - 1) で定めると、これは全単射であること を示せ。
  2. ℝ と ℝ - {0} の間の全単射を構成せよ。