超限順序数
https://gyazo.com/b99310451ccd30e690f4212462b6a486
整列集合
$ (A, <_{A})
Aに含まれる全ての要素は$ <_{A}によって比較できる
$ \forall x, y ((x <_{A} y) \lor (y <_{A} x))
Aの要素の中に他のどの要素より"小さい"要素（＝最小元）がただ1つ存在する
$ \exists x \forall y ((x <_{A} y) \lor (x = y))
要は小さいものから順番に一列に並べられる物の集合
比較方法も任意に定義できる
例
({1,2,3},<)
({バナナ,みかん,りんご},辞書順)
順序数の定義
$ ord(A, <_{A}) = ran(G)
$ G(a) = \{G(x)|x<_{A}a\}
整列集合を小さい順に並べる
1つ目（最小元）を空集合とする
2つ目は空集合のみを要素とする集合
という感じで再帰的にn個目はnより小さいものの集合となる
例
$ ord(\{0, 2, 5\}, <)
$ G(0) = \{\} = \emptyset
$ G(2) = \{G(0)\} = \{\emptyset\}
$ G(5) = \{G(0), G(2)\} = \{\emptyset, \{\emptyset\}\}
$ \therefore ord(\{0,2,5\},<) = \{G(0), G(2), G(5)\} = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}
イメージとしては集合を小さい順に並べて順番に通し番号を付けていく感じ
上記定義により順序数は自分より小さい順序数全ての集合となる
実際の順序数
$ 0 := \{\} = \emptyset
$ 1 := \{0\} = \{\emptyset\}
$ 2 := \{0, 1\} = \{\emptyset, \{\emptyset\}\}
$ 3 := \{0, 1, 2\} = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}
順序数における"次の数"
自然数において"次の数"は重要
全ての自然数は必ず"次の数"を持つ
順序数では「自身」に「自身」を要素として追加すると"次の数"になる
$ n+1 = n \cup \{n\}
順序数の大小
$ a < b \Leftrightarrow a \in b
超限順序数
$ \omega := \mathbb{N} = \{0,1,2,\cdots\}
「全ての自然数」という集合を順序数とすると、その数は「全ての自然数より大きい」ということになる
これをωと呼ぶ
ωの「次の数」も存在する
$ \omega + 1 = \omega \cup \{\omega\} = \{0,1,2,\cdots, \omega\}
$ \omega + 2 = (\omega+1) \cup \{(\omega+1)\} = \{0,1,2,\cdots, \omega, (\omega + 1)\}
$ \omega + 3 = (\omega+2) \cup \{(\omega+2)\} = \{0,1,2,\cdots, \omega, (\omega + 1), (\omega + 2)\}
有限の枠を超えた大きさを持つ順序数を超限順序数と呼ぶ
ωは有限の数しか含んでいないのでωは一番小さい超限順序数と言える
⇔ ω以外の超限順序数は必ずωを含んでいる
極限順序数とも言う
順序数の加算
$ \alpha + \betaを考える
$ \alpha = ord(A, <_{A}), \beta = ord(B, <_{B}), A \cap B = \emptysetとなるような適当な$ A,<_{A},B,<_{B}を仮定する
$ x <_{AB} y \Leftrightarrow (x<_{A}y) \lor (x<_{B}y) \lor (x \in A \land y \in B)
$ \alpha + \beta := ord(A \cup B, <_{AB})
イメージとしては足される数の列の後ろに足す数の列を連ねていく感じ
$ 2+3 \rightarrow \{0_{A}, 1_{A}\}+\{0_{B}, 1_{B}, 2_{B}\} \rightarrow \{0_{A}, 1_{A}, 0_{B}, 1_{B}, 2_{B}\} \rightarrow \{0, 1, 2, 3, 4\} = 5
$ \omega + 1 \rightarrow \{0_{A}, 1_{A}, 2_{A}, \cdots \} + \{0_{B}\} \rightarrow \{0_{A}, 1_{A}, 2_{A}, \cdots , 0_{B}\} \rightarrow \{0,1,2,\cdots,\omega\}=\omega+1
$ 1 + \omega \rightarrow \{0_{A}\} + \{0_{B}, 1_{B}, 2_{B}, \cdots \} \rightarrow \{0_{A}, 0_{B}, 1_{B}, 2_{B}, \cdots \} \rightarrow \{0,1,2,3,\cdots\}=\omega
超限順序数では足し算の順序によって答えが変わることがある
順序数の乗算
$ \alpha \cdot \betaを考える
$ \left<x_{1}, y_{1}\right> <_{AB} \left<x_{2}, y_{2}\right> \Leftrightarrow y_{1} < y_{2} \lor (y_{1} = y_{2} \land x_{1} < x_{2})
$ \alpha \cdot \beta := ord(\{\left<x,y\right>|x \in \alpha, y \in \beta\}, <_{AB})
イメージとしては掛けられる数を掛ける数の分並べる、足し算を繰り返す感じ
$ 2 \cdot 3 = \{0,1\} \cdot \{0,1,2\} \rightarrow \{\left<0,0\right>, \left<1,0\right>, \left<0,1\right>, \left<1,1\right>, \left<0,2\right>, \left<1,2\right>\} \rightarrow \{0,1,2,3,4,5\} = 6
$ \omega \cdot 2 = \{0,1,2,\cdots\}\cdot\{0,1\} \rightarrow \{\left<0,0\right>, \left<1,0\right>, \left<2,0\right>, \cdots, \left<0,1\right>, \left<1,1\right>, \left<2,1\right>, \cdots\}
$ \rightarrow \{0,1,2,\cdots,\omega,(\omega+1),(\omega+2),\cdots\}=\omega+\omega=\omega\cdot2
$ 2\cdot\omega=\{0,1\}\cdot\{0,1,2,\cdots\}\rightarrow\{\left<0,0\right>, \left<1,0\right>, \left<0,1\right>, \left<1,1\right>, \left<0,2\right>, \left<1,2\right>, \cdots\}\rightarrow\{0,1,2,3,4,5,\cdots\}=\omega
超限順序数では掛け算も順序によって答えが変わることがある
順序数の冪乗
$ \alpha^{\beta}を考える
$ F(\alpha, \beta) = \{f \in \mathscr{F}(\alpha, \beta) | f(b) \neq 0を満たすような$ bが有限個しかないもの$ \}
（補足1）配置集合（集合の冪）というものがあり、$ \mathscr{F}(A,B)のように表す
この$ \mathscr{F}(A,B)は「BからAへの写像全ての集合」という意味になる
つまりBの全ての要素について f(b)=a となるような要素 a がただ一つ決まる関数全て
本当は$ A^{B}とも書くのだけれど、数としての冪と集合としての冪が紛らわしいので上の表記を利用した
（補足2）どうしてbが有限個のものだけにするかと言うと↓の比較の際に厳密な比較ができないから
無限集合の場合最大か最小のどちらかが定まらない場合がある
順序数の場合は「最大」が決まらない（「最大の自然数」が決められないのと同じ）
だから比較対象を有限に絞る必要がある
$ f <_{AB} g \Leftrightarrow (f \neq g) \land (f(b) \neq g(b)となる最大の$ b\in\betaについて$ f(b)<g(b)
$ \alpha^{\beta} := ord(F(\alpha,\beta),<_{AB})
イメージとしてはβ桁のα進数みたいなもの
具体例（式は雰囲気以下略 あと↑は冪乗を表す演算子です 関数は左を引数右を返り値で書きました）
$ 2^{3} = \{0,1\}\uparrow\{0,1,2\}
$ \rightarrow \{\{(0,0),(1,0),(2,0)\},\{(0,1),(1,0),(2,0)\},\{(0,0),(1,1),(2,0)\},\{(0,1),(1,1),(2,0)\},
$ \{(0,0),(1,0),(2,1)\},\{(0,1),(1,0),(2,1)\},\{(0,0),(1,1),(2,1)\},\{(0,1),(1,1),(2,1)\}\}
$ \rightarrow \{0,1,2,3,4,5,6,7\}=8
$ \omega^{2} = \{0,1,2,\cdots\}\uparrow\{0,1\}
$ \rightarrow\{\{(0,0),(1,0)\},\{(0,1),(1,0)\},\{(0,2),(1,0)\},\cdots,
$ \{(0,0),(1,1)\},\{(0,1),(1,1)\},\{(0,2),(1,1)\},\cdots,
$ \{(0,0),(1,2)\},\{(0,1),(1,2)\},\{(0,2),(1,2)\},\cdots,
$ \cdots\cdots\}=\omega+\omega+\omega+\cdots=\omega\cdot\omega=\omega^{2}
$ 2^{\omega}=\{0,1\}\uparrow\{0,1,2,\cdots\}
$ \rightarrow\{\{(0,0),(1,0),(2,0)\cdots\},\{(0,1),(1,0),(2,0)\cdots\},\{(0,0),(1,1),(2,0)\cdots\},
$ \{(0,1),(1,1),(2,0)\cdots\},\{(0,0),(1,0),(2,1)\cdots\},\cdots\} = \omega
いろいろな超限順序数
$ 0,1,2,\cdots $ \rightarrow \omega $ (1+\omega=\omega)
$ \omega,\omega+1,\omega+2,\cdots$ \rightarrow\omega+\omega=\omega\cdot2
$ \omega,\omega\cdot2,\omega\cdot3,\cdots $ \rightarrow\omega\cdot\omega=\omega^{2} $ (\omega+\omega^2=\omega^2)
$ \omega,\omega^2,\omega^3,\cdots $ \rightarrow\omega^\omega $ (\omega\cdot\omega^\omega=\omega^\omega)
$ \omega,\omega^\omega,\omega^{\omega^\omega},\cdots $ \rightarrow\epsilon_0 $ (\omega^{\epsilon_0}=\epsilon_0)
$ \epsilon_0+1,\epsilon_0+\omega,\epsilon_0+\omega^\omega,\epsilon_0+\omega^{\omega^\omega},\cdots$ \rightarrow\epsilon_0+\epsilon_0=\epsilon_0\cdot2
$ \epsilon_0,\epsilon_0\cdot\omega,\epsilon_0\cdot\omega^\omega,\epsilon_0\cdot\omega^{\omega^\omega},\cdots $ \rightarrow \epsilon_0\cdot\epsilon_0=\epsilon_0^2
$ \epsilon_0,\epsilon_0^\omega,\epsilon_0^{\omega^\omega},\epsilon_0^{\omega^{\omega^\omega}},\cdots $ \rightarrow\epsilon_0^{\epsilon_0}
$ \epsilon_0,\epsilon_0^{\epsilon_0},\epsilon_0^{\epsilon_0^{\epsilon_0}},\epsilon_0^{\epsilon_0^{\epsilon_0^{\epsilon_0}}},\cdots $ \rightarrow\epsilon_1
$ \epsilon_1,\epsilon_1^{\epsilon_1},\epsilon_1^{\epsilon_1^{\epsilon_1}},\epsilon_1^{\epsilon_1^{\epsilon_1^{\epsilon_1}}},\cdots $ \rightarrow\epsilon_2
$ \epsilon_0,\epsilon_1,\epsilon_2,\cdots $ \rightarrow\epsilon_\omega
$ \epsilon_{\omega},\epsilon_{\omega^\omega},\epsilon_{\omega^{\omega^\omega}},\cdots $ \rightarrow\epsilon_{\epsilon_0}
いろいろな超限順序数の演算
$ (\omega+1)^2=(\omega+1)\cdot(\omega+1)=(\omega+1)\cdot\omega+(\omega+1)\cdot1=((\omega+1)+(\omega+1)+(\omega+1)+\cdots)+(\omega+1)
$ =(\omega+1+\omega+1+\omega+1+\cdots)+(\omega+1)=(\omega+\omega+\omega+\cdots)+(\omega+1)
$ =\omega\cdot\omega+\omega+1=\omega^2+\omega+1
$ (\omega+1)^3=(\omega+1)^2\cdot(\omega+1)=(\omega^2+\omega+1)\cdot(\omega+1)=(\omega^2+\omega+1)\cdot\omega+(\omega^2+\omega+1)\cdot\omega
$ =\omega^3+\omega^2+\omega+1
$ (\omega+1)^n=\omega^n+\omega^{n-1}+\cdots+\omega^2+\omega+1
$ (\omega+1)^\omega=\omega^\omega
参考