Bachmann–Howard順序数(Bachmann–Howard ordinal)とは、最初の非可算順序数 $\Omega$ を使う崩壊関数 $\psi$ により $\psi(\varepsilon_{\Omega+1})$ と定まる可算順序数である。$\psi(\alpha)$ は、$\rho$ 未満の順序数と $0$、$\Omega$ から和・$\omega$ の冪・$\alpha$ 未満の引数での $\psi$ で書ける可算順序数の全体が $\rho$ になる最小の $\rho$ で、$\varepsilon$ 数である。$\alpha\le\zeta_0$ で $\psi(\alpha)=\varepsilon_\alpha$、$\zeta_0\le\alpha\le\Omega$ で $\zeta_0$ にとどまる。無限公理を含む KP 集合論の証明論的順序数である。
Bachmann–Howard 順序数(Bachmann–Howard ordinal)は、最初の非可算順序数 $\Omega$ を「名前」として使う 崩壊関数 $\psi$ によって $\psi(\varepsilon_{\Omega+1})$ と定義される可算順序数である。Kripke–Platek集合論 に無限公理を加えた理論 $\mathsf{KP}$ の証明論的順序数がこの順序数であることが知られており、順序数解析 で、崩壊関数による順序数の表記を使う代表的な値として現れる。
Veblen の関数は、順序数の関数の不動点を数え上げることを下から繰り返して大きな順序数に名前をつける(順序数解析 の節「より大きな順序数を書き表す」)。崩壊関数は逆に、非可算な $\Omega$ まで含めた名前の体系を作り、その中で可算な部分を切り取る。$\Omega$ は可算順序数を作る材料として使われるだけで、値はすべて可算である。この考えは Bachmann(1950 年)に始まる(Rat06 p. 55)。
この記事では、Rathjen の形の崩壊関数を定義し、値がいつも定まり可算な $\varepsilon$ 数になること、単調性と連続性(prop-bh-basic)、最初の値の計算(thm-bh-values)を証明する。値は $\alpha\le\zeta_0$ では $\varepsilon_\alpha$ だが、$\zeta_0\le\alpha\le\Omega$ では $\zeta_0$ で止まり、$\Omega$ を引数に入れて初めて先へ進む。$\mathsf{KP}$ の順序数解析は主張と所在だけを述べる。
以下 $\Omega:=\omega_1$(最初の非可算順序数)とする。$\Omega$ 未満の順序数は可算順序数で、可算順序数の和と $\omega$ の冪は可算なので、$\Omega$ 未満の順序数は $+$ と $\xi\mapsto\omega^\xi$ で閉じている(Cantor標準形 の命題「指数が順序数自身に等しくなる場合」の 3 の証明の評価 $\lvert\omega^\gamma\rvert\le\max(\aleph_0,\lvert\gamma\rvert)$)。可算順序数の可算集合の上限は可算である。
$\omega^\xi=\xi$ となる $\xi$ を $\varepsilon$ 数 という(Cantor標準形 の定義「$\varepsilon$ 数」)。写像 $\xi\mapsto\omega^\xi$ は正規関数なので、順序数解析 の命題「正規関数の不動点」により、$\varepsilon$ 数を小さい順に並べた $\xi\mapsto\varepsilon_\xi$ も正規関数である。$\xi<\Omega$ なら $\varepsilon_\xi<\Omega$ である(可算な $\beta$ から $\omega$ の冪を可算回繰り返した上限は $\beta$ より大きい可算な $\varepsilon$ 数なので、$\Omega$ 未満の $\varepsilon$ 数は $\Omega$ の中で非有界で、その全体の順序型は $\Omega$ になる)。$\Omega$ 自身も $\varepsilon$ 数である(Cantor標準形 の命題「指数が順序数自身に等しくなる場合」の 3)。$\varepsilon_\xi=\xi$ となる最小の $\xi$ を $\zeta_0$ と書く($\varepsilon_0,\varepsilon_{\varepsilon_0},\dots$ の上限で、可算である)。正規関数は $\varepsilon_\xi\ge\xi$ を満たすので(Cantor標準形 の補題「和・積・冪の基本法則」の 4)、$\xi<\zeta_0$ なら $\xi<\varepsilon_\xi$ である。
順序数 $\alpha$ についての超限再帰で、順序数 $\beta$ ごとに集合 $C(\alpha,\beta)$ と順序数 $\psi(\alpha)$ を次のように定める(Rat06 (8)・(9)、p. 60)。
$\Omega$ より大きい最小の $\varepsilon$ 数を $\varepsilon_{\Omega+1}$ と書く。$\psi(\varepsilon_{\Omega+1})$ を Bachmann–Howard 順序数 という(Rat06 pp. 60–61)。
$C(\alpha,\beta)$ は「$\beta$ 未満の順序数と $0$、$\Omega$ から、和・冪・$\alpha$ 未満の引数での $\psi$ を有限回使って書ける順序数」の全体である。$\psi(\alpha)$ は、そのように書ける可算順序数がちょうど $\rho$ 未満の順序数になる最初の $\rho$ である。2 の集合が空でないことは prop-bh-basic の 1 で示す。この $\psi$ は $\Omega$ の添字の $\psi_\Omega$ とも書かれ、$\psi(\alpha)$ は $\Omega$ の $\alpha$ 番目の 崩壊(collapse)とよばれる(Rat06 p. 60)。
すべての順序数 $\alpha$ について次が成り立つ。
1. $\alpha$ についての帰納法で、$\xi<\alpha$ なら $\psi(\xi)$ は定まり可算であると仮定する。$\rho$ が可算なら $C(\alpha,\rho)$ は可算である。実際、$D_0:=\rho\cup\{0,\Omega\}$、$D_{k+1}:=D_k\cup\{\xi+\eta,\ \omega^\xi\mid\xi,\eta\in D_k\}\cup\{\psi(\xi)\mid\xi\in D_k,\ \xi<\alpha\}$ とおくと、各 $D_k$ は可算で、$\bigcup_kD_k$ は 3 つの操作で閉じているので $C(\alpha,\rho)$ に等しい。
$\rho_0:=0$ とし、$\rho_{k+1}$ を $C(\alpha,\rho_k)\cap\Omega$ のすべての元より大きい最小の順序数とする。これは可算順序数の可算集合の上限以下なので可算である。$\rho_k\subseteq C(\alpha,\rho_k)\cap\Omega$ なので $\rho_k\le\rho_{k+1}$ である。$\rho:=\sup_k\rho_k$ は可算である。$\bigcup_kC(\alpha,\rho_k)$ は $\rho\cup\{0,\Omega\}$ を含み($\rho=\bigcup_k\rho_k$)、操作の引数は有限個なのでどれもある $C(\alpha,\rho_k)$ に入り、3 つの操作で閉じている。よって $C(\alpha,\rho)=\bigcup_kC(\alpha,\rho_k)$ で、
$$
C(\alpha,\rho)\cap\Omega=\bigcup_k\bigl(C(\alpha,\rho_k)\cap\Omega\bigr)\subseteq\bigcup_k\rho_{k+1}=\rho
$$
である。逆の包含 $\rho\subseteq C(\alpha,\rho)\cap\Omega$ は定義から成り立つ。したがって定義 2 の集合は $\rho$ を含み、$\psi(\alpha)\le\rho$ は可算である。
2. $\psi(\alpha)$ の定義そのものである。
3. $\rho:=\psi(\alpha)$ とおく。$\xi,\eta<\rho$ なら $\xi,\eta\in C(\alpha,\rho)$ で、$\xi+\eta$ と $\omega^\xi$ は $C(\alpha,\rho)$ に属す可算順序数なので、2 により $\rho$ 未満である。$0\in C(\alpha,\rho)\cap\Omega$ なので $\rho\ge1$ で、$\xi<\rho$ なら $\xi+1=\xi+\omega^0<\rho$ だから $\rho$ は極限順序数である。冪の連続性から $\omega^\rho=\sup_{\xi<\rho}\omega^\xi\le\rho$ で、逆向きの $\omega^\rho\ge\rho$ と合わせて $\omega^\rho=\rho$ である。
4. 引数の範囲が広いほど閉包は大きいので $C(\alpha,\beta)\subseteq C(\alpha',\beta)$ である。$\rho':=\psi(\alpha')$ とすると $\rho'\subseteq C(\alpha,\rho')\cap\Omega\subseteq C(\alpha',\rho')\cap\Omega=\rho'$ なので、$C(\alpha,\rho')\cap\Omega=\rho'$ で、$\psi(\alpha)\le\rho'$ である。
5. $\rho_n:=\psi(\alpha_n)$ は 4 により広義増加で、$\rho:=\sup_n\rho_n$ は可算である。4 により $\psi(\alpha)\ge\rho$ である。$U:=\bigcup_nC(\alpha_n,\rho_n)$ とおく。$C(\alpha_n,\rho_n)$ は $n$ について増加するので、$U$ は $\rho\cup\{0,\Omega\}$ を含み、和と冪で閉じている。$\xi\in U$、$\xi<\alpha$ なら、ある $m$ で $\xi\in C(\alpha_m,\rho_m)$ で、$\xi<\alpha_n$ となる $n\ge m$ をとれば $\psi(\xi)\in C(\alpha_n,\rho_n)\subseteq U$ である。よって $C(\alpha,\rho)\subseteq U$ で、2 により $C(\alpha,\rho)\cap\Omega\subseteq\bigcup_n\rho_n=\rho$ となる。したがって $\psi(\alpha)\le\rho$ である。$\square$
1 と 2 は Rat06 p. 60 に証明なしで述べられている。2 は、$\psi(\alpha)$ 未満の可算順序数は $\psi(\alpha)$ 未満の順序数を材料にして書け、$\psi(\alpha)$ 以上の可算順序数は書けないことを意味する。4 の不等号は狭義とは限らない(thm-bh-values の 2)。
$\alpha\le\Omega$ のとき、$\Omega$ を含む項は値が $\Omega$ 以上になり、$\psi$ の引数にならない。このため可算な部分だけを見ればよい。$\alpha$ と可算な $\rho$ について、$\rho\cup\{0\}$ を含み、和、冪、$\xi<\alpha$ での $\xi\mapsto\psi(\xi)$ で閉じた最小の集合を $K(\alpha,\rho)$ と書く。$\psi$ の値は可算なので(prop-bh-basic の 1)、$K(\alpha,\rho)$ は可算順序数からなる。
$\alpha\le\Omega$、$\rho<\Omega$ なら $C(\alpha,\rho)\cap\Omega=K(\alpha,\rho)$ である。
$K(\alpha,\rho)\subseteq C(\alpha,\rho)\cap\Omega$ は定義から従う。$D:=K(\alpha,\rho)\cup\{\gamma\in C(\alpha,\rho)\mid\gamma\ge\Omega\}$ とおくと、$D$ は $\rho\cup\{0,\Omega\}$ を含む。$\xi,\eta\in D$ のどちらかが $\Omega$ 以上なら、$\xi+\eta\ge\xi$、$\xi+\eta\ge\eta$、$\omega^\xi\ge\xi$(Cantor標準形 の補題「和・積・冪の基本法則」の 2・4)により結果も $\Omega$ 以上で、$C(\alpha,\rho)$ に属すので $D$ に属す。両方が $K(\alpha,\rho)$ に属せば結果も属す。$\xi\in D$、$\xi<\alpha$ なら $\xi<\Omega$ なので $\xi\in K(\alpha,\rho)$ で、$\psi(\xi)\in K(\alpha,\rho)$ である。よって $D$ は 3 つの操作で閉じ、$C(\alpha,\rho)\subseteq D$、すなわち $C(\alpha,\rho)\cap\Omega\subseteq K(\alpha,\rho)$ である。$\square$
順序数の集合 $X$ が $0$ を含み、和と $\xi\mapsto\omega^\xi$ で閉じているとする。順序数 $\gamma$ 未満の $\varepsilon$ 数がすべて $X$ に属すなら、$\gamma\subseteq X$ である。
$\beta<\gamma$ についての帰納法で $\beta\in X$ を示す。$\beta=0$ と、$\beta$ が $\varepsilon$ 数の場合は仮定による。そうでない $\beta>0$ を Cantor 標準形 $\beta=\omega^{\beta_1}+\cdots+\omega^{\beta_m}$($\beta_1\ge\cdots\ge\beta_m$)で書く(Cantor標準形 の定理「底 $\beta$ の展開の存在と一意性」)。$\beta_1\le\omega^{\beta_1}\le\beta$ で、$\beta$ は $\varepsilon$ 数でないので Cantor標準形 の命題「指数が順序数自身に等しくなる場合」の 1 により $\beta_1\ne\beta$ である。よってすべての $\beta_i$ は $\beta$ 未満で、帰納法の仮定から $X$ に属し、$X$ は和と冪で閉じているので $\beta\in X$ である。$\square$
$\varepsilon$ 数 $\varepsilon$ は和と冪で閉じている。$\xi<\varepsilon$ なら $\omega^\xi<\omega^\varepsilon=\varepsilon$ である。$\xi,\eta<\varepsilon=\sup_{\zeta<\varepsilon}\omega^\zeta$ なら $\xi,\eta<\omega^\zeta$ となる $\zeta<\varepsilon$ があり、$\xi+\eta<\omega^\zeta\cdot2\le\omega^{\zeta+1}<\varepsilon$ である。
1. $\alpha\le\zeta_0$ についての帰納法で示す。$\xi<\alpha$ では $\psi(\xi)=\varepsilon_\xi$ と仮定する。$\alpha\le\Omega$ なので lem-bh-countable-part が使える。
$K(\alpha,\varepsilon_\alpha)\subseteq\varepsilon_\alpha$:$\varepsilon_\alpha$ は $0$ を含み、和と冪で閉じ、$\xi<\alpha$ なら $\psi(\xi)=\varepsilon_\xi<\varepsilon_\alpha$ なので、$\varepsilon_\alpha\cup\{0\}$ を含み 3 つの操作で閉じている。
$\varepsilon_\alpha\subseteq K(\alpha,0)$:$\varepsilon_\alpha$ 未満の $\varepsilon$ 数は $\varepsilon_\xi$($\xi<\alpha$)なので、lem-bh-closure により、$\xi<\alpha$ で $\varepsilon_\xi\in K(\alpha,0)$ であることを示せばよい。$\xi$ についての帰納法による。$\eta<\xi$ で $\varepsilon_\eta\in K(\alpha,0)$ なら、lem-bh-closure により $\varepsilon_\xi\subseteq K(\alpha,0)$ である。$\xi<\zeta_0$ なので $\xi<\varepsilon_\xi$、よって $\xi\in K(\alpha,0)$ で、$\xi<\alpha$ だから $\psi(\xi)=\varepsilon_\xi\in K(\alpha,0)$ である。
$K$ は第 2 引数について単調なので、$\rho\le\varepsilon_\alpha$ なら $\varepsilon_\alpha\subseteq K(\alpha,0)\subseteq K(\alpha,\rho)$ である。したがって $C(\alpha,\rho)\cap\Omega=K(\alpha,\rho)$ は $\rho<\varepsilon_\alpha$ では $\rho$ に等しくなく、$\rho=\varepsilon_\alpha$ では $\varepsilon_\alpha$ に等しい。よって $\psi(\alpha)=\varepsilon_\alpha$ である。
2. $\zeta_0=\varepsilon_{\zeta_0}$ は和と冪で閉じている。$K(\alpha,\zeta_0)$ の元が $\zeta_0$ 未満であることを、作り方の段数についての帰納法で示す。和と冪はそのとおりで、$\psi$ を引数 $\xi<\zeta_0$ に使うと 1 により $\psi(\xi)=\varepsilon_\xi<\varepsilon_{\zeta_0}=\zeta_0$ である。よって $C(\alpha,\zeta_0)\cap\Omega=K(\alpha,\zeta_0)=\zeta_0$ で $\psi(\alpha)\le\zeta_0$ である。prop-bh-basic の 4 と 1 から $\psi(\alpha)\ge\psi(\zeta_0)=\varepsilon_{\zeta_0}=\zeta_0$ である。
3. $\Omega\in C(\Omega+1,\beta)$ で $\Omega<\Omega+1$ なので、2 により $\zeta_0=\psi(\Omega)\in C(\Omega+1,\beta)$ である。$\rho:=\varepsilon_{\zeta_0+1}$ とし、$D:=\rho\cup\{\gamma\in C(\Omega+1,\rho)\mid\gamma\ge\Omega\}$ とおく。$\rho$ は和と冪で閉じ、$\xi\le\Omega$ なら prop-bh-basic の 4 とこの定理の 2 により $\psi(\xi)\le\psi(\Omega)=\zeta_0<\rho$ なので、prf-bh-countable-part と同じ議論で $D$ は 3 つの操作で閉じている。よって $C(\Omega+1,\rho)\cap\Omega\subseteq\rho$ で、$\psi(\Omega+1)\le\rho$ である。逆に $\rho'<\rho$ とすると、$C(\Omega+1,\rho')$ は $C(\zeta_0,0)$ を含むので 1 の証明により $\zeta_0$ 未満の順序数をすべて含み、さらに $\zeta_0$ を含む。$\rho$ 未満の $\varepsilon$ 数は $\zeta_0$ 以下なので、lem-bh-closure により $C(\Omega+1,\rho')\supseteq\rho$ となり、$C(\Omega+1,\rho')\cap\Omega\ne\rho'$ である。よって $\psi(\Omega+1)=\rho$ である。$\square$
2 の「止まり」は崩壊関数の要点を示している。$\psi(\xi)$ を使うには引数 $\xi$ がすでに書けていなければならないが、$\Omega$ 未満の引数だけでは $\zeta_0$ 自身が書けない。非可算な $\Omega$ を名前として使い、$\psi(\Omega)=\zeta_0$ と書けるようになったことで、3 で先へ進む。$\zeta_0$ は Veblen の関数では $\varphi_2(0)$ である(順序数解析 の節「より大きな順序数を書き表す」の $\varphi_\alpha$)。
$\omega_0(\gamma):=\gamma$、$\omega_{k+1}(\gamma):=\omega^{\omega_k(\gamma)}$ とおく。
$\varepsilon_{\Omega+1}=\sup_k\omega_k(\Omega+1)$ であり、Bachmann–Howard 順序数は
$$
\psi(\varepsilon_{\Omega+1})=\sup_k\psi\bigl(\omega_k(\Omega+1)\bigr)
$$
を満たす可算な $\varepsilon$ 数で、$\varepsilon_{\zeta_0+1}$ 以上である。
$\omega^{\Omega+1}>\Omega+1$ なので、列 $\omega_k(\Omega+1)$ は狭義増加である(冪の狭義単調性による帰納法)。順序数解析 の命題「正規関数の不動点」の証明により、その上限 $\gamma$ は $\omega^\gamma=\gamma$ を満たし、$\gamma>\Omega$ である。$\Omega$ より大きい $\varepsilon$ 数 $\varepsilon$ は $\Omega+1\le\varepsilon$ を満たし、帰納法で $\omega_k(\Omega+1)\le\omega_k(\varepsilon)=\varepsilon$ なので $\gamma\le\varepsilon$ である。よって $\gamma=\varepsilon_{\Omega+1}$ である。$\varepsilon_{\Omega+1}$ は極限順序数なので、prop-bh-basic の 5 から等式が、1 と 3 から可算な $\varepsilon$ 数であることが従う。4 と thm-bh-values の 3 から $\psi(\varepsilon_{\Omega+1})\ge\psi(\Omega+1)=\varepsilon_{\zeta_0+1}$ である。$\square$
Bachmann–Howard 順序数が証明論で重要なのは次の定理による。
無限公理を含む Kripke–Platek 集合論 $\mathsf{KP}$ について、次が成り立つ。
この記事では証明しない。主張は Rat06 §2.3(pp. 60–61)による。そこでの $\mathsf{KP}$ の公理は外延性・対・和集合・無限・有界分出・有界収集・集合の帰納法で(同 p. 59)、Kripke–Platek集合論 の記事の体系に無限公理を加えたものである。$\Sigma$ 文は、有界な論理式から $\land,\lor$、有界な量化、有界でない存在量化で作られる文で、$L_\beta$ は構成可能階層の段階である(構成可能宇宙)。証明の筋は、$\mathsf{KP}$ の証明を、$C(\varepsilon_{\Omega+1},0)$ の順序数で長さを測る無限の導出に移し、$\Sigma$ 反映の規則によるカットを、$\psi$ を使って導出をつぶす(collapsing)ことで取り除くものである(同 p. 61)。$C(\varepsilon_{\Omega+1},0)$ は初等的に計算可能な順序数の表記系を与える(同 p. 60)。順序数解析 の記事の表で、$\mathsf{KP}$ の行の値がこの順序数である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| def-bh-collapse の「$\Omega$ は非可算」 | $\Omega$ の代わりに $\omega$ を使う | prop-bh-basic の 1($\psi(0)$ が定まること) |
| thm-bh-values の 1 の「$\alpha\le\zeta_0$」 | $\alpha=\zeta_0+1$ | $\psi(\alpha)=\varepsilon_\alpha$ |
| lem-bh-countable-part の「$\alpha\le\Omega$」 | $\alpha=\Omega+1$、$\rho=0$ | $C(\alpha,\rho)\cap\Omega=K(\alpha,\rho)$ |
| lem-bh-closure の「$\gamma$ 未満の $\varepsilon$ 数がすべて $X$ に属す」 | $X=\varepsilon_0$、$\gamma=\varepsilon_0+1$ | $\gamma\subseteq X$ |
1 行目:$\Omega$ を $\omega$ に替えると、$C(0,\rho)$ は $0$ と $\omega^0=1$ を含み和で閉じているので、すべての自然数を含む。定義 2 の条件は $\rho<\omega$ で $C(0,\rho)\cap\omega=\rho$ だが、左辺は $\omega$ で有限の $\rho$ に等しくない。よって $\psi(0)$ は定まらない。
2 行目:$\zeta_0<\zeta_0+1\le\Omega$ なので thm-bh-values の 2 により $\psi(\zeta_0+1)=\zeta_0$ である。正規関数は狭義増加なので $\varepsilon_{\zeta_0+1}>\varepsilon_{\zeta_0}=\zeta_0$ で、両者は等しくない。
3 行目:$C(\Omega+1,0)\cap\Omega$ は $\psi(\Omega)=\zeta_0$ を含む。$K(\Omega+1,0)$ では $\psi$ の引数は可算順序数だけなので、prf-bh-values の 2 と同じ帰納法でその元はすべて $\zeta_0$ 未満であり、$\zeta_0\notin K(\Omega+1,0)$ である。
4 行目:$\varepsilon_0$ は $0$ を含み和と冪で閉じているが、$\gamma$ 未満の $\varepsilon$ 数 $\varepsilon_0$ は $X$ に属さず、$\varepsilon_0\in\gamma\setminus X$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する