利用者:Nayuta Ito/高校数学から巨大基数まで最速でたどる

この記事はジョークではありません。

前提知識: 高校数学(ほとんどⅠA)。~~数ⅡBの知識は(たぶん)必要ないし、数Ⅲの知識は全く必要ない。~~極限の概念が必要なので数Ⅲを勉強してください。極限は必要ですが微積は必要ありません。

目標知識: 到達不可能基数の定義。あわよくばマーロ基数まで行きたい。

参考文献: 巨大数研究Wiki

第0章記号の定義

$ \mathbb{N} $で$ 0 $以上の整数の集合を表すことにする。

$ \mathbb{R} $で実数全体の集合を表すことにする。

第1章順序数の定義

参考文献: 巨大数研究Wiki「順序数」

第1節直積

集合$ A $と$ B $に対し、$ A $と$ B $の直積とは、$ \{ (a,b) \mid a \in A, b \in B \} $のことであり、$ A \times B $で表す。

以下に例を示す。

$$ \{ 1, 2, 3 \} \times \{ a, b\} = \{ (1,a), (1,b), (2,a), (2,b), (3,a), (3,b) \} $$

$$ \mathbb{N} \times \{ 1 \} = \{ (0,1), (1,1), (2,1), \cdots \} = \{ (x,1) | x \in \mathbb{N} \} $$

$ \mathbb{R} \times \mathbb{R} = \{ (x,y) \mid x, y \in \mathbb{R} \} $であるが、$ (x,y) $を座標だと思うと、これは座標平面全体に対応する。

第2節関係

集合$ A $に対し、$ A $上の関係とは、$ A \times A $の部分集合のことである。関係は英語でrelationと呼ばれるため、その頭文字を取って$ R $で表されることが多い。

$ (a,b) \in R $であるとき、$ a R b $と書くこともある。

以下に例を示す。

$ A = \{ 1, 2, 3 \} $上の関係$ R $を$ \{ (1,1), (1,2), (2,1), (2,2), (3,3) \} $とすると、$ 1R1, 1R2, 2R1, 2R2, 3R3 $であるが、$ 1R3, 2R3, 3R1, 3R2 $ではない。

$ \mathbb{R} $上の関係$ L $を$ \{ (x,y) \mid x \leq y \} $で定義する。このとき$ xLy $と$ x \leq y $は同値である。

$ \mathbb{R} $上の関係$ E $を$ \{ (x,x) \mid x \in \mathbb{R} \} $で定義する。このとき$ xRy $と$ x = y $は同値である。

第3節全順序集合

集合$ T $とその上の関係$ R $の組$ \langle T , R \rangle $が全順序集合であるとは、$ R $が次の性質を満たすことである。

どんな$ x \in T $に対しても、$ xRx $が成り立つ。(反射性)
「$ xRy $ かつ $ yRx $」ならば、「$ x=y $」。(反対称性)
「$ xRy $ かつ $ yRz $」ならば、「$ xRz $」。(推移性)
どんな$ x,y \in T $に対しても、$ xRy $と$ yRx $の少なくとも一方が成り立つ。(比較可能性)

全順序集合とは、$ \langle T , R \rangle $という組のことであって、$ T $そのものや$ R $そのものを指しているわけではない。

以下に例を示す。

$ A = \{ 1, 2, 3 \} $上の関係$ B $を$ \{ (1,1), (1,2), (2,1), (2,2), (3,3) \} $とすると、$ B $は反射性と推移性を満たすが、反対称性と比較可能性は満たしていないので、$ \langle A , B \rangle $は全順序集合ではない。

$ T = \{ R, P, S \} $上の関係$ M $を$ \{ (R,R), (R,P), (P,P), (P,S), (S,S), (S,R) \} $とすると、$ M $は反射性、反対称性、比較可能性を満たすが、推移性は満たしていないので、$ \langle T , M\rangle $は全順序集合ではない。

$ A = \{ 1, 2, 3 \} $上の関係$ C $を$ \{ (1,1), (2,1), (2,2), (3,1), (3,2), (3,3) \} $とすると、$ C $は反射性、反対称性、推移性、比較可能性の全てを満たすので、$ \langle A , C \rangle $は全順序集合である。

$ \mathbb{R} $上の関係$ L $を$ \{ (x,y) \mid x \leq y \} $とすると、$ L $は反射性、反対称性、推移性、比較可能性の全てを満たすので、$ \langle \mathbb{R} , L \rangle $は全順序集合である。

全順序集合は$ \leq $や$ \geq $に似たものだと思えばわかりやすい。実際、3番目の例は$ \geq $、4番目の例は$ \leq $に対応している。

しかし、全順序集合はすべて$ \leq, \geq $になるかというとそうではない。実際、$ \mathbb{N} $上の関係$ R $を次のように定義すると、$ \langle \mathbb{N}, R \rangle $は全順序集合である。

$$ \{ (x,y) \mid 「y = 0」または「x \neq 0 かつ x \leq y」 \} $$

この関係は、$ 1R2, 2R3, 3R4, \cdots $かつ$ 1R0, 2R0, 3R0, \cdots $という式を満たす。すなわち、「基本的には普通の大小関係だが、$ 0 $だけは例外的に一番大きいとみなす」という大小関係における$ \leq $の関係であると言える。すなわち、次のような序列が成り立っている。

$$ 1R2R3R4 \cdots \cdots R0 $$

奇妙な例だが、$ S = \{ \emptyset\}, T = \{ \emptyset, \{ \emptyset\} \} $とおき、$ V = \{ \emptyset, S, T\}, R = \{ (A, B) \mid A \in B \} $とすると、$ \langle V, R \rangle $は全順序集合になる。この例は後々重要になる。実際、この$ V $は順序数である。このことは後で確認する。

$ \geq $は「要素の符号を反転させたときの$ \leq $」とみなせるので、以下では全順序集合の関係として$ \leq $のようなものを想定する。しかし、$ \geq $も全順序集合の関係になりうることに注意されたい。

第4節整列集合

全順序集合$ \langle T, R \rangle $が整列集合であるとは、どんな$ T $の$ \emptyset $ではない部分集合$ S $に対しても、その中に「どんな$ s \in S $に対しても$ m R s $となるような$ m $」が存在することである。

もし$ R $を$ \leq $だと思えば、「」内は単に「$ S $の最小値」と言い換えられる。

「$ \emptyset $ではない」という条件は「空集合に最小値がないのは当たり前である」ということを表しているだけであり、整列集合の条件は「$ T $の要素が1個以上集まればその中には必ず最小値がある」と言い換えることもできる。

以下に例を示す。

$ A = \{ 1, 2, 3 \} $上の関係$ X $を$ \{ (1,1), (1,2), (1,3), (2,2), (2,3), (3,3) \} $とすると、$ a X b $は$ a \leq b $と同値であり、$ \emptyset $ではない$ A $のどんな部分集合に対しても最小値が存在するので、$ \langle A, X \rangle $は全順序集合である。

$ \mathbb{R} $上の関係$ L $を$ \{ (x,y) \mid x \leq y \} $とすると、$ aLb $は$ a \leq b $と同値であるが、$ \mathbb{R} $の部分集合の中には$ \emptyset $ではなくて最小値が存在しないものが存在するので、$ \langle \mathbb{R}, L \rangle $は全順序集合ではない。

実際、$ \mathbb{N} $上の関係$ R $を$ \{ (x,y) \mid 「y = 0」または「x \neq 0 かつ x \leq y」 \} $とすると、$ a R b $は$ a \leq b $と同値ではないが、$ \mathbb{N} $のどんな$ \emptyset $ではない部分集合にも$ 1R2R3R4 \cdots \cdots R0 $という特殊な大小関係の下での最小値は存在するので、全順序集合である。

第5節推移的集合

集合$ A $が推移的集合であるとは、$ A $の全ての要素がそれ自体$ A $の部分集合であることである。「要素がそれ自体部分集合」とはいささか奇妙だが、以下の例を見れば納得するだろう。

$ \{ \emptyset \} $は推移的集合である。なぜなら、$ \{ \emptyset \} $の要素$ \emptyset $は$ \{ \emptyset \} $の部分集合だからである(どんな集合に対しても$ \emptyset $はその部分集合となることに注意しよう)。

$ \{ \{ \emptyset \} \} $は推移的集合でない。なぜなら、$ \emptyset $ は$ \{ \{ \emptyset \} \} $の要素ではなく、したがって$ \{ \{ \emptyset \} \} $の要素$ \{ \emptyset \} $は$ \{ \{ \emptyset \} \} $の部分集合ではないからである。

$ \{ \emptyset, \{\emptyset\}, \{\{\emptyset\}\} \} $は推移的集合である。証明は読者への演習問題とする。

特殊な例として、$ \emptyset $がある。$ \emptyset $はそれ自身が推移的集合である。なぜなら、もし「$ \emptyset $の全ての要素がそれ自体$ \emptyset $の部分集合である」が偽だとすると、「$ \emptyset $の要素だが$ \emptyset $の部分集合でないもの」という反例が存在することになるが、そのような反例は存在しないからである。

第6節順序数

集合$ \alpha $が順序数であるとは、$ \alpha $が次の2条件を満たすことである:

$ \alpha $は推移的集合である。
$ \langle \alpha, \{ (\beta, \gamma) \mid \beta, \gamma \in \alpha かつ \beta \in \gamma \} \rangle $は整列集合である。

集合を表すのに小文字を使っているのは、順序数が数のような性質を持つためである。これについては後で触れる。

以下に例を示す。

$ \emptyset $は順序数である。なぜなら、$ \emptyset $は推移的集合であり、$ \langle \alpha, \{ (\beta, \gamma) \mid \beta, \gamma \in \alpha かつ \beta \in \gamma \} \rangle = \langle \emptyset, \emptyset \rangle $であるが、これが整列集合とならないことを示す反例が存在しないためである。このあたりの論理は高校では厳密ではないため、「そういうものだ」と認識してほしい。

要素が$ 1 $個であるような集合であって順序数であるものは$ \{ \emptyset \} $だけである。証明は以下の通りである。もし$ \alpha = \{ \beta \} $が順序数だとすると、推移的集合の性質から$ \beta \subset \alpha $であるが、$ \alpha $の部分集合は$ \emptyset $と$ \alpha $だけである。しかし、$ \alpha = \beta $となるとこれはZFC(数学の基本的なルール)である「正則性公理」に反することが知られているため、$ \alpha = \emptyset $とするしかない。$ \alpha = \{ \emptyset \} $のとき$ \langle \alpha, \{ (\beta, \gamma) \mid \beta, \gamma \in \alpha かつ \beta \in \gamma \} \rangle $は整列集合になっているので、これは唯一の要素が$ 1 $個であるような順序数である。

説明は省略するが、要素が$ 2 $個である順序数は$ \{ \emptyset, \{ \emptyset \} \} $のみであることが知られている。一般に、任意の$ n \in \mathbb{N} $に対し、要素が$ n $個であるような順序数はただ一つ存在する。要素が$ n $個であるような順序数を$ O_n $とすると、$ O_0, \cdots, O_4 $は次のようになる:

$$ O_0 = \emptyset $$

$$ O_1 = \{ \emptyset \} = \{ O_0 \} $$

$$ O_2 = \{ \emptyset, \{ \emptyset \} \} = \{ O_0, O_1 \} $$

$$ O_3 = \{ \emptyset, \{ \emptyset \}, \{ \emptyset, \{ \emptyset \} \} \} = \{ O_0, O_1, O_2 \} $$

$$ O_4 = \{ \emptyset, \{ \emptyset \}, \{ \emptyset, \{ \emptyset \} \}, \{ \emptyset, \{ \emptyset \}, \{ \emptyset, \{ \emptyset \} \} \} \} = \{ O_0, O_1, O_2, O_3 \} $$

一般に、$ n > 0 $であるとき、$ O_n = \{ O_0, \cdots, O_{n-1} \} $であることが知られている。

また、$ n > 1 $であれば、

$$ O_n = \{ O_0, \cdots, O_{n-2}, O_{n-1} \} = \{ O_0, \cdots, O_{n-2} \} \cup \{ O_{n-1} \} = O_{n-1} \cup \{ O_{n-1} \} $$

と「漸化式」のように書ける。また、任意の集合$ A $に対して$ \mathrm{succ}(A) $を$ A \cup \{ A \} $とすれば、これは「$ A $の要素に$ A $自身を追加したもの」という集合になっており、

$$ O_n = \mathrm{succ}(O_{n-1}) $$

と簡潔に書くことができる。

第7節超限順序数

有限集合の順序数は上にあげた$ O_n $だけだが、順序数の中には無限集合であるようなものが存在する。例えば、

$$ O_{\omega} = \{ O_0, O_1, O_2, \cdots \} $$

という集合は順序数である。

無限集合の順序数は他にもある。たとえば、

$$ O_{\omega+1} = \{ O_0, O_1, O_2, \cdots, O_{\omega} \} = O_{\omega} \cup \{ O_{\omega} \} = \mathrm{succ}(O_{\omega})$$

も順序数である。一般に、もし集合$ A $が順序数であれば、$ \mathrm{succ}(A) = A \cup \{ A \} $も順序数である。

$ O_{\omega} $から始めて$ \mathrm{succ} $を繰り返し取ることにより、

$$ O_{\omega}, O_{\omega+1}, O_{\omega+2}, O_{\omega+3}, \cdots $$

という無限列が得られる。さらに、これらのどれよりも大きい

$$ O_{\omega2} = \{ O_0, O_1, O_2, \cdots, O_{\omega}, O_{\omega+1}, O_{\omega+2} \cdots \} $$

も順序数である。もちろん、$ \mathrm{succ}(O_{\omega2}) = O_{\omega2+1} $も順序数だし、$ \mathrm{succ}(O_{\omega2+1}) = O_{\omega2+2} $も順序数である。順序数は、いくら具体例をリストアップしても文字通りの意味で切りがない。

第8節超限帰納法

順序数全体の集まり(これは厳密には集合ではない)を$ \mathrm{Ord} $とすると、$ \mathrm{Ord} $は次のような性質を持つ。逆に、次のような性質を持つ順序数の集まりは$ \mathrm{Ord} $のみである:

$ O_0 = \emptyset \in \mathrm{Ord} $である。
$ \alpha \in \mathrm{Ord} $ならば、$ \mathrm{succ}(\alpha) \in \mathrm{Ord} $である。
$ \alpha $は$ \alpha = \mathrm{succ}(\beta) $の形で書けない順序数で、$ \alpha $未満の$ \beta $が全て$ \mathrm{Ord} $の要素であるとき、$ \alpha $も$ \mathrm{Ord} $の要素である。

この性質を逆に利用し、順序数を次のように3つのグループに分けて考えることが多い。

$ O_0 = \emptyset $
$ \alpha = \mathrm{succ}(\beta) $となるときの$ \alpha $
それ以外

2つ目のグループに入る順序数を後続順序数といい、そうでない順序数を極限順序数という。たとえば、$ O_1, O_2, O_{\omega+1} $などは後続順序数であり、$ O_0, O_{\omega}, O_{\omega2} $などは極限順序数である。

第9節順序数の算術

巨大基数を定義するうえでは直接必要とならないが、順序数に対する直感を深めるために、ここでは順序数の大小比較、足し算、掛け算を定義し、その性質の自然数のそれらとの類似点・相違点を確認する。

1. 順序数の比較

どんな順序数$ \alpha, \beta $に対しても、次の3つのうちのいずれか1つだけが成り立つことが知られている。これを三分律という。

$ \alpha \in \beta $である。
$ \alpha = \beta $である。
$ \alpha \ni \beta $である。

$ \alpha \in \beta $が成り立つとき、$ \alpha $は$ \beta $より小さいとし、$ \alpha < \beta $と書く。$ \leq, >, \geq $に対しても同様に定義する。

自然数との類似点: 自然数$ a, b $に対し、$ O_a < O_b $は$ a < b $の必要十分条件である。また、順序数では$ O_{\alpha_1} > O_{\alpha_2} > O_{\alpha_3} > \cdots $のように徐々に小さくなる順序数を取っていくといつかは必ず$ \emptyset = O_0 $になってそれより小さい順序数が取れなくなるが、自然数でも同様に、徐々に小さくなる自然数を取っていくといつかは必ず最小の自然数$ 1 $^[1]に辿り着いて、それより小さい自然数が取れなくなる。

自然数との相違点: $ O_{\omega} $より小さい順序数は$ O_0, O_1, O_2, \cdots $と無限に存在する。しかし、「それより小さい自然数が無限に存在する自然数」は存在しない。

2. 順序数の加法

順序数$ \alpha, \beta $に対し、$ \alpha + \beta $を次のように定義する。

$ \beta = O_0 = \emptyset $のとき: $ \alpha + O_0 = \beta $
$ \beta = \mathrm{succ}(\gamma) $のとき: $ \alpha + \mathrm{succ}(\gamma) = \succ{\alpha + \gamma} $
それ以外のとき: $ \alpha + \beta = \displaystyle{\lim_{\gamma < \beta}} (\alpha + \beta) $

ただし、最後の式の$ \lim $は$ \gamma < \beta $の範囲での順序数的な意味での極限である。高校数学のように書くなら$ \displaystyle{\lim_{\gamma \rightarrow \beta - 0}} $となるが、順序数とマイナス記号を同時に扱うことはあまりないのでこのような書き方になっている。

以下に例を示す。

$ \begin{align*} & O_3 + O_2 \\ =& O_3 + \mathrm{succ}(O_1) \\ =& \mathrm{succ}(O_3 + O_1) \\ =& \mathrm{succ}(O_3 + \mathrm{succ}(O_0)) \\ =& \mathrm{succ}(\mathrm{succ}(O_3 + O_0)) \\ =& \mathrm{succ}(\mathrm{succ}(O_3)) \\ =& \mathrm{succ}(O_4) \\ =& O_5 \\ \end{align*} $

この例のように、自然数$ a, b $に対して$ O_a + O_b = O_{a+b} $が成り立つことが知られている。

$ \begin{align*} & O_{\omega} + O_1 \\ =& O_{\omega} + \mathrm{succ}(O_0) \\ =& \mathrm{succ}(O_{\omega} + O_0) \\ =& \mathrm{succ}(O_{\omega}) \\ =& O_{\omega+1} \end{align*} $

これが$ \mathrm{succ}(\omega) $を$ O_{\omega+1} $と表記する理由である。

$ \begin{align*} & O_1 + O_{\omega} \\ =& \lim_{\gamma < \omega} (O_1 + \gamma) \\ \end{align*} $

これは$ O_1+O_0=O_1, O_1+O_1=O_2, O_1+O_2=O_3, \cdots $のという列の極限である。すなわち、自然数$ 1, 2, 3, \cdots $の極限が$ +\infty $であるのと同様にして、順序数$ O_1, O_2, O_3, \cdots $の極限は$ O_{\omega} $となる。すなわち、

$$ O_{\omega} + O_1 = O_{\omega+1} \neq O_{\omega} = O_1 + O_{\omega} $$

である。

$ \begin{align*} & O_{\omega} + O_{\omega} \\ =& \lim_{\gamma < \omega} (O_{\omega} + \gamma) \\ \end{align*} $

これは$ O_{\omega}+O_0=O_{\omega}, O_{\omega}+O_1=O_{\omega+1}, O_{\omega}+O_2=O_{\omega+2}, \cdots $のという列の極限である。すなわち、

$$ O_{\omega} + O_{\omega} = O_{\omega2} $$

である。ある意味で、$ O_{\omega2} $は「無限よりさらに大きい無限」であると言える。

自然数との類似点: 自然数$ a, b $に対し、$ a+b=c $とすると、$ O_a + O_b = O_c $が成り立つ。

自然数との相違点: どんな自然数$ a, b $に対しても$ a + b = b + a $であるが、どんな順序数$ \alpha, \beta $に対しても$ \alpha + \beta = \beta + \alpha $が成り立つとは限らない。

3. 順序数の乗法

順序数$ \alpha, \beta $に対し、$ \alpha \cdot \beta $を次のように定義する。

$ \beta = O_0 = \emptyset $のとき: $ \alpha \cdot O_0 = O_0 $
$ \beta = \mathrm{succ}(\gamma) $のとき: $ \alpha \cdot \mathrm{succ}(\gamma) = \alpha \cdot \gamma + \alpha $
それ以外のとき: $ \alpha \cdot \beta = \displaystyle{\lim_{\gamma < \beta}} (\alpha \cdot \beta) $

加法の定義と同じように、3つに分けて定義されている。$ \beta $が極限順序数であるときの定義は加法と全く同じである。加法と乗法以外にも極限順序数に対して同様の定義を行っているものは多いが、ここでは触れないことにする。

以下に例を示す。

$ \begin{align*} & O_3 \cdot O_2 \\ =& O_3 \cdot \mathrm{succ}(O_1) \\ =& O_3 \cdot O_1 + O_3 \\ =& O_3 \cdot \mathrm{succ}(O_0) + O_3 \\ =& (O_3 \cdot O_0 + O_3) + O_3 \\ =& (O_0 + O_3) + O_3 \\ =& O_3 + O_3 \\ =& O_6 \\ \end{align*} $

この例のように、自然数$ a, b $に対して$ O_a \cdot O_b = O_{a \cdot b} $が成り立つことが知られている。

$ \begin{align*} & O_{\omega} \cdot O_2 \\ =& O_{\omega} \cdot \mathrm{succ}(O_1) \\ =& O_{\omega} \cdot O_1 + O_{\omega} \\ =& O_{\omega} \cdot \mathrm{succ}(O_0) + O_{\omega} \\ =& (O_{\omega} \cdot O_0 + O_{\omega}) + O_{\omega} \\ =& (O_0 + O_{\omega}) + O_{\omega} \\ =& O_{\omega} + O_{\omega} \\ =& O_{\omega2} \\ \end{align*} $

$ \cdot $の左側が極限順序数であっても、右側が後続順序数であれば、2つ目のルールが適用される。

$ \begin{align*} & O_2 \cdot O_{\omega} \\ =& \lim_{\gamma < \omega} (O_2 \cdot \gamma) \\ \end{align*} $

これは$ O_2 \cdot O_0=O_0, O_2 \cdot O_1=O_2, O_2 \cdot O_2=O_4, \cdots $のという列の極限である。すなわち、整数$ 0, 2, 4, \cdots $の極限が$ +\infty $であるのと同様にして、順序数$ O_0, O_2, O_4, \cdots $の極限は$ O_{\omega} $となる。すなわち、

$$ O_{\omega} \cdot O_2 = O_{\omega2} \neq O_{\omega} = O_2 \cdot O_{\omega} $$

である。

自然数との類似点: 自然数$ a, b $に対し、$ a \cdot b=c $とすると、$ O_a \cdot O_b = O_c $が成り立つ。

自然数との相違点: どんな自然数$ a, b $に対しても$ a \cdot b = b \cdot a $であるが、どんな順序数$ \alpha, \beta $に対しても$ \alpha \cdot \beta = \beta \cdot \alpha $が成り立つとは限らない。

以上のことから、自然数$ a $に対して$ O_a $は$ a $と同じような性質を持つことが分かった。そこで、今まで$ O_{\alpha} $と書いていたものを単に$ \alpha $と書くことにする。たとえば、

$$ O_1 = 1, O_2 = 2, O_0 = 0, O_{\omega} = \omega, O_{\omega+1} = \omega+1, O_{\omega2} = \omega2 $$

のように書く。

$ 0 $および自然数の範囲内では整数と順序数で計算の結果は全く同じになるから、このような同一視を行っても問題ない。また以下でも、順序数がもともと集合であったことを強調するために$ O_{\alpha} $という表記を使うことがある。

第1¼章全射・単射・全単射

ここでは一旦順序数から離れ、全射・単射・全単射の概念に触れる。

第0節写像

高校数学では「入力が実数で出力も実数」の関数を考えることが多いが、ここではその入力と出力を別の集合にすることを考える。例えば「入力が$ \{ a, b, c \} $で出力が$ \{ 1, 2, 3 \} $」の関数$ f $を

$$ f(a) = 2, f(b) = 1, f(c) = 3 $$

のように定義すれば、これは1つの関数になっている。あるいは、高校数学では$ y = \sqrt{x} $という関数を扱うが、これは$ x < 0 $では定義されない。すなわち、$ y = \sqrt{x} $は「入力が$ \{ x \mid x \geq 0 \} $で出力が$ \mathbb{R} $」の関数だと思えばよい。

「出力は$ \{ y \mid y \geq 0 \} $ではないのか?」と思った人もいるだろう。しかし、出力と値域は必ずしも一致しなくてもよい。出力は単に「$ y = \sqrt{x} $の$ y $をどのように扱うか」を表すものであり、出力全体が値域に対応している必要はない。

大学の数学用語に合わせるため、入力のことを定義域、出力のことを終域と呼ぶことにする。上で述べたとおり、終域と値域は異なる概念である。

第1節全射

定義域が$ A $、終域が$ B $であるような関数$ f $が全射であるとは、$ y \in B$を定数としたときの$ x $の方程式

$$ y = f(x) $$

が$ x \in A $の範囲に必ず1個以上の解を持つことである。

たとえば、$ A = \mathbb{R}, B = \mathbb{R}, f(x) = x^3-3x $のとき、どのような$ y \in \mathbb{R} $に対しても$ x^3 - 3x = y $は実数解を持つ。したがって、$ f(x) = x^3 - 3x $は全射である。

同じ関数であっても、定義域と終域によって全射になったりならなかったりする。

$ y = \sqrt{x} $を考える。定義域は$ \{ x \mid x \geq 0 \} $である。もし終域が$ \mathbb{R} $であれば、これは全射ではない。なぜなら、$ \sqrt{x} = -1 $は定義域すなわち$ \{ x \mid x \geq 0 \} $の範囲に解を持たないからである。

しかし、終域を$ \{ y \mid y \geq 0 \} $とすれば、これは全射となる。なぜなら、$ y \geq 0 $を満たすどんな$ y $についても$ y = \sqrt{x} $は解を持つ($ x = y^2 $が解である)からである。この場合、$ y = -1 $は終域に含まれていないので、考えている$ y $の範囲から除外されている。

第2節単射

定義域が$ A $、終域が$ B $であるような関数$ f $が全射であるとは、$ y \in B$を定数としたときの$ x $の方程式

$$ y = f(x) $$

が$ x \in A $の範囲に必ず1個以下(0個でもよい)の解を持つことである。

たとえば、$ A = \mathbb{R}, B = \mathbb{R}, f(x) = x^3-3x $のとき、$ y = 0 $に対して$ x^3 - 3x = 0 $は異なる3つの実数解を持つ。したがって、$ f(x) = x^3 - 3x $は単射ではない。

一方、$ A = \{ x \mid x \geq 1 \}, B = \mathbb{R}, f(x) = x^3-3x $とすると、これは単射である。なぜなら、どんな実数$ y $に対しても$ x^3 - 3x = y $は定義域すなわち$ x \geq 1 $の範囲に実数解を最大でも1個しか持たないからである。証明は読者の演習問題とする(実際にグラフを描くとこのことは明らかになる)。

$ y = \sqrt{x} $の定義域は$ \{ x \mid x \geq 0 \} $である。終域が$ \mathbb{R} $であっても$ \{ y \mid y \geq 0 \} $であっても、これは単射である。

第3節全単射

定義域が$ A $、終域が$ B $であるような関数$ f $が全単射であるとは、$ f $が全射かつ単射であることである。すなわち、$ y \in B$を定数としたときの$ x $の方程式

$$ y = f(x) $$

が$ x \in A $の範囲に必ずちょうど1個の解を持つことである。

たとえば、$ A = \mathbb{R}, B = \mathbb{R}, f(x) = x^3-3x $のとき、$ f $は全射であるが単射ではないので、全単射ではない。

$ y = \sqrt{x} $の定義域は$ \{ x \mid x \geq 0 \} $である。もし終域が$ \mathbb{R} $であれば、これは単射であるが全射ではないので、全単射ではない。一方、もし終域が$ \{ y \mid y \geq 0 \} $であれば、これは全射かつ単射であるので、全単射である。

$ A = \mathbb{R}, B = \mathbb{R}, f(x) = -x^3 $のとき、$ f $は全単射である。証明は読者への演習問題とする。

第1½章集合の濃度

集合の濃度とは、直感的にはその集合の「要素の個数」のことであるが、単なる「要素の個数」とは異なり、無限集合にも定義される。

第1節有限集合の濃度

有限集合の濃度は、その集合の要素の個数と同じである。以下に例を示す。

$ \{ 1, 3, 5 \} $の濃度は$ 3 $である。
$ \{ a, b, c, \cdots, z \} $の濃度は$ 26 $である。
$ \emptyset $の濃度は$ 0 $である。
$ \{ \emptyset \} $の濃度は$ 1 $である。

下から2番目の例は空集合である。空集合には要素が存在しないので、「要素が$ 0 $個ある」と考えると、空集合の濃度は$ 0 $であることがわかる。

一方、一番下の例は「空集合のみを要素に持つ集合」である。この集合には空集合という要素が$ 1 $個あるので、その濃度は$ 0 $ではなく$ 1 $である。

以下は、濃度に関する当然だが重要な事実である。$ A, B $は有限集合とする。

$ A $を定義域、$ B $を終域とする全射が存在するとき、$ A $の濃度は$ B $の濃度以上である。
$ A $を定義域、$ B $を終域とする単射が存在するとき、$ A $の濃度は$ B $の濃度以下である。
$ A $を定義域、$ B $を終域とする全単射が存在するとき、$ A $の濃度は$ B $の濃度と等しい。

第2節無限集合の濃度

「正の偶数全体の集合」と「自然数全体の集合」ではどちらが要素が多いだろうか? 「正の偶数全体の集合」は「自然数全体の集合」の真部分集合(それ自身でない集合)であるから、「自然数全体の集合」の方が多いように見える。しかし、「正の偶数全体の集合」から「自然数全体の集合」への関数$ f $を

$$ f(x) = 2x $$

とすると、これは全単射である。全単射が存在するということは、濃度は同じでなければならない。有限集合の場合は、「全単射が存在するとき、濃度が等しい」は濃度に関する性質であったが、無限集合の場合は逆にこれを定義とする。濃度の以上、以下の関係についても同様に定める。すなわち、無限集合$ A, B $に対して

$ A $を定義域、$ B $を終域とする全射が存在するとき、$ A $の濃度は$ B $の濃度以上である。
$ A $を定義域、$ B $を終域とする単射が存在するとき、$ A $の濃度は$ B $の濃度以下である。
$ A $を定義域、$ B $を終域とする全単射が存在するとき、$ A $の濃度は$ B $の濃度と等しい。

が成り立つように無限集合の濃度を定義する。このように定義すると、きちんと濃度の「等しい」「以上」「以下」が自然数の大小関係に似た性質を持つ、すなわち濃度に大小関係があるとみなせることが知られている。

最小の無限集合の濃度は$ \mathbb{N} $の濃度である。その濃度を$ \aleph_0 $(アレフ・ゼロ)と書く。

整数全体の集合$ \mathbb{Z} $の濃度は$ \aleph_0 $である。これは、次のような$ \mathbb{N} $と$ \mathbb{Z} $の間の全単射が存在することからわかる:

$$ f(0) = 0, f(1) = +1, f(2) = -1, f(3) = +2, f(4) = -2, \cdots $$

これよりも複雑な全単射を用いることで、有理数全体の集合$ \mathbb{Q} $の濃度も$ \aleph_0 $であることが知られている。

一方、$ \mathbb{R} $の濃度は$ \mathbb{N} $の濃度より大きい(すなわち等しくない)ことが知られている。$ \mathbb{R} $の濃度を連続体濃度といい$ \mathfrak{c} $で表す。

第1¾章カントールの対角線論法

第1節連続体濃度

連続体濃度は$ \aleph_0 $ではないことが知られている。この節では、このことを背理法で証明する。

そのために、連続体濃度が$ \aleph_0 $であると仮定する。すなわち、$ \mathbb{N} $と$ \mathbb{R} $の濃度が同じ、すなわち$ \mathbb{N} $から$ \mathbb{R} $への全単射が存在すると仮定する。そのような全単射をひとつとり$ f $とする。$ f $の値を次のようにリストアップする。ただし、右辺は実数の十進数表記である:

\begin{align*} f(0) =& \pm a_{00}.a_{01}a_{02}a_{03} \cdots \\ f(1) =& \pm a_{10}.a_{11}a_{12}a_{13} \cdots \\ f(2) =& \pm a_{20}.a_{21}a_{22}a_{23} \cdots \\ f(3) =& \pm a_{30}.a_{31}a_{32}a_{33} \cdots \\ \vdots& \end{align*}

ここで、実数$ r' $を以下の方法で構成する:

$ r' $の符号は$ + $とする。
$ r' $の整数部分は、$ a_{00} $と異なる数にする。
$ r' $の小数第$ n $位は、$ 0, 9, a_{nn} $のどれとも異なる数にする。すなわち、$ r' $の小数第$ n $位が$ f(n) $の小数第$ n $位と異なるようにする。$ 0, 9 $を排除したのは、$ 0.999\cdots = 1.000\cdots $という問題を避けるためである。

このように構成した$ r' $に対して方程式$ f(x) = r' $を考えると、$ x = 0 $は解ではない。なぜなら、両辺の整数部分が異なるからである。また、任意の自然数$ n $に対して、$ x = n $は解ではない。なぜなら、両辺の小数第$ n $位が異なるからである。

したがって、$ f(x) = r' $は解を持たず、これは$ f $が全単射であることに矛盾する。

よって、背理法により、連続体濃度は$ \aleph_0 $ではないことが示された。

第2節冪集合

集合$ A $の冪集合$ \mathcal{P}(A) $を、$ A $の部分集合全体の集合と定義する。以下に例を示す。

$$ \mathcal{P}(\emptyset) = \{ \emptyset \} $$

$$ \mathcal{P}(\{ X \}) = \{ \emptyset, \{ X \} \} $$

$$ \mathcal{P}(\{ a, b \}) = \{ \emptyset, \{ a \}, \{ b \}, \{ a, b \} \} $$

$$ \mathcal{P}(\{ 1, 2, 3 \}) = \{ \emptyset, \{ 1 \}, \{ 2 \}, \{ 1, 2 \}, \{ 3 \}, \{ 1, 3 \}, \{ 2, 3 \}, \{ 1, 2, 3 \} \} $$

数学Aの「集合と論理」では、「$ A = \{a, b \} $の部分集合を全て書け」のような問題があるが、冪集合はそのような問題の答えの両端に$ \{ $と$ \} $を付けたものだと考えるとわかりやすいだろう。

もちろん、$ \mathcal{P}(A) $は無限集合に対しても定義される。例えば、

$$ \{ 1, 3, 25 \} \in \mathcal{P}(\mathbb{N}) $$

$$ \{ x \mid xは正の偶数 \} \in \mathcal{P}(\mathbb{N}) $$

$$ \left\{ \frac{a+b\sqrt{5}}{2} \mid a, b は整数 \right\} \in \mathcal{P}(\mathbb{R}) $$

である。$ \mathcal{P}(A) $は「$ A $の部分集合をすべて集めた集合」なので、$ \subset $ではなく$ \in $であることに注意せよ。

また、$ \mathcal{P}(\mathbb{N}) $の濃度は$ \mathbb{R} $の濃度と等しいことが知られている。

第3節カントールの対角線論法

出典: 高校数学の美しい物語「カントールの定理の証明と対角線論法」

ここでは、任意の集合$ A $に対し、$ \mathcal{P}(A) $の濃度が$ A $の濃度より大きいことを示す。

「$ A $を定義域、$ \mathcal{P}(A) $を終域とする関数」を考える。これは、$ A $の要素を入力すると、$ A $の部分集合が出力される関数だと思えばよい。

$ A $を定義域、$ \mathcal{P}(A) $を終域とする関数$ f $を$ f(a) = \{ a \} $とすると、これは単射である。したがって、$ A $の濃度は$ \mathcal{P}(A) $の濃度以下である。

$ A $の濃度が$ \mathcal{P}(A) $の濃度と等しくないことを背理法で示す。そのために、等しいと仮定する。このとき、$ A $を定義域、$ \mathcal{P}(A) $を終域とする全単射$ g $が存在する。

このとき、次のような$ A $の部分集合を考える:

$$ B = \{ b \in A | b \not \in g(b) \} $$

$ b $は$ A $の要素、 $ g(b) $は$ A $の部分集合であるから、$ b \in g(b) $という命題が意味を持つ。この命題が偽であるような$ b $だけを集めて作った$ A $の部分集合が$ B $である。

$ g $は全単射であるから、$ g(a) = B $を満たす$ a \in A $が存在する。$ B $は$ A $の部分集合なので、$ a \in B $または$ a \not \in B $のどちらかが成り立つ。しかし、その両方が成り立たないことを示す。

$ a \in B = g(a) $であるとすれば、$ a $は$ a \not \in g(a) $を満たさないので$ B $の要素ではない。したがって、$ a \in B $はありえない。

$ a \not \in B = g(a) $であるとすれば、$ a $は$ a \not \in g(a) $を満たすので$ B $の要素ではない。したがって、$ a \not \in B $もありえない。

これは矛盾である。矛盾が生じたので、$ A $の濃度が$ \mathcal{P}(A) $の濃度と等しくないことが示された。

以上より、任意の集合$ A $に対し、$ \mathcal{P}(A) $の濃度が$ A $の濃度より大きいことが示された。

第4節一般連続体仮説

$ \aleph_0 $は最も小さい無限集合の濃度であった。無限集合の濃度は順序数に沿って並べることができ、小さい方から

$$ \aleph_0, \aleph_1, \aleph_2, \cdots, \aleph_{\omega}, \aleph_{\omega+1}, \cdots, \aleph_{\omega2} \cdots \cdots $$

と並ぶ。

ここで、次の問題を考える:

任意の無限集合$ A $に対し、$ A $の濃度と$ \mathcal{P}(A) $の濃度の間の濃度は存在しないといえるか?

この問題は、ZFCと呼ばれる通常の数学の枠組みでは解けない(YESであることもNOであることも証明できない)ことが知られている。

そこで、この問題の答えがYESであるという命題を一般連続体仮説と呼び、この記事ではそれを信じることにする。「信じる」というのは数学的ではないかもしれないが、そもそも何も信じなければ数学を始められないので、一般連続体仮説を信じることにする。

このとき、次の命題が成り立つ:

もし無限集合$ A $の濃度が$ \aleph_{\alpha} $であれば、$ \mathcal{P}(A) $の濃度は$ \aleph_{\mathrm{succ}(\alpha)} $である。

第2章基数と共終数

第1節基数

順序数$ \kappa $が基数であるとは、すべての$ \alpha < \kappa $に対して$ \alpha $と$ \kappa $の間に全単射が存在しないことを言う。

同じことであるが、基数とは「濃度が同じ中で最小の順序数」であるといえる。

たとえば、有限の整数$ n $に対応する順序数$ O_n $は全て基数である。なぜなら、濃度が$ n $であるような順序数は$ O_n $しかないからである。

一方、$ O_{\omega} $は基数であるが、$ O_{\omega + 1} $は基数ではない。なぜなら、$ O_{\omega} = \{ O_0, O_1, O_2, \cdots \} $から$ O_{\omega + 1} = \{ O_0, O_1, O_2, \cdots, O_{\omega} \} $への全単射として

$$ f(O_0) = O_{\omega}, f(O_1)=O_0, f(O_2)=O_1, \cdots, f(O_n)=O_{n-1}, \cdots (n \geq 1) $$

が存在するからである。同様に、$ O_{\omega+2}, O_{\omega2} $なども基数ではない。

[大草の炒め物を挿入]

[共終数の定義と例を挿入]

第3章到達不能基数

[到達不能基数の定義を挿入]

[ZFCとの独立性に関する言及を挿入]

脚注

↑ この記事は高校数学を仮定している。そのため、$ 0 $は自然数ではなく、$ 1 $が最小の自然数である。$ \mathbb{N} $という記号の定義に「自然数」を用いていないため、$ 0 $が自然数でないことと$ 0 \in \mathbb{N} $であることが両立することに注意せよ。

[1] この記事は高校数学を仮定している。そのため、\( 0 \)は自然数ではなく、\( 1 \)が最小の自然数である。\( \mathbb{N} \)という記号の定義に「自然数」を用いていないため、\( 0 \)が自然数でないことと\( 0 \in \mathbb{N} \)であることが両立することに注意せよ。

[1]

利用者:Nayuta Ito/高校数学から巨大基数まで最速でたどる

目次

第0章 記号の定義

第1章 順序数の定義

第1節 直積

第2節 関係

第3節 全順序集合

第4節 整列集合

第5節 推移的集合

第6節 順序数

第7節 超限順序数

第8節 超限帰納法

第9節 順序数の算術

1. 順序数の比較

2. 順序数の加法

3. 順序数の乗法

第1¼章 全射・単射・全単射

第0節 写像

第1節 全射

第2節 単射

第3節 全単射

第1½章 集合の濃度

第1節 有限集合の濃度

第2節 無限集合の濃度

第1¾章 カントールの対角線論法

第1節 連続体濃度

第2節 冪集合

第3節 カントールの対角線論法

第4節 一般連続体仮説

第2章 基数と共終数

第1節 基数

第3章 到達不能基数

脚注

第0章記号の定義

第1章順序数の定義

第1節直積

第2節関係

第3節全順序集合

第4節整列集合

第5節推移的集合

第6節順序数

第7節超限順序数

第8節超限帰納法

第9節順序数の算術

第1¼章全射・単射・全単射

第0節写像

第1節全射

第2節単射

第3節全単射

第1½章集合の濃度

第1節有限集合の濃度

第2節無限集合の濃度

第1¾章カントールの対角線論法

第1節連続体濃度

第2節冪集合

第3節カントールの対角線論法

第4節一般連続体仮説

第2章基数と共終数

第1節基数

第3章到達不能基数