利用者: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 \} $$
という集合は順序数である。