集合論問題集

5 難しいこと

5.1 濃度

集合 , について以下の問に答えよ。
1. (1) $|A| ≤ |B|$ であることの定義を述べよ。
2. (2) $|A| < |B|$ であることの定義を述べよ。
3. (3) $|A| = |B|$ であることの定義を述べよ。
-
1. (1) $A$ から $B$ への単射が存在する。
2. (2) $|A| ≤ |B|$ であって $|B| ≤ |A|$ ではない。
3. (3) $A$ から $B$ への全単射が存在する。
$|A| ≤ |B|$ , $|C| ≤ |D |$ であるとき $|A ×C | ≤ |B ×D |$ であることを示せ。
-

$|A | ≤ |B |$ の定義が「 $A$ から $B$ への単射が存在する」ということなので、これは第 3 章問 35 (1) によって示される。
ベルンシュタイン (Bernstein) の定理を述べよ。
-

「 $|A | ≤ |B |$ かつ $|B | ≤ |A |$ ならば、 $|A | = |B |$ である。」言い換えると「単射 $A → B$ と単射 $B → A$ が存在するならば、全単射 $A → B$ が存在する。」
次のような全単射を具体的に構成せよ。ただしなどは区間を表わすものとする。
1. (1) $a &'x003C; b$ に対して $f : (0,1) → (a,b)$
2. (2) $a ∈ ℝ$ に対して $f : [0,1) → [a,∞)$
3. (3) $a ∈ ℝ$ に対して $f : (0,1) → (a,∞ )$
4. (4) $a ∈ ℝ$ に対して $f : (0,1] → (- ∞, a]$
5. (5) $a &'x2208; ℝ$ に対して $f : (0,1) → (- ∞,a)$
6. (6) $f : [0,1] → [0,1)$
7. (7) $f : (0,1] → (0,1)$
8. (8) $f : [0,1) → (0,1]$
9. (9) $f : (- 1,1) → (- ∞, ∞)$
-
1. (1) $f(x) = (b- a)x + a$
2. (2) $f(x) = a - 1+ 1∕(1- x)$
3. (3) $f(x) = a - 1+ 1∕(1- x)$
4. (4) $f(x) = a + 1- 1∕x$
5. (5) $f(x) = a + 1- 1∕x$
6. (6) $S = {1∕2m | m ∈ ℕ ∪{0}}$ とする。 $x ⁄∈ S$ のとき $f(x) = x$ 、 $x ∈ S$ のとき $f(x) = x∕2$ で $f$ を定めれば、これが全単射になる。
7. (7) (6) の $f$ を $(0,1]$ に制限したもの。
8. (8) $f(x) = 1 - x$
9. (9) $f(x) = x ∕(1 - x2)$
これによって実数の区間はすべて等しい濃度をもつことが分かる。
$ℕ$ から $ℤ$ への全単射を具体的に構成せよ。
-

$a$ が偶数のとき $f(a) = a∕2$ 、 $a$ が奇数のとき $f(a) = (1- a)∕2$ とすれば、この $f$ は全単射である。
$ℕ × ℕ$ から $ℕ$ への全単射を具体的に構成せよ。
-

$a-1f(a,b) = 2 (2b- 1)$
$|ℚ| = |ℕ|$ を示せ。
-

$r ∈ ℚ$ を既約分数の形に書き、その分母を $r1$ , 分子を $r2$ とする。分母は正であるとし、整数については、その分母を $1$ とする。これによって写像 $ℚ → ℤ × ℤ$ , $r ↦→ (r1,r2)$ が定義でき、作り方から単射である。したがって $|ℚ| ≤ |ℤ× ℤ|$ である。問 2, 5, 6 より $|ℤ× ℤ| = |ℕ × ℕ| = |ℕ|$ となるので $|ℚ | ≤ |ℕ |$ である。
一方、自然な埋め込み $ℕ → ℚ$ があるので $|ℕ| ≤ |ℚ |$ である。よってベルンシュタインの定理により $|ℚ | = |ℕ |$ である。
$|ℕ| < |ℝ|$ を示せ。
-

$ℕ ⊂ ℝ$ なので $|ℕ | ≤ |ℝ|$ である。よって $|ℕ | ⁄= |ℝ |$ であること、すなわち $ℕ$ から $ℝ$ への全単射が存在しないことをいえばよい。 $I = (0,1)$ を開区間とする。 $|I| = |ℝ|$ なので $ℕ$ から $I$ への全単射が存在しないことをいえば十分である。 $f : ℕ → I$ を全単射とする。 $(0,1)$ の元を無限小数として表し

$f(1) = 0.a(1)a(1)a(1)⋅⋅⋅ 1(2)2(2)3(2)f(2) = 0.a1 a2 a3 ⋅⋅⋅f(3) = 0.a(13)a(23)a(33)⋅⋅⋅ ⋅⋅⋅$

と表すことにする。このとき、 $b ∈ I$ を少数第 $i$ 位が $f(i)$ と異なるように作る。そうすれば $b$ は、どの $f (i)$ とも異なるので $f$ が全単射であることに矛盾する。したがって $ℕ$ から $I$ への全単射は存在しない。
$ℝ$ から $ℝ\ {0}$ への全単射を具体的に構成せよ。
-

$f : ℝ → ℝ \{0}$ を、
${ x+ 1 if x ∈ {0} ∪ℕf(x) = x if x ⁄∈ {0} ∪ℕ$
で定めるとこれは全単射である。
$|X | < |2X |$ を証明せよ。
-

$f : X → 2X$ ( $f(x) = {x}$ ) は単射なので $|X| ≤ |2X|$ である。 $|2X| ≤ |X|$ と仮定する。ベルンシュタインの定理より、全単射 $g : X → 2X$ が存在する。
$R = {x ∈ X | x ⁄∈ g(x)}$
とおく。 $R ∈ 2X$ であり、 $g$ は全単射なので $R = g(y)$ となる $y ∈ X$ が存在する。 $y ∈ R$ とすると $y ⁄∈ g(y) = R$ で矛盾、 $y ⁄∈ R$ とすると $y ∈ g(y) = R$ でやはり矛盾である。したがって、このような全単射は存在せず $|X| < |2X|$ である。
すべてのものを含む集合が存在するとすれば、それは最大の濃度をもつはずであるが、この関係式によって、最大の濃度をもつ集合は存在しない。したがって、すべてのものを含むものは集合ではない。
$|ℝ × ℝ| = |ℝ |$ であることを示せ。
-

$I = (0,1)$ (開区間) とする。 $|ℝ| = |I|$ であるから $|I × I| = |I|$ を示せばよい。また $f : I → I × I$ ( $f(a) = (a,0.5)$ ) は単射なので $|I| ≤ |I × I|$ である。 $I × I$ から $I$ への単射を構成すればベルンシュタインの定理によって $|I × I| = |I|$ である。
任意の $a ∈ I$ は $0.a1a2a3⋅⋅⋅$ と無限 $10$ 進小数で表すことができる。ここで $0.1 = 0.999⋅⋅⋅$ などと表し、有限少数は許さないこととする。 $g : I × I → I$ を
$g(0.a1a2⋅⋅⋅ , 0.b1b2⋅⋅⋅) = 0.a1b1a2b2 ⋅⋅⋅$
で定義すると、これは単射である。
したがって $|ℝ × ℝ| = |I × I| = |I| = |ℝ|$ となる。
集合 $X$ とその真の部分集合 $Y$ に対して、 $|X | = |Y|$ である、すなわち全単射 $f : X → Y$ が存在する、とする。このとき $|ℕ | ≤ |X |$ であることを示せ。
-

$x ∈ X - Y$ とする。 $x = x 1$ として、帰納的に $x = f (x ) i+1 i$ ( $i ∈ ℕ$ ) とする。ただし $x = f(x) ∈ Y ⊂ X i+1 i$ と見る。これによって $X$ の部分集合 ${x } i i∈ℕ$ が得られる。これがすべて異なることをいえば、 $ℕ → X$ ( $i ↦→ x i$ ) は単射となり $|ℕ | ≤ |X |$ である。
$S = {(i,j) ∈ ℕ × ℕ | i < j}$ とおき、これを辞書式順序による整列集合 $ℕ × ℕ$ の順序部分集合と見れば、これも整列集合である。 $T = {(i,j) ∈ S | xi = xj}$ とおく。 $T = ϕ$ を示せばよいので、 $T ⁄= ϕ$ として矛盾を導く。
$T ⁄= ϕ$ とすると、 $S$ が整列集合であることから $T$ は最小元 $(i0,j0)$ をもつ。 $x1 ⁄∈ Y$ であり $j > 1$ に対しては $xj ∈ Y$ であるから、 $x1 ⁄= xj$ である。よって $i0 > 1$ である。また $i0 < j0$ であるから $j0 > 1$ も成り立つ。このとき $xi0 = xj0$ より $f(xi0-1) = f(xj0-1)$ である。 $f$ は単射なので $xi0- 1 = xj0- 1$ である。よって $(i0 - 1,j0 - 1) ∈ T$ である。しかし、これは $(i0,j0)$ の最小性に反する。したがって $T = ϕ$ である。
集合 $X$ について、ある真の部分集合 $Y$ との間に全単射が存在するとき、 $X$ を無限集合と定義することもある。したがって、この問は自然数の濃度 $|ℕ|$ (これを $aleph 0$ とかきアレフゼロとよむ) が無限集合の濃度のうち最小であることを示している。
$|X | ≤ |ℕ |$ となる集合 $X$ は整列順序をもつことを示せ。 ( $|X | ≤ |ℕ |$ となる集合 $X$ を可算集合という。)
-

単射 $f : X → ℕ$ が存在する。このとき $ℕ$ の順序によって $X$ の順序を定めれば、それは整列順序である。すなわち、 $x,y ∈ X$ に対して $f (x) ≤ f(y)$ のとき $x ≤ y$ と定めるのである。 (第 4 章問 24 参照)

5.2 選択公理

選択公理 (選出公理) を書け。
-

集合の族 ${Aλ}λ∈Λ$ を考える。任意の $λ ∈ Λ$ に対して $A λ$ は空でないとする。このとき、「各 $A λ$ からいっせいに一つずつ元を取り出すことができる。」
これは次のように言い換えることもできる。「直積集合 $∏ λ∈Λ Aλ$ は空でない。」
選択公理を他の標準的な公理から導くことはできない。したがって、しれを使うにはこれを公理として仮定しなくてはならない。しかし $Λ$ が有限集合であれば、他の標準的な公理から導くことができる。したがって、有限個の集合族に対して用いる場合には注意する必要はない。また、各 $Aλ$ が可算集合 (あるいは整列集合) であれば、やはり他の標準的な公理から導くことができる。
整列可能定理を書け。
-

任意の集合は整列順序をもつ。
ツォルン (Zorn) の補題を書け。
-

帰納的順序集合は極大元をもつ。
「選択公理」、「整列可能定理」、「Zorn の補題」の三つは互いに同値であることが分かっている。すなわちこのうちのどれか一つを仮定すれば、残りの二つが証明できるのである。
$X$ , $Y$ を空でない集合とする。選択公理を仮定する。 $X$ から $Y$ への全射が存在するとき、 $Y$ から $X$ への単射が存在することを示せ。
-

任意の $b ∈ B$ に対して $f-1(b) ⁄= ϕ$ である。各 $b ∈ B$ に対して $f -1(b)$ から一つ元を取り、それを $g(b)$ とする (ここで選択公理を使っている)。このとき $g : B → A$ は単射である。
第 3 章問36 とこの問により、選択公理を仮定すれば、 $X$ から $Y$ への全射が存在することと、 $Y$ から $X$ への単射が存在することは同値となる。
整列可能定理から選択公理を示せ。
-

集合の族 ${A } λ λ∈Λ$ を考え、任意の $λ ∈ Λ$ に対して $A λ$ は空でないとする。 $A = ⋃ A λ∈Λ λ$ とおく。整列可能定理より $A$ に整列順序が存在する。この順序によって、各 $A λ$ も整列集合となる。このとき $A λ$ は (唯一つの) 最小元をもつので、それを選ぶことによって $A λ$ からいっせいに一つずつ元を選ぶことが出来る。
集合の族 ${A λ}λ∈ Λ$ を考える。 $A = ⋃λ∈Λ Aλ$ とおく。 ${A λ}λ∈Λ$ の disjoint union とは
$⋃ {(x,λ) ∈ A × Λ | x ∈ Aλ}λ∈Λ$
のこととし、これを $∐ λ∈ΛA λ$ と書く。このとき $∐|A| ≤ | λ∈ΛA λ|$ を示せ。ただし、選択公理を仮定するものとする。
-

(証明 1)
単射 $∐f : A → λ∈ΛA λ$ を構成する。 $x ∈ A$ に対して、ある $λ ∈ Λ$ があって $x ∈ A λ$ である。したがって $Λ(x) = {λ ∈ Λ | x ∈ A λ}$ とおけば、これは空ではない。 ${Λ(x)}x∈A$ に選択公理を用いて、写像 $g : A → Λ$ が得られ、 $x ∈ Ag(x)$ である。このとき $∐f : A → λ∈ΛA λ$ を $f(x) = (x,g(x))$ で定めれば、これは単射となる。
(証明 2)
$∐f : λ∈Λ Aλ → A$ を $f(x,λ) = x$ で定める。これが全射であることを示せば、選択公理と問 17 より単射 $∐g : A → λ∈ΛA λ$ が存在する。
$x ∈ A$ とする。ある $λ ∈ Λ$ が存在し $x ∈ A λ$ である。このとき $(x,λ) ∈ ∐ λ∈ΛA λ$ であり $f(x,λ) = x$ である。よって $f$ は全射である。
$|∐ A | λ∈Λ λ$ を $∑ |A | λ∈Λ λ$ とも書く。特に $|Λ| < ∞$ である場合には $|A |+ ⋅⋅⋅+ |A | 1 n$ などの記号も用いる。
(代数学の知識を仮定する。) $R$ を単位元 $1$ をもつ環、 $I$ をその真のイデアルとする。このとき $I$ を含む極大イデアルが存在することを示せ。ただしツォルンの補題を利用してよい。
-

$S$ を $I$ を含む真のイデアル全体の集合とする。 $I ∈ S$ なので $S ⁄= ϕ$ である。 $S$ を集合としての包含関係によって順序集合と考える。 ${Jλ}λ∈Λ$ を $S$ の全順序部分集合とする。 $⋃J = λ∈ ΛJλ$ とおく。このとき $J$ は $R$ のイデアルで $I$ を含む。また、各 $λ ∈ Λ$ について、 $Aλ$ は $R$ の真のイデアルなので $1 ⁄∈ Jλ$ である。よって $1 ⁄∈ J$ となり $J ∈ S$ である。したがって ${Jλ}λ∈Λ$ は上界 $J$ をもち、上に有界である。よって $S$ は帰納的順序集合となり、ツォルンの補題によって極大元 $M$ をもつ。このとき $M$ は $R$ の極大イデアルであり $I$ を含む。