(第一の証明) 順序型 \(\alpha\) の整列順序 \(\langle X,{\triangleleft}\rangle\) が与えられたときに \({}^{<\omega}X\) の部分集合 \(T\) を, \(\triangleleft\) に関する(有限)降下列の全体と定めると, これは \({}^{<\omega}X\) の部分木になる. \(\triangleleft\)-無限降下列が存在しないことから \(T\) は整礎的な木である. この \(T\) の階数 \(\mathrm{rank}(T)\) が \(\alpha\) になることを \(\alpha\) に関する超限帰納法で証明する.
任意の要素 \(x_0\in X\) に対して, 集合 \(T_{x_0}\) を \[ T_{x_0}=\big\{\,s\in{}^{<\omega}X\,:\,\langle x_0\rangle^\frown s\in T\,\big\} \] と定める. これは 順序型 \(\mathrm{rank}(x_0,X,{\triangleleft})\) の整列順序 \(\langle\mathrm{pred}(x_0,X,{\triangleleft}),\,{\triangleleft}\rangle\) の要素の \(\triangleleft\)-降下列の全体がなす \({}^{<\omega}\mathrm{pred}(x_0,X,{\triangleleft})\) の部分木である. そこで, 帰納法の仮定として \(\mathrm{rank}(T_{x_0})=\mathrm{rank}(x_0,X,{\triangleleft})\) となっているものとしよう. すると \[ \mathrm{rank}(T)=\sup\big\{\,\mathrm{rank}(T_{x_0})+1\,:\,x_0\in X\,\big\}=\sup\big\{\,\mathrm{rank}(x_0,X,{\triangleleft})+1\,:\,x_0\in X\,\big\}=\alpha \] となることがわかる. (ここんところの細かいチェック, とくに第一の等号のチェックは略すけど, なに大丈夫ホントですから.)
いま \(\alpha\) が \(\kappa^+\) 未満の順序数であれば, 順序型 \(\alpha\) の整列順序 \(\langle X,{\triangleleft}\rangle\) を \(X\subset\kappa\) となるように取れるから, これについて上記の構成をすれば \({}^{<\omega}\kappa\) の整礎的な部分木で階数 \(\alpha\) のものが得られることになる.
(第二の証明) 選択公理を使って \(\kappa^+\) 未満の極限順序数 \(\alpha\) に対して単射 \(f_\alpha:\alpha\to\kappa\) を選ぶ. あとは \(\kappa^+\) までの超限再帰的定義で \(\langle\,T_\alpha\,:\,\alpha<\kappa^+\,\rangle\) を \[ T_\alpha=\begin{cases} 0,&(\alpha=0)\\ \{0\}\cup\{\,\langle0\rangle^\frown s\,:\,s\in T_\xi\,\},&(\alpha=\xi+1)\\ \{0\}\cup\bigcup_{\xi<\alpha}\{\,\langle f_\alpha(\xi)\rangle^\frown s\,:\,s\in T_\xi\,\},&(\alpha:\text{ limit}) \end{cases} \] と定義する. 超限帰納法によって \(\mathrm{rank}(T_\alpha)=\alpha\) を示すのは簡単だから詳細は略す.