|| 自然数から順序数まで拡張された数学的帰納法
「無限」の範囲を証明できる強力な証明手段
スポンサーリンク
目次
自然数「人間の直感に根差した数」
数学的帰納法「超限帰納法の雛型」
加法「和を得る操作（足し算のこと）」
大小関係「どちらが大きいか小さいか」
順序数「自然数から無限まで拡張した数」
整列原理「全ての集合は整列集合に加工できる」
整列可能定理「証明された形の整列原理」
ハルトークスの定理「集合の要素数より大きい順序数の存在」
超限帰納法「順序数まで拡張された数学的帰納法」
整列帰納法「順序数から整列集合に拡張された帰納法」
ε-帰納法「帰納法の発想と基礎公理の帰結」
自然数 Natural Number
これは厳密には
「ペアノの公理」により存在が保証されていて
\begin{array}{rcr} && 0 \in N \\ \\ 0 \in N &\to& 0+1 \in N \\ \\ 1 \in N &\to& 1+1 \in N \\ \\ &\vdots \end{array}
その構成はこのようになっています。
（これは厳密には加法の後に定義できる）
数学的帰納法
これは「一般化」という操作を保証するための手段で
（ペアノの5番名の公理はこれを更に一般化したもの）
\begin{array}{ccc} P (0) ∧ \Bigl( \forall n \,\, P (n) ⇒ P (n+1) \Bigr) & ⇒ & \forall n \,\, P (n) \\ \\ P(1) ∧ \Bigl( \forall n \,\, P(n) ⇒ P(n+1) \Bigr) & ⇒ & \forall n \,\, P(n) \end{array}
本質的には
「直感的な予想を裏付ける」ための
\begin{array}{ccc} 0 &≤& 0+1 \\ \\ n &≤& n+1 \end{array}
「代数」操作の基礎になります。
（厳密にはペアノの公理により保証される）
そしてこれは「超限帰納法」の原型に当たるため
これを理解していないとこの記事の内容は理解できません。
後者関数 Successor
これは「加法 + 」を一般化した概念で
（ + 以外のあらゆる「次」を定義できる）
\begin{array}{ccl} 0 &=& × \\ \\ 1&=&\mathrm{Suc}(0) \\ \\ 2&=&\mathrm{Suc}(1) \\ \\ 3&=&\mathrm{Suc}(2) \\ \\ & \vdots \end{array}
「次の数」を出力する操作になります。
（足し算ではなくあくまで「次」を定義する）
加法 +
これはつまり「足し算」のことで
\begin{array}{ll} \forall n\in N & f_n(0)=n \\ \\ \forall n,m\in N & f_n \Bigl( \mathrm{Suc}(m) \Bigr) = \mathrm{Suc} \Bigl( f_n(m) \Bigr) \end{array}
厳密にはこのような「関数 f_n(m) 」として定義されており
（この f_n(m) が n+m の具体的な中身）
\begin{array}{ccc} \Bigl( \Bigl(n, \mathrm{Suc}(0) \Bigr) , \mathrm{Suc} \Bigl( f(n,0) \Bigr) \Bigr) \\ \\ \Bigl( \Bigl(n, \mathrm{Suc}(m) \Bigr) , \mathrm{Suc} \Bigl( f(n,m) \Bigr) \Bigr) \end{array}
その実体はこのようになっています。
（詳細は加法の唯一存在定理の記事で）
大小関係
これは「大きさ」を比較する操作で
\begin{array}{ccc} \forall n,m\in N & n≤m &\Longleftrightarrow& \exists k\in N \,\, n+k=m \end{array}
厳密には「加法」により定義されています。
（加法が定義されてないと厳密には定義できない）
順序数 Ordinal Number
これは「自然数」を拡張した概念で
（有限順序数は自然数を意味する）
\begin{array}{l} 0, 1 , 2 ,..., n ,... \\ \\ 0, 1 , 2 ,..., n ,..., ω_0 , ω_0+1 ,..., ω_0+n ,..., ω_0+ω_0 ,... \end{array}
その具体的な構成は
\begin{array}{lcccl} 0 &=& ∅ &&初期値 \\ \\ α+1 &=& α∪\{α\} && 後続順序数 \\ \\ ω &=& \displaystyle \bigcup_{β<ω} β &{}& 極限順序数\end{array}
こんな感じになっています。
（ペアノの公理＋無限和集合の定義＋整列集合）
詳細は長くなるので別記事で扱いますが
\begin{array}{ccc} \mathrm{Ordinal}(α) &\Longleftrightarrow& \mathrm{Trans}(α) &∧&\mathrm{Well}\text{-}\mathrm{Order}(α,\in ) \\ \\ \mathrm{Ordinal}(α) &\Longleftrightarrow& \mathrm{Trans}(α) &∧& \forall β \in α \,\, \mathrm{Trans}(β) \end{array}
「順序数」の「要請的な定義」はこんな感じです。
（主にこの２つがあってこれらから ↑ の形が得られる）
順序数と超限帰納法
「超限帰納法」というのは
\begin{array}{ccc} 数学的帰納法 &\to& 超限帰納法 \\ \\ 自然数 &\to& 順序数 \end{array}
この「順序数の存在」を基盤とする概念で
（つまり順序数が分かってないと完全には理解できない）
「自然数の存在」により
（ペアノの公理により保証される）
\begin{array}{ccc} P(1) ∧ \Bigl( \forall n \,\, P(n) ⇒ P(n+1) \Bigr) & ⇒ & \forall n \,\, P(n) \end{array}
「数学的帰納法」の正しさが保証されるように
（自然数の全称化まで保証できる）
「順序数が存在する」から
（整列集合の構造を無限方向に拡張した概念）
\begin{array}{ccc} \forall α \Bigl( \Bigl( \forall β\in α \,\, P(β) \Bigr) ⇒ P(α) \Bigr) &\Longrightarrow& \forall α \,\, P(α) \end{array}
「超限帰納法」は正しくなります。
（順序数の範囲まで全称化できるようになる）
整列原理 Well-Orderable
『全ての集合 S 』は「整列順序を持つ」
（あらゆる集合は整列させることができる）
\begin{array}{ccc} \mathrm{Well}\text{-}\mathrm{Order}(N,≤) \\ \\ ↓ \\ \\ \mathrm{Well}\text{-}\mathrm{Order}(α,\in) \\ \\ ↓ \\ \\ \mathrm{Well}\text{-}\mathrm{Orderable}(S) \end{array}
これが「整列原理」の主張で
基本的には「公理」に当たるものになります。
（選択公理から定理として導くこともできる）
整列原理の公理的な感覚
「整列順序を持つ」というと難しく見えますが
これは具体的な操作を考えると簡単に理解できます。
\begin{array}{ccc} S &:& 中身が分かる集合 \\ \\ \mathrm{Choice} &:& 集合から要素を選ぶ操作 \end{array}
というのも
「選択公理」を前提として
「１つ選ぶ → それ以外を選ぶ」このように考えれば
\begin{array}{lcl} e_0 &=& \mathrm{Choice}(S) \\ \\ e_1 &=& \mathrm{Choice}(S\setminus \{e_0\}) \\ \\ e_2&=&\mathrm{Choice}(S\setminus \{e_0,e_1\}) \\ \\ &\vdots \\ \\ e_{n+1} &=& \mathrm{Choice}(S\setminus \{e_0,e_1,...,e_n\}) \\ \\ &\vdots \end{array}
これができるというのは当たり前の話です。
特に疑問を覚えるような部分は無いと思います。
（これが無限回可能という感覚が超限帰納法に繋がる）
選択公理の感覚
念のため補足しておくと
「選択公理」の感覚というのは
\begin{array}{lcl} \mathrm{Choice}(\{a,b,c\}) &\to& \{a\} \\ \\ \mathrm{Choice}(実数) &\to& \{π\} \\ \\ \mathrm{Choice}(果物) &\to& \{リンゴ\} \end{array}
要は「中身がある集まり」から
「なにか１つ選ぶ」感覚のことで
（これができないという世界に我々はいない）
\begin{array}{ccc} \mathrm{Choice}(この世の全て) &=& \{ 水 \} \end{array}
これがどんなに大きな集合でも可能というのが
この公理が主張している内容になります。
（これができないというのは直感に反する）
より厳密には
「共通部分を持たない集合」から
（この集合は複数でも１つでも可）
\begin{array}{ccc} \{ 偶数,奇数 \} &&\to&& \{2,7\} \\ \\ \{自然数\} &&\to&& \{ 1 \} \end{array}
「要素を１つだけ」選んで
「その要素を全て集める」
（この全て集めるという部分が矛盾の原因になり得る）
\begin{array}{ccc} \Bigl\{ \{0\},\{1\},...,\{n\},... \Bigr\} &&\to&& \{ 0,1,2,...,n,... \} \end{array}
つまりこのような「集合が存在する」ということを
この「選択公理」は保証しています。
（直感的に明らか故に公理）
整列原理と順序数
この「整列原理 \mathrm{Well}\text{-}\mathrm{Orderable}(S) 」は
\begin{array}{ccc} \forall S& \exists R\subset S\times S & \mathrm{Well}\text{-}\mathrm{Order}(S,R ) \end{array}
実は「選択公理＋順序数」と同値の概念で
（全ての集合 S には整列順序 R が存在する）
\begin{array}{ccc} \mathrm{Ordinal}(α) &\Longleftrightarrow& \mathrm{Trans}(α) &∧&\mathrm{Well}\text{-}\mathrm{Order}(α,\in ) \end{array}
「直感」から得られるのが「整列原理」であるとするなら
「順序数」はその「論理的基盤」に位置します。
（順序数は整列する形を具体化できる）
故にこの記事ではこれを「公理」としては扱わず
（超限帰納法は整列原理からも正しさを保証できる）
\begin{array}{ccc} 順序数 &\to& 整列原理 \\ \\ && 整列可能定理 \end{array}
「定理」と位置付けて話を進めていきます。
（つまり証明する必要がある命題として扱う）
超限帰納法 Transfinite Induction
この記事の主題であるこれは
「数学的帰納法」の形と
（初期値は 0 でも良い）
\begin{array}{ccc} P(1) ∧ \Bigl( \forall n \,\, P(n) ⇒ P(n+1) \Bigr) & ⇒ & \forall n \,\, P(n) \end{array}
「順序数の存在」に基づいて
\begin{array}{ccc} \forall α \Bigl( \Bigl( \forall β\in α \,\, P(β) \Bigr) ⇒ P(α) \Bigr) &\Longrightarrow& \forall α \,\, P(α) \end{array}
このように定義されています。
（厳密にはこれは統合された形）
補足しておくと
↓ の部分を比較すれば
\begin{array}{ccl} P(n) &⇒& P(n+1) \\ \\ \Bigl( \forall β\in α \,\, P(β) \Bigr) & ⇒ & P(α) \end{array}
ほとんど変わっていないことが分かると思います。
（ n+1 に無限が入り得るので左が調整されている）
超限帰納法の本来の定義
実は ↑ の定義は
\begin{array}{lcc} α=1 && P(1) &⇒& P(1) \\ \\ α<ω_0 && \forall α \,\, \Bigl( P(α) ⇒ P(α+1) \Bigr) &⇒& \forall α \,\, P(α) \\ \\ ω_0≤λ && \forall λ \Bigl( \Bigl( \forall β\in λ \,\, P(β) \Bigr) ⇒ P(λ) \Bigr) &⇒& \forall λ \,\, P(λ)\end{array}
これを「統合した形」で
本来の「超限帰納法」はこのようになっています。
（正確には ω+1 などは後続順序数なので2番目に該当）
補足しておくと
「順序数 α の範囲」を
「最小の無限 ω_0 未満」とすれば
\begin{array}{ccc} ω_0&=& \displaystyle \bigcup_{n\in N} n \end{array}
「 ω_0 以上の範囲」を考える必要が無くなることから
（可算無限 ω_0 の定義より ω_0 以上の n は存在しない）
\begin{array}{lcc} α=1 && P(1) &⇒& P(1) \\ \\ α<ω_0 && \forall α \,\, \Bigl( P(α) ⇒ P(α+1) \Bigr) &⇒& \forall α \,\, P(α) \\ \\ ω_0≤λ && \forall λ \Bigl( \Bigl( \forall β\in λ \,\, P(β) \Bigr) ⇒ P(λ) \Bigr) &⇒& \forall λ \,\, P(λ)\end{array}
当然の帰結として
\begin{array}{lcc} n=1 && P(1) &⇒& P(1) \\ \\ n<ω_0 && \forall n \,\, \Bigl( P(n) ⇒ P(n+1) \Bigr) &⇒& \forall n \,\, P(n) \end{array}
そのまま「数学的帰納法」を導くことができます。
（本来の定義からだと拡張が実感しやすい）
整列可能定理
『全ての集合には整列順序が存在する』
これは「整列原理」という「公理」なんですが
\begin{array}{ccc} \forall S& \exists R\subset S\times S & \mathrm{Well}\text{-}\mathrm{Order}(S,R ) \end{array}
「選択公理」と「超限帰納法」を認める場合
実は「定理」として導くことができます。
直感的な証明
「整列順序の存在」については
「選んで取り出す」という操作を考えれば
（この操作の「選ぶ」の保証に選択公理が使われる）
\begin{array}{lcccl} S &\to& x_0 && S\setminus \{x_0\} \\ \\ α &\to& 0 && α\setminus \{0\} \end{array}
「任意の集合 S 」から取り出す
「順序数」から順番に取り出す
\begin{array}{ccc} S \to x_0 & S\setminus \{x_0\} && α\to 0 & α\setminus \{0\} \\ \\ S\setminus \{x_0\} \to x_1 & S\setminus \{x_0,x_1\} && α\setminus\{0\}\to 1 & α\setminus \{0,1\} \\ \\ & & \vdots \end{array}
これを『 S が空になるまで同時に続ける』ことで
\begin{array}{ccc} C&=& \{ (α,x_α) \mid \mathrm{Ordinal}(α)∧x_α\in S \} \end{array}
感覚的に証明することができます。
（ C の整列順序がそのまま S の整列順序になる）
選択公理と選択関数
「選んで取り出す」という操作は
\begin{array}{lcl} x_0 &=& \mathrm{Choice}(S) \\ \\ x_1 &=& \mathrm{Choice}(S\setminus \{x_0\}) \\ \\ x_2&=&\mathrm{Choice}(S\setminus \{x_0,x_1\}) \\ \\ &\vdots \\ \\ x_{n+1} &=& \mathrm{Choice}(S\setminus \{x_0,x_1,...,x_n\}) \\ \\ &\vdots \end{array}
↑ の「整列原理」で紹介したように
この「選択関数」により実現されていて
（この時の S は空集合じゃないことが前提）
\begin{array}{ccc} \mathrm{Choice} &:& S&\to& S \end{array}
これがあるから
「選ぶ」という感覚は形式化することができます。
選んで取り出すの具体的な中身
そして「選択関数 \mathrm{Choice} 」から
「選んで取り出す」という操作は定義できて
\begin{array}{ccc} S &&\to&& x_0 & S\setminus \{x_0\} \end{array}
入力 S からの出力が ↑ であることを考えると
\begin{array}{ccc} \mathrm{Pop}(S) &:=& \Bigl( \mathrm{Choice}(S),S\setminus \{\mathrm{Choice}(S)\} \Bigr) \end{array}
「選んで取り出す」の形式は
このような形で定義できることが分かります。
補足しておくと
\begin{array}{lcl} \mathrm{Pop}(\{a,b,c\}) &=& \Bigl( a,\{b,c\} \Bigr) \\ \\ \mathrm{Pop}(\{b,c\}) &=& \Bigl( b,\{c\} \Bigr) \\ \\ \mathrm{Pop}(\{c\}) &=& \Bigl( c,∅ \Bigr) \end{array}
この \mathrm{Pop} の挙動はこんな感じです。
（ \mathrm{Choice} は非空でないと使えないので最後は止まる）
順序数を下から順番に取り出す
これは簡単そうに見えて意外と難解で
\begin{array}{ccc} \mathrm{Numbering}(α) &:=& \Bigl( \min(α),α\setminus \{α\} \Bigr) \end{array}
「順序数の最小元をとる」の
「順序数 τ 」を定義する段階で
\begin{array}{ccc} α & x_α && α<τ \end{array}
実は「 S の要素数より大きい」という
「不足が無い」前提が課せられています。
（故に S が非空なので τ も空ではない）
「有限」であれば
\begin{array}{ccc} \mathrm{Cardinal}(S)&=&τ \end{array}
「 S の要素数」がそのまま「順序数」になるので
この場合の話は簡単なんですが
「無限濃度の S 」になると
（特に非可算無限集合なんかでは）
\begin{array}{ccc} \mathrm{Cardinal}(S)&≤&τ &&？ \end{array}
途端に話がややこしくなります。
（こんな順序数 τ が本当に存在するのか）
形式と着地
ひとまず「 S の要素数より大きな順序数 τ 」
これの存在を前提として話を進めてみると
\begin{array}{ccc} \Bigl( \mathrm{Numbering}(τ),\mathrm{Pop}(S) \Bigr) \end{array}
「同時に取り出す」場合
このようになることが分かったので
\begin{array}{ccc} \mathrm{Value} &:& \Bigl( (a_1,a_2), (b_1,b_2) \Bigr) &\mapsto& (a_1,b_1) \end{array}
後は「ペアの中にあるペア」の
「第1成分を取り出す」ような写像を使えば
\begin{array}{ccc} \mathrm{Value}\Bigl( \mathrm{Numbering}(τ),\mathrm{Pop}(S) \Bigr)&=& (0,x_0) \end{array}
この着地を得ることができます。
同様に
\begin{array}{ccc} \mathrm{Sets} &:& \Bigl( (a_1,a_2), (b_1,b_2) \Bigr) &\mapsto& (a_2,b_2) \end{array}
「第2成分を取り出す」ような写像を使って
\begin{array}{ccc} \mathrm{Number} &:& (a_2,b_2) &\mapsto& a_2 \\ \\ \mathrm{ArgSet} &:& (a_2,b_2) &\mapsto& b_2 \end{array}
それぞれ取り出せば
（構造がややこしいですがやってることは単純）
\begin{array}{rcc} \mathrm{Number}\Bigl( \mathrm{Sets}\Bigl( \mathrm{Numbering}(τ),\mathrm{Pop}(S) \Bigr) \Bigr) &=& τ\setminus\{0\} \\ \\ \mathrm{ArgSet}\Bigl( \mathrm{Sets}\Bigl( \mathrm{Numbering}(τ),\mathrm{Pop}(S) \Bigr) \Bigr) &=& S\setminus\{x_0\} \end{array}
「次」を形式的に得ることができます。
（引数 τ,S のみで次の引数を作れる）
超限帰納法による操作回数の保証
「 ↑ の操作が無限回でも行える」
これを保証してくれるのが「超限帰納法」で
\begin{array}{ccc} (0,x_0) &\to& (α,x_α) \end{array}
これは ↑ で得た一定の手続きを
\begin{array}{ccc} x_α &=& \mathrm{Choice}(S_α) \\ \\ S_α &=& S\setminus \{ x_γ \mid γ \in α\} \end{array}
帰納ステップに書き直すことにより
（ \mathrm{Choice} は S_α≠∅ の時のみ使える）
\begin{array}{ccc} S_{α+1} &=& S_α\setminus \{x_α\} \\ \\ x_{α+1} &=& \mathrm{Choice}(S_{α+1}) \end{array}
「後続順序数」の形と
（ S_{α+1}≠∅ であれば選べる要素が存在する）
\begin{array}{ccc} S_λ &=& S\setminus \{ x_β \mid β \in λ\} \\ \\ x_λ &=& \mathrm{Choice}(S_λ) \end{array}
「極限順序数」の形から
（ S_λ≠∅ であれば選べる要素が存在する）
\begin{array}{lclcl} \mathrm{Choice}(S) &=& x_0 && S≠∅ \\ \\ \mathrm{Choice}(S_{α+1}) &=& x_{α+1} && S_{α+1}≠∅ \\ \\ \mathrm{Choice}(S_λ) &=& x_λ && S_λ≠∅ \end{array}
「 x_α の存在」という形で証明することができます。
（ ↑ は α と x_α の存在を確認している）
まとめると
\begin{array}{ccl} P(α) &\Longleftrightarrow& S_α≠∅⇒ \exists x_α\in S_α \\ \\ &\Longleftrightarrow& S_α≠∅⇒\Bigl( \exists x_α\in S_α \,\, x_α=\mathrm{Choice}(S_α) \Bigr) \end{array}
今回の帰納法における条件 P はこんな感じで
（存在することが真であるかを確認する必要がある）
\begin{array}{lcc} α=0 && P(0) &⇒& P(0) \\ \\ α<ω_0 && \forall α \,\, \Bigl( P(α) ⇒ P(α+1) \Bigr) &⇒& \forall α \,\, P(α) \\ \\ ω_0≤λ && \forall λ \Bigl( \Bigl( \forall β\in λ \,\, P(β) \Bigr) ⇒ P(λ) \Bigr) &⇒& \forall λ \,\, P(λ)\end{array}
証明の内容はそのままこんな感じになっています。
（選択関数の定義に強く依存してる）
任意の集合より大きな順序数の存在
いったんスルーしましたが
↑ の証明を完成させるには
\begin{array}{ccc} \mathrm{Cardinal}(S) &≤& τ \end{array}
「集合 S の要素数」以上の
「順序数 τ の存在」が必須です。
（これが無いと S の全ての要素に α を用意できない）
確認しておくと
\begin{array}{ccc} \mathrm{Cardinal}(S) &=& τ \end{array}
「有限」の範囲なら
「 S の要素数」がそのまま使えて
\begin{array}{ccc} \mathrm{Cardinal}(S) &=&ω<ω+1 \end{array}
「可算無限」範囲なら
このようにできることは直感的に明らか。
しかし「非可算無限」の範囲になると
\begin{array}{ccc} \mathrm{Cardinal}(R) &≤& ω && ？ \end{array}
このようになる順序数 α が本当にあるのか
これがちょっと微妙なので
現時点では
\begin{array}{ccc} \forall S & \exists τ & \mathrm{Set}(S)∧\mathrm{Ordinal}(τ) ∧ \mathrm{Cardinal}(S) ≤ τ \end{array}
これが正しい保証はありません。
（正しければ整列可能定理の証明も完成する）
非可算無限と順序数
これをそのまま意味する
「 \mathrm{Hartogs} の定理」という主張が実はあって
\begin{array}{ccc} \forall S & \exists τ & \mathrm{Set}(S)∧\mathrm{Ordinal}(τ) ∧ \mathrm{Cardinal}(S) ≤ τ \end{array}
これは「全ての集合 S 」に対して
そのままこのようになる順序数 τ を提供してくれます。
（ S からの単射が作れない τ が存在する）
より正確には
\begin{array}{ccc} τ&:=&\sup\{ α \in \mathrm{ON} \mid αからSへの単射が存在する \} \end{array}
「有限の範囲」なら「全単射の存在」を意味する
「 \mathrm{Hartogs} 数」なる順序数 τ の定義と
（公理系は \mathrm{NBG} を採用するのが適切）
\begin{array}{ccc} \forall α\in τ & \exists f & (f:α\to S) は単射 \end{array}
「単射の存在」によって定義されてるんですが
言ってることは ↑ とほぼ同じです。
集合のサイズと写像
↑ のままだと難解ですが
\begin{array}{ccc} \left\{\begin{array}{ccc} 1&\to& a \\ \\ 2&\to& b \\ \\ &&c \end{array}\right. &→&\left\{\begin{array}{ccc} 1&\to& a \\ \\ 2&\to& b \\ \\ 3&\to&c \end{array}\right. &→& \left\{\begin{array}{ccc} 1&\to& a \\ \\ 2&\to& b \\ \\ \textcolor{pink}{τ}&\to&c \\ \\ 4 \end{array}\right. \end{array}
要はこういう話で
（ ↑ の単射云々から得られる τ はこれ）
\begin{array}{ccc} 自然数の要素数 && 有理数の要素数 && 実数の要素数 \\ \\ \mathrm{Cardinal}(N) &=& \mathrm{Cardinal}(Q) &<&\mathrm{Cardinal}(R) \end{array}
「無限集合」の場合でも
この理屈は通用するというのがこの定理の主張です。
（詳しくはカントールの定理を参照してください）
単射の存在と順序数
故に発想としては単純かつ自然で
\begin{array}{ccc} τ&:=&\sup\{ α \in \mathrm{ON} \mid αからSへの単射が存在する \} \end{array}
これ自体は
\begin{array}{ccc} 集合の要素数を調べたい \\ \\ ↓ \\ \\ 無限集合の要素数を調べたい \\ \\ ↓ \\ \\ 全単射があるなら要素数は同じ \\ \\ ↓ \\ \\ 全単射の存在を調べたい \\ \\ ↓ \\ \\ 全単射を調べるなら双方に単射があればいい \end{array}
「自然数と有理数の要素数」や
「ベルンシュタインの定理」のような
\begin{array}{c} α \to S & α ← S && 大きさ \\ \\ 〇 &× && α>|S| \\ \\ 〇 &〇 && α=|S| \\ \\ × &〇 && α<|S| \end{array}
「要素数が無限の集合」を調べる話では
普通に出て来る発想になります。
（無限集合の基数の定義に由来する）
非可算集合に対して単射が存在する順序数
以上を踏まえると
\{ α \in \mathrm{ON} \mid αからSへの単射が存在する \}
こういう集合は自然に発想できて
（下の順序数から S の要素数に近付ける）
\begin{array}{lcc} \{0\} &\to& S \\ \\ \{0,1\} &\to& S \\ \\ \{0,1,2\} &\to& S \\ \\ & \vdots \\ \\ \{0,1,2,3,...,α\} &\to& S \\ \\ &\vdots \\ \\ \{α \mid α\in ω_0\} &\to& S \\ \\ &\vdots \end{array}
「非可算無限集合の要素数」
これより下の順序数を全て集められることから
（ S の要素数に関係無くこの操作は明らかに可能）
\begin{array}{ccr} T&:=& \{ α \in \mathrm{ON} \mid αからSへの単射が存在する \} \\ \\ τ&:=&\sup\{ α \in \mathrm{ON} \mid αからSへの単射が存在する \} \end{array}
この「上限として得られる順序数 τ 」は
必ず「 S の要素数より大きくなる」と言えます。
（この集合の上界は S より大きな α の集まりになる）
上界はすぐに作れる
事実確認をしておくと
\begin{array}{ccl} 0&=&\{\} \\ \\ 1&=&\{0\} \\ \\ 2&=&\{0,1\} \\ \\ &\vdots \end{array}
「順序数同士の和集合」は
\begin{array}{ccc} β = α∪β &&\Longleftrightarrow&& α\in β∨α=β \\ \\ α = α∪β &&\Longleftrightarrow&& β\in α∨β=α \end{array}
必ず「順序数」になります。
そしてこの事実と
「極限順序数」の定義を考えると
\begin{array}{ccc} τ &=& \displaystyle \bigcup_{α\in T} α \end{array}
このように定義できる集合 τ は
確実に「 T の要素 α の要素を全て持つ」ため
\begin{array}{cl} \forall α\in T & α\in τ ∨α=τ \\ \\ \forall α\in T & α≤τ \end{array}
確実に全ての α 以上の順序数になると言えます。
（有限だと一番大きな順序数になるので明らか）
Hartgos の定理
この定理の証明の概形は
ほとんどが ↑ の内容で
\begin{array}{ccr} T &:=& \{ α \in \mathrm{ON} \mid αからSへの単射が存在する \} \\ \\ τ&:=&\sup\{ α \in \mathrm{ON} \mid αからSへの単射が存在する \} \end{array}
この「 τ の存在」が明らかなら
（上界が存在すれば τ は存在する）
\begin{array}{ccc} \mathrm{Cardinal}(S)=α &\to& \mathrm{Hartogs} \,\, \mathrm{Number} \\ \\ α<ω_0 && α+1 \\ \\ α=ω_0 && ω_0∪\{ω_0\} \\ \\ ω_0<α && τ \end{array}
特に考えることは無く
\begin{array}{ccc} \mathrm{Cardinal}(S) &<&τ \end{array}
これを満たす「順序数」の存在は
\begin{array}{ccc} τ &=& \displaystyle \bigcup_{α\in T} α \end{array}
このような形ですぐに導くことができます。
（上界の存在は集合であるなら明らか）
非可算より大きな順序数の存在
ただよくよく考えると
\{ α \in \mathrm{ON} \mid αからSへの単射が存在する \}
これが「順序数全体にならない」保証は無く
（クラスの定義を考えるとならなそうではある）
\begin{array}{ccc} 順序数 &<& 非可算無限 \end{array}
常にこうなる可能性は否定できません。
（非可算より大きな順序数は存在する？）
\{ α \in \mathrm{ON} \mid αからSへの単射が存在する \}
これが「真クラス」ではなく
「集合である」なら大丈夫そうですが
この時点でこれは分かっていないので
\begin{array}{ccc} \mathrm{ON} &=& \displaystyle \bigcup_{α\in \mathrm{ON}} α \\ \\ τ &=& \displaystyle \bigcup_{α\in T} α \end{array}
この τ が「順序数になる」保証はまだありません。
（ T が集合であれば順序数になる）
単射を持つ順序数の集まりは集合？
これを深堀するには
\begin{array}{ccc} αからSへの単射が存在する \end{array}
この部分をきちんと確認する必要があって
\begin{array}{ccc} f&=&\{ (γ,f(γ)) \mid γ\in α ∧ f(γ) \in S \} \end{array}
「順序対を要素に持つ」という
\begin{array}{ccc} f&=&\{ (x,y) \mid x\in X ∧ y \in Y \} \\ \\ f&\subset& X\times Y \end{array}
「写像 f 」の定義を意識する必要があります。
（つまり写像を対の集合として扱う必要がある）
というのも
\begin{array}{ccc} \mathrm{Set}\Bigl( \{ α \in \mathrm{ON} \mid αからSへの単射が存在する \} \Bigr) \end{array}
欲しい着地を考えるにしても
\begin{array}{ccc} αからSへの単射が存在する \\ \\ \exists f \,\, f:α→S \end{array}
要素 α の条件はこれしか存在せず
（ここの f は単射に限定するとします）
\begin{array}{ccc} \mathrm{Cardinal}(N)&<&\mathrm{Cardinal}(2^N) \end{array}
「 S の要素数」が「非可算無限である」
この前提しか扱うことができません。
（有限と可算無限の場合は明らか）
加えて
この時点で分かっているのは
\begin{array}{ccc} \mathrm{Set}(2^N) \end{array}
「 S は集合である」だけです。
（冪集合公理より非可算無限集合は集合である）
写像と集合の関係が
\begin{array}{ccc} T&=&\{ α \in \mathrm{ON} \mid αからSへの単射が存在する \} \end{array}
\begin{array}{ccc} α\in T &\Longleftrightarrow& α\in \mathrm{ON} \,\, \exists f:α\to S \end{array}
このような形で定義されていることも分かってますが
まだこれだけでは欲しい答えには届きません。
単射と全単射と順序数
ここから更に事実確認をしていくと
\begin{array}{ccc} f&:& α &\to& S \\ \\ && γ &\mapsto& x \end{array}
まず「順序数 α から S への単射 f 」は
『存在するなら』こうなっていて
\begin{array}{ccc} 1&\to& a \\ \\ 2&\to& b \\ \\ &&c \end{array}
「対応していない S の要素」を考えると
（単射が存在するなら要素数は S 以下）
\begin{array}{ccc} S_f &=& \{ f(γ)\in S \mid γ\in α \} \end{array}
それを除いた S の部分集合として
「要素 f(γ) のみ」の集合が作れます。
（とりあえず全単射を作って話を単純にしたい）
そしてこれを考えると
\begin{array}{ccc} f&:& α &\to& S_f \end{array}
この f は必ず全単射なので
（ S のドメインが制限されている）
\begin{array}{ccc} f^{-1} &:& α &←& S_f \end{array}
このような「逆写像 f^{-1} 」を考えた時
これもまた確実に「全単射」になると言えて
（１つの値に１つの値が対応している）
この逆写像を用いると
\begin{array}{ccc} α \in β &\Longleftrightarrow& α<β \end{array}
「順序数同士は確実に比較できる」ことから
（順序数は整列集合であるため三分律を満たす）
\begin{array}{ccc} f^{-1}(x)&=& δ \\ \\ f^{-1}(y)&=& η \end{array}
こうなるとして
\begin{array}{ccc} δ<η &\Longleftrightarrow& f^{-1}(x) < f^{-1}(y) \end{array}
δ<η であるとすると
\begin{array}{ccc} x<_{S} y &\Longleftrightarrow& f^{-1}(x) < f^{-1}(y) &\Longleftrightarrow& δ<η \end{array}
このような形で
「集合 S_f の整列順序 <_{S} 」を定義することができます。
（これは本質的には順序数の整列順序）
集合同士の関係が作れる
整理すると
\begin{array}{ccc} (x,y) &\in& S_f \times S_f \end{array}
「整列順序 <_S 」は
\begin{array}{ccc} R_S &=& \{ (x,y)\in S\times S \mid f^{-1}(x)<f^{-1}(y) \} \end{array}
「集合 R_S 」としては S\times S の部分集合です。
（関係は写像と同様の形で定義できる）
そして
\begin{array}{ccc} T&=& \{ α \in \mathrm{ON} \mid \exists f:α\to S \} \end{array}
問題のクラスをこのようにすると
（この時点では集合か不明なのでクラスと呼ぶ）
\begin{array}{ccc} \forall α\in T &\Longleftrightarrow& \forall α\in \mathrm{ON} \,\, \exists f:α\to S \end{array}
その要素である「順序数」と
\begin{array}{ccc} α &\leftrightarrows& (α,S) \end{array}
「全単射による繋がり」の流れは
（ α が繋がってるのは S の要素の一部か全て）
\begin{array}{ccl} (γ,f(γ))\in f &\Longleftrightarrow& \forall γ\in α \\ \\ (γ,f(γ))\in f &\Longleftrightarrow& \forall f(γ)\in S_f \end{array}
こうなっています。
（定義上必ず α と S_f は要素数が同じになる）
そしてこの関係をさらに整理すると
\begin{array}{ccc} α &\rightleftarrows& S_f &\subset& S \end{array}
このような関係が得られるので
（これは単射の定義より明らかとも言える）
\begin{array}{ccc} S_f &←& S &←& f(α) &←& α \\ \\ S &\to& S_f &\to& f^{-1}(S_f) &\to& α \end{array}
このような操作が存在する
これが確認できていることも考慮すると
\begin{array}{ccc} f && f^{-1} && {} && R_f \\ \\ α\times S &\rightleftarrows& f(α)\times S &=& S_f\times S_f &\subset& S\times S \end{array}
このような関係も見えてきます。
（大事なのはどちらの方向からも写像で得られる事実）
改めて最初から整理してみる
基本に立ち返って
\begin{array}{ccc} \mathrm{Cardinal}(α)&≤&\mathrm{Cardinal}(S) \end{array}
まずこれを前提とした
（有限と可算無限は明らか）
\begin{array}{ccl} T &=& \{α\in \mathrm{ON} \mid αからSへの単射が存在する \} \\ \\ &=& \{α\in \mathrm{ON} \mid \exists f:α\to S は単射 \} \end{array}
これですが
（上限が \mathrm{Hartogs} 数になるはずのクラス）
\begin{array}{ccc} α &？& S \end{array}
これはこのままではよく分からないので
（最終的には一致したり追い越したりするかも）
\begin{array}{ccc} α &\to& f(α) && S\setminus f(α) \\ \\ γ &\mapsto& f(γ) \end{array}
「部分集合」を使うことで
（可算無限までは確実にとれるので単射の存在は明らか）
\begin{array}{ccl} T&=&\{α\in \mathrm{ON} \mid \exists f:α\to S は単射 \} \\ \\ &=& \{α\in \mathrm{ON} \mid \exists S_f\subset S \,\, \exists f:α ↔ S_f は全単射 \} \end{array}
「全単射」の形に書き換えてみます。
（これが ↑ の S_f 周りの話のまとめ）
\begin{array}{ccc} T && T \\ \\ α &↔& α\leftrightarrows S_f \end{array}
簡略的にはこんな感じ。
（ただ部分集合の形に書き換えただけ）
そしてこれを更に整理してみると
\begin{array}{ccc} T && f \\ \\ α &\leftrightarrows& α\times S_f \end{array}
このような関係が見えて
\begin{array}{ccc} α &\overset{f}{\longleftrightarrow}& S_f \end{array}
「全単射」である以上
必ずこのようになると言えることから
\begin{array}{ccc} T && f && <_S \\ \\ α &\leftrightarrows& α\times S_f &\leftrightarrows& S_f\times S_f \end{array}
この関係も見えてきます。
（１つの α が１つの「集合」に対応している）
全体と冪集合
ここで着地を意識すると
\begin{array}{ccl} T&=&\{α\in \mathrm{ON} \mid \exists f:α\to S は単射 \} \\ \\ &=& \{α\in \mathrm{ON} \mid \exists S_f\subset S \,\, \exists f:α ↔ S_f は全単射 \} \end{array}
最終目標は「 α のクラス」ですから
（より厳密には S への単射が存在する α の集まり）
\begin{array}{ccc} α &&\to && \forall α \end{array}
この目標から
「全ての α を集めたい」という要望が得られて
ここで
\begin{array}{ccc} T && f && <_S \\ \\ α &\leftrightarrows& α\times S_f &\leftrightarrows& S_f\times S_f \end{array}
この関係を意識すると
「 S_f を全て集める」ことが
「 α を全て集める」ことに
\begin{array}{rcccr} S_f×S_f &&\overset{}{\longleftrightarrow} && α \\ \\ \forall \,\, S_f×S_f &&\overset{}{\longleftrightarrow} && \forall \,\, α \end{array}
間接的に繋がるということが分かるので
\begin{array}{ccc} S_f×S_f&\subset&S×S \end{array}
この関係から
（ S_f が S の部分集合である以上明らか）
\begin{array}{ccc} S_f\times S_f &\in & 2^{S\times S} \end{array}
このような操作を考えることができます。
（冪集合は「全ての部分集合」を集める操作）
対公理と置換公理と冪集合公理
ここまでの話を整理すると
\begin{array}{ccc} \mathrm{Set}(S) &\Longleftrightarrow& Sは集合である \end{array}
「全単射」「対」「冪集合」
そして「部分集合」という操作を使えば
\begin{array}{ccc} T && f && <_S &&\mathrm{Set}(S) \\ \\ α &\leftrightarrows& α\times S_f &\leftrightarrows& S_f\times S_f &\subset& S\times S \end{array}
その結果として
この対応を得ることができるので
\begin{array}{ccc} \mathrm{Set}(S) &\overset{\mathrm{pair}}{\longleftrightarrow}& \mathrm{Set}(S\times S) &\overset{\mathrm{subset}}{\longleftrightarrow}& \mathrm{Set}(S_f\times S_f) \end{array}
この事実を考えると
（対公理と置換公理が根拠）
\begin{array}{ccc} \mathrm{Set}(S_f\times S_f) &\overset{f^{-1}}{\longleftrightarrow}& \mathrm{Set}(α\times S_f) &\overset{f}{\longleftrightarrow}& \mathrm{Set}(α) \end{array}
同様の理屈で
\begin{array}{ccc} \mathrm{Set}(S) &\overset{\mathrm{pair}}{\longleftrightarrow}& \mathrm{Set}(S\times S) &\overset{\mathrm{power}}{\longleftrightarrow}& \mathrm{Set}(2^{S\times S}) \end{array}
こうなると言えます。
（これの根拠は対公理と冪集合公理）
冪集合に間接的に含まれる
まとめると
\begin{array}{ccc} \mathrm{Set}(S_f\times S_f) &\overset{\mathrm{subset}}{\longleftrightarrow}& \mathrm{Set}(S\times S) &\overset{\mathrm{power}}{\longleftrightarrow}& \mathrm{Set}(2^{S\times S}) \\ \\ S_f\times S_f &\subset& S\times S &\in& 2^{S\times S} \end{array}
「 S_f\times S_f の全て」が
「冪集合 2^{S\times S} の要素」に含まれることから
（ 2^{S\times S} は S\times S の部分集合を全て要素に持つ）
「全ての S_f\times S_f の集まり」もまた
\begin{array}{ccc} R_S &=& \{ (x,y)\in S\times S \mid f^{-1}(x)<f^{-1}(y) \} \end{array}
「集合である」と言えるので
（関係 <_S の集合形 R_S がこれと同一視できる）
\begin{array}{ccc} S_f\times S_f &\in& R_S &\subset & 2^{S\times S} \end{array}
これと「全ての α 」を
\begin{array}{ccl} T&=&\{α\in \mathrm{ON} \mid \exists f:α\to S は単射 \} \\ \\ &=& \{α\in \mathrm{ON} \mid \exists S_f\subset S \,\, \exists f:α ↔ S_f は全単射 \} \end{array}
「全単射」によって繋げることができる事実を考えると
\begin{array}{ccc} α &\overset{}{\longleftrightarrow}& S_f\times S_f \\ \\ T &\longleftrightarrow& R_S \end{array}
「置換公理」より
\begin{array}{ccc}\mathrm{Set}(2^{S\times S}) &\overset{}{\longleftrightarrow}& \mathrm{Set}(R_S) &\overset{}{\longleftrightarrow}& \mathrm{Set}(T) \end{array}
T もまた「集合である」と言えます。
（置換公理は集合の像が集合であることを保証する）
順序数の集まりが集合であるなら
以上のことを踏まえると
\begin{array}{ccl} T&=&\{α\in \mathrm{ON} \mid \exists f:α\to S は単射 \} \\ \\ &=& \{α\in \mathrm{ON} \mid \exists S_f\subset S \,\, \exists f:α ↔ S_f は全単射 \} \end{array}
これは確実に「真クラス」ではないため
（集合であるという事実から）
\begin{array}{ccc} T&≠& \mathrm{ON} \end{array}
「順序数全体」と一致することはありませんから
（ T が真クラスではないため τ は集合）
\begin{array}{ccc} \mathrm{ON} &=& \displaystyle \bigcup_{α\in \mathrm{ON}} α \\ \\ τ &=& \displaystyle \bigcup_{α\in T} α \end{array}
「極限順序数」の定義を参考に
このような順序数 τ を定義すると
\begin{array}{ccc} \forall α\in T & α≤τ \end{array}
これは必ずこうなると言えます。
（ τ は T の上界の要素になる）
\mathrm{Hartogs} 数の定義と順序数
そしてこの τ が
\begin{array}{ccr} T&=&\{α\in \mathrm{ON} \mid \exists f:α\to S は単射 \} \\ \\ τ&=&\sup\{α\in \mathrm{ON} \mid \exists f:α\to S は単射 \} \end{array}
「 \mathrm{Hartogs} 数」と呼ばれる順序数で
\begin{array}{ccc} τ &=& \displaystyle \bigcup_{α\in T} α \end{array}
これは「 T の上界」の「最小元」になります。
（全ての上界 κ は \forall α\in T \,\, α≤κ であるため）
整列帰納法
この「整列原理」の感覚から
\begin{array}{ccc} \mathrm{Ordinal}(α) && {} && \mathrm{Well}\text{-}\mathrm{Order}(S,R) \\ \\ α &&\to && x\in S \end{array}
「整列集合」方向に一般化された帰納法が
\begin{array}{ccc} e \in \mathrm{Predecessor}(x) &\Longleftrightarrow& \forall e\in S \,\, R(e,x) \\ \\ \mathrm{pre}(x) &:=& \max\Bigl( \mathrm{Predecessor}(x) \Bigr) \end{array}
「整列帰納法」と呼ばれる帰納法で
\begin{array}{rcc} \min(S) && P\Bigl( \min(S) \Bigr) &⇒& P\Bigl( \min(S) \Bigr) \\ \\ \exists\mathrm{pre}(x) && \forall x \,\, \Bigl( P(\mathrm{pre}(x)) ⇒ P(x) \Bigr) &⇒& \forall x \,\, P(x) \\ \\ \lnot\exists\mathrm{pre}(x) && \forall x \Bigl( \Bigl( \forall e \,\, R(e,x)⇒P(e) \Bigr) ⇒ P(x) \Bigr) &⇒& \forall x \,\, P(x)\end{array}
これを採用する場合
「順序数の整列順序 \in 」に限らず
「任意の整列順序 R 」を使えるようになることから
\begin{array}{l} 0,1,2,3,...,n \\ \\ 0,1,2,3,...,n,...,ω,ω+1,...,ω+n,... \\ \\ a,b,c,d,e,f,g,h,...,x,y,z \end{array}
「数字」だけではなく
「記号・文字など」による帰納法の証明も可能になります。
（人間が感覚的に使っている帰納法はこれに近い）
直前という発想とその定義
↑ で出てきた『直前』という発想は
\begin{array}{ccc} xの直後 &\Longleftrightarrow& \min(xの後の集まり) \end{array}
「整列集合」故に「直後は必ず存在する」ことと
（後の集まりという部分集合の最小元は必ず存在する）
\begin{array}{ccc} xの直前 &\Longleftrightarrow& \mathrm{pre}(x) \end{array}
「後続順序数」「極限順序数」に相当する
「整列集合の要素」を区別したいという要望
\begin{array}{ccc} ？+1 &=& ω && × \end{array}
そして「極限順序数」が持つ
「１つ前が無い」という性質から得られていて
（１つ後は ω+1 という形で定義できる）
形式的には
\begin{array}{ccc} a<b &\to& <(a,b) \\ \\ α\in β &\to& \in (α,β) \\ \\ aRb &←& R(a,b) \end{array}
こういった流れで一般化できる
「整列順序 R 」の定義から
\begin{array}{ccc} R(a,b) &\Longleftrightarrow& aはbの前 \\ \\ R(a,b) &\Longleftrightarrow& bはaの後 \end{array}
「前」「後」という概念を得ることで
（厳密には含意だが同一と定義しても良い）
\begin{array}{ccc} e \in \mathrm{Predecessor}(x) &\Longleftrightarrow& \forall e\in S \,\, R(e,x) \\ \\ \mathrm{pre}(x) &:=& \max\Bigl( \mathrm{Predecessor}(x) \Bigr) \end{array}
厳密に定義されています。
（この段階だとこれはまだ得られない）
ここで出てくる「最大値」
\begin{array}{ccc} n \in N & n< ω \end{array}
これの由来が「極限順序数 ω 」の性質で
（無限集合内に最大値は基本的に存在しない）
\begin{array}{ccc} xの前の集まり &\Longleftrightarrow& \mathrm{Predecessor}(x) \end{array}
\begin{array}{ccc} \mathrm{Predecessor}(x) &:=& \{ e\in S \mid R(e,x) \} \end{array}
この「 x の前」の中での「最大」が
\begin{array}{ccc} \mathrm{pre}(x) &:=& \max\Bigl( \mathrm{Predecessor}(x) \Bigr) \end{array}
「直前 \mathrm{pre} 」の厳密な定義になります。
（整列集合は最大元の存在を保証しない）
整列帰納法と超限帰納法
これを使って場合分けしたのが
\begin{array}{rcc} \min(S) && P\Bigl( \min(S) \Bigr) &⇒& P\Bigl( \min(S) \Bigr) \\ \\ \exists\mathrm{pre}(x) && \forall x \,\, \Bigl( P(\mathrm{pre}(x)) ⇒ P(x) \Bigr) &⇒& \forall x \,\, P(x) \\ \\ \lnot\exists\mathrm{pre}(x) && \forall x \Bigl( \Bigl( \forall e \,\, R(e,x)⇒P(e) \Bigr) ⇒ P(x) \Bigr) &⇒& \forall x \,\, P(x)\end{array}
この「整列帰納法」の形で
より厳密には
\begin{array}{ccc} ω &\in& ω+1 \\ \\ \mathrm{pre}(ω+1) &\in& ω+1 \end{array}
ω より大きな ω+1 は「後続順序数」であり
「直前」を持つことから
\begin{array}{ccc} \forall λ \Bigl( \Bigl( \forall β\in λ \,\, P(β) \Bigr) ⇒ P(λ) \Bigr) &⇒& \forall λ \,\, P(λ) \end{array}
３つ目の定義（直前を持たず後者を定義できない）は
「極限順序数 λ 」にのみ適用という形で分離できるので
↑ の「整列集合 (S,R) 」の部分を
「順序数 (α,\in) 」にすれば
\begin{array}{rcc} \min(α) && P\Bigl( \min(α) \Bigr) &⇒& P\Bigl( \min(α) \Bigr) \\ \\ \exists \mathrm{pre}(α) && \forall α \,\, \Bigl( P(α) ⇒ P(α+1) \Bigr) &⇒& \forall α \,\, P(α) \\ \\ \lnot\exists \mathrm{pre}(λ) && \forall λ \Bigl( \Bigl( \forall β\in λ \,\, P(β) \Bigr) ⇒ P(λ) \Bigr) &⇒& \forall λ \,\, P(λ)\end{array}
より厳密かつ詳細な
「超限帰納法」の形を得ることができます。
（先に紹介した超限帰納法の形でも特に問題は無い）
ε-帰納法
そして「整列集合」も飛び越えて
\begin{array}{ccc} \mathrm{Well}\text{-}\mathrm{Order}(S,R) && {} && \mathrm{Set}(A) \\ \\ x\in S &&\to && A \end{array}
更に「一般的な集合」にまで拡張されたのが
「ε-帰納法」と呼ばれる帰納法で
\begin{array}{ccr} 整列 &\to& 一番下が分かる \\ \\ 整礎 &\to&局所的に一番下が分かる \end{array}
これは「整列性」を「整礎性」にまで抽象化した
（一直線の並びから分岐した階層構造の並びへ）
\begin{array}{rcc} \forall A \Bigl( \Bigl( \forall B\in A \,\, P(B) \Bigr) ⇒ P(A) \Bigr) &⇒& \forall A \,\, P(A)\end{array}
「基礎公理」に由来する概念になります。
（極小元が必ず存在することから発想できる）
極小元の存在と階層構造
これは「帰属関係 \in 」と「整列原理」
主にこの２つから発想できる帰納法で
\begin{array}{ccc} &U \\ \\ A&B&C \\ \\ &b_1 & c_1,c_2 \\ \\ &b_{11} \end{array}
例えばこのような集合を考えた時
\begin{array}{ccl} U&=&\{A,B,C\} \\ \\ B&=&\{b_1\} \\ \\ C &=& \{c_1,c_2\} \\ \\ b_1&=&\{b_{11}\} \end{array}
U に「整列帰納法」を当て嵌めてみると
（ P(U) の成立を帰納的に求めようとしてみる）
\begin{array}{lcl} P(b_{11})&⇒&P(b_{1}) \\ \\ P(c_1)∧P(c_2) &⇒&P(C) \\ \\ P(b_1) &⇒& P(B) \\ \\ P(A)∧P(B)∧P(C) &⇒& P(U) \end{array}
下の方から考えていけば
それぞれこのような形に分解できるので
階層がどのようになっていようと
「全ての集合の全ての要素」を調べてしまえば
\begin{array}{ccc} \forall X \,\, P(X) &⇒& P(U) \end{array}
帰納法の形になることは明らかです。
（直線的じゃなくても局所的な底が分かれば良い）
ドメインを順序数から集合へ
これは「整列原理」を根拠として
本質的にはドメインを変更したものでしかなく
（どのような集合と要素の関係も整列順序を持つ）
\begin{array}{ccc} 順序数 &\to& 整列原理+集合 \\ \\ 超限帰納法 &\to& ε\text{-}帰納法 \end{array}
「添え字（インデックス）」や「並び」の
「自由さ」を上げているだけで
\begin{array}{rcc} \forall A \Bigl( \Bigl( \forall B\in A \,\, P(B) \Bigr) ⇒ P(A) \Bigr) &⇒& \forall A \,\, P(A)\end{array}
正しさの根底にあるのは
変わらず「超限帰納法」になります。
（この A のドメインは集合全体になる）
実際、この帰納法の「集合」から
\begin{array}{ccc} A,B \in \mathrm{SET} &&\to&& α,β \in \mathrm{ON} \end{array}
「順序数」だけを選ぶと
（順序数は集合の１つ）
\begin{array}{lcl} \forall A \Bigl( \Bigl( \forall B\in A \,\, P(B) \Bigr) ⇒ P(A) \Bigr) &⇒& \forall A \,\, P(A) \\ \\ \forall α \Bigl( \Bigl( \forall β\in α \,\, P(β) \Bigr) ⇒ P(α) \Bigr) &⇒& \forall α \,\, P(α) \end{array}
そのまま「超限帰納法」の形が得られますし
（これは順序数の一般形から得られる形）
「整列原理」を考えれば
（整列順序が存在する）
\begin{array}{lcl} \forall α \Bigl( \Bigl( \forall β\in α \,\, P(β) \Bigr) ⇒ P(α) \Bigr) &⇒& \forall α \,\, P(α) \\ \\ \forall A \Bigl( \Bigl( \forall B\in A \,\, P(B) \Bigr) ⇒ P(A) \Bigr) &⇒& \forall A \,\, P(A) \end{array}
逆も成立すると言えます。
（集合側の並びに順序数の番号を当てられる）