よい基本列の考察（Buchholz, Cichon, Weiermannによる）

Buchholz、Cichon、Weiermannの論文「A Uniform Approach to Fundamental Sequences and Hierarchies」を基に、よい基本列の特徴付けについて考えます。

文章中の命題番号は全て[BCW]によるものです。番号のないものはMerlibornによるものです。

定義

\(\tau\) は \(\omega^\omega\)の倍数 (\(\exists \tau_0.\tau=\omega^\omega\cdot\tau_0\) )である0でない順序数とする。\(\tau\) に対して \(\mathrm{Lim}_\tau\) を、\(\tau\) より小さく0でない極限順序数の集合とする。また、\(\tau\) に対して、\(\_[\_]\) および \(N\) はそれぞれ写像\(\_[\_]:\tau\times\mathbb{N}\to \tau\)、\(N:\tau\to\mathbb{N}\)とする。

写像 \(\_[\_]\) が基本列系 (system of fundamental sequences) である、あるいは基本列の割り当て (assignment of fundamental sequences) とは、次の条件 (B1-a)～(B1-c) を満たすことである：

(B1)　\(\forall\alpha<\tau.\forall n<\omega.\)

(B1-a)　\(0[n]=0\)

(B1-b)　\((\alpha+1)[n]=\alpha\)

(B1-c)　\(\alpha\in\mathrm{Lim}_\tau\Longrightarrow\alpha[n]<\alpha[n+1]<\alpha\)

以下 \(\_[\_]\) は基本列系とする。

\(\langle\tau,\_[\_]\rangle\) がバッハマン系 (Bachmann system) とは、次の条件 (B2) を満たすことである：

(B2)　\(\forall\alpha,\beta<\tau.\forall n<\omega.\alpha[n]<\beta<\alpha\Longrightarrow\alpha[n]\leq\beta[0]\)

\(\_[\_]\) が \(N\) と両立 (compatible with \(N\)) する、そして \(\langle\tau,\_[\_],N\rangle\) がノルム付きバッハマン系 (normed Bachmann system) であるとは、次の (B3), (B4) を満たすことである：

(B3)　\(\forall\alpha,\beta<\tau.\forall n<\omega.\alpha[n]<\beta<\alpha\Longrightarrow N(\alpha[n])< N(\beta)\)

(B4)　\(\forall\alpha\in\mathrm{Lim}_\tau.N(\alpha)\leq N(\alpha[0])+1\)

バッハマン系 \(\langle\tau,\_[\_],N\rangle\) が正則 (regular)とは、次の条件を満たすことである：

\(\forall\beta<\alpha<\tau.\beta\leq\alpha[N(\beta)]\)

\(N\) が \(\tau\) 上のノルムであるとは、次の条件を満たすことである：

\(\forall\alpha<\tau.\forall n<\omega.\#\{\beta<\alpha\mid N(\beta)\leq n\}<\omega\)

基本的な性質

各語が定義する概念の関係性を確認しておく。

補題 (Lemma 1)
\(\langle\tau,\_[\_],N\rangle\) がノルム付きバッハマン系であるとき、以下が成り立つ： \(\langle\tau,\_[\_],N\rangle\) はバッハマン系である。 \(N\) は \(\tau\) 上のノルムである。 \(\langle\tau,\_[\_],N\rangle\) は正則バッハマン系である。

証明． 1. \(\alpha[n]<\beta<\alpha\) と \(\beta[0]<\alpha[n]\) を仮定する。このとき、(B1), (B3), (B4) の各条件から

\(N(\alpha[n])< N(\beta)\leq N(\beta[0])+1\leq N(\alpha[n])\)

が従うため、矛盾する。従って \(\alpha[n]<\beta<\alpha\) ならば \(\alpha[n]\leq\beta[0]\) である。

2. まず以下の主張を示す：

(*)　\(\{\beta<\alpha\mid N(\beta)\leq n\}\subseteq \{\beta<\alpha[n]\mid N(\beta)\leq n\}\)

\(\alpha\notin\mathrm{Lim}_\tau\) の場合は明らかなので、\(\alpha\in\mathrm{Lim}_\tau\) の場合について考える。このとき、任意の \(n<\omega\) について \(N(\alpha[n])< N(\alpha[n+1])\) が成り立つため、\(n\leq N(\alpha[n])\) である。一方、\(\beta<\alpha\) について (B3) から \(N(\beta)\leq N(\alpha[n])\Longrightarrow \beta\leq\alpha[n]\) が成り立つため、上記 (*) が成り立つ。

(*) から、\(\alpha\) についての帰納法によって \(N\) がノルムとなることが示される。

3. \(\alpha\notin\mathrm{Lim}_\tau\) の場合は明らかに \(\forall\beta<\alpha.(\beta\leq\alpha[N(\beta)])\) が成り立つため、以下 \(\alpha\in\mathrm{Lim}_\tau\) の場合について考える。(B3) より \(\forall n<\omega.n\leq N(\alpha[n])\) であり、特に \(N(\beta)\leq N(\alpha[N(\beta)])\) である。(B3) から \(\forall\beta<\alpha. N(\beta)\leq N(\alpha[N(\beta)])\Longrightarrow \beta\leq\alpha[N(\beta)]\) を得られるため、\(\forall\beta<\alpha.\beta\leq\alpha[N(\beta)]\) が示される。\(\square\)

命題 (Lemma 3.e)
バッハマン系 \(\langle\tau,\_[\_]\rangle\) に対して、\(\alpha\in\mathrm{Lim}_\tau\Longrightarrow\alpha=\sup\{\alpha[n]\mid n\in\mathbb{N}\}\)

証明．\(\alpha\in\mathrm{Lim}_\tau\) かつ \(\sup\{\alpha[n]\mid n\in\mathbb{N}\}=\beta<\alpha\) を仮定する。このとき \(\beta\in\mathrm{Lim}_\tau\) が成り立つ。\(\langle\tau,\_[\_]\rangle\) がバッハマン系であることから \(\forall n<\omega.\alpha[n]\leq\beta[0]\) が成り立つため \(\beta=\sup\{\alpha[n]\mid n\in\mathbb{N}\}\leq\beta[0]\) が成り立つが、\(\beta\in\mathrm{Lim}_\tau\) より \(\beta[0]<\beta\) であるため矛盾。\(\square\)

従って、通常基本列の定義とされているものはこの論文におけるバッハマン系と似た概念であることがわかる。実際、バッハマン系の性質がよいために[BCW]でも一般の基本列系に関してはそれほど深堀りされてはいない。

一方で、バッハマン系は基本列とされていた定義よりも強い条件である。実際、Wainer階層に使われる一般的な基本列を基本列系に単純に拡張すると、これはバッハマン系にならない (後述)。

バッハマン系とノルムの相互関係

基本列系 \(\langle\tau,\_[\_]\rangle\) に対して、\(\alpha[0]^0=\alpha,\) \(\alpha[0]^{i+1}=\alpha[0]^i[0]\) とする。

補題 (Lemma 2)
基本列系 \(\langle\tau,\_[\_]\rangle\) に対して、写像 \(G:\tau\to\mathbb{N}\) を \(G(\alpha)=\min\{i\mid\alpha[0]^i=0\}\) で与える。このとき、 任意の \(\alpha<\tau\) について \(\#\{\beta<\tau\mid\beta[0]=\alpha\}<\omega\) が成り立つならば、\(G\) は \(\tau\) 上のノルムである。 \(\langle\tau,\_[\_]\rangle\) がバッハマン系ならば、\(\langle\tau,\_[\_],G\rangle\) はノルム付きバッハマン系である。

定理 (Theorem 4.a)

\(N:\tau\to\mathbb{N}\) は \(\tau\) 上のノルムであり、さらに \(\forall\alpha<\tau.N(0)\leq N(\alpha)\) \(\forall\alpha<\tau.N(\alpha+1)\leq N(\alpha)+1\) の2条件を満たす。また、写像 \(p:\tau\to\mathbb{N}\) は \(N(\alpha)\leq p(\alpha)+1\leq p(\alpha+1)\) を満たすとする。 写像 \(\_[\_]:\tau\times\mathbb{N}\to\tau\) を次で定めるとき、\(\langle\tau,\_[\_],N\rangle\) はノルム付きバッハマン系である： \(\begin{align}0[n]&=0\\ \alpha[n]&=\max\{\beta<\alpha\mid N(\beta)\leq p(\alpha+n)\}\end{align}\)

例

ブーフホルツらによる例

[BCW] にはノルムの例として3種類の \(\varepsilon_0\) 上のノルムが紹介されて、さらにそれらから構成される基本列系がどれもノルム付きバッハマン系となり、さらに誘導されるハーディ階層の全体がどれも等しくなることが示されている。

以下でノルム \(N_i\) を定義する。

例1．\(\alpha<\varepsilon_0\) に対して、\(N_1(\alpha)\) を以下で定める：

\(\begin{align}N_1(0)&=0\\ N_1(\alpha)&=1+\max\{N_1(\alpha_1),N_1(\alpha_2)\mid \alpha=\omega^{\alpha_1}+\alpha_2\}\end{align}\)

	\(n<\omega\) に対する値
\(N_1(n)\)	0,1,2,3,4,...
\(N_1(\omega+n)\)	2,3,4,5,6,...
\(N_1(\omega\cdot 2+n)\)	3,4,5,6,7,...
\(N_1(\omega^2+n)\)	3,4,5,6,7,...
\(N_1(\omega^\omega+\omega^3+n)\)	5,6,7,8,9,...

\(p_1:\varepsilon_0\to\mathbb{N}\) を、

\(\begin{align}p_1(n)&=n\quad(n<\omega)\\ p_1(\alpha)&=N_1(\alpha)-1\quad(\omega\leq\alpha)\end{align}\)

で定める。このとき、Theorem 4.a によってバッハマン系\(\_[\_]_1\)を定めたとき、

	\(\_[n]_1\) の値
\(\omega^\omega+\omega^3\)	\(\omega^\omega+\omega^2\cdot 2,\omega^\omega+\omega^2\cdot 3,\dots\)

例2．\(\alpha<\varepsilon_0\) に対して、\(N_2(\alpha)\) を以下で定める：

\(\begin{align}N_2(0)&=0\\ N_2(\alpha)&=\max\{1+N_2(\alpha_1),\dots,1+N_2(\alpha_m),m\mid\alpha=\omega^{\alpha_1}+\cdots+\omega^{\alpha_m},\alpha>\alpha_1\geq\cdots\geq\alpha_m\}\end{align}\)

	\(n<\omega\) に対する値
\(N_2(n)\)	0,1,2,3,4,...
\(N_2(\omega+n)\)	2,2,3,4,5,...
\(N_2(\omega\cdot 2+n)\)	2,3,4,5,6,...
\(N_2(\omega^2+n)\)	3,3,3,4,5,...
\(N_1(\omega^\omega+\omega^3+n)\)	5,5,5,5,6,...

\(p_2:\varepsilon_0\to\mathbb{N}\) を、

\(\begin{align}p_2(n)&=n\quad(n<\omega)\\ p_2(\omega\cdot\alpha'+n)&=N_2(\omega\cdot\alpha')+n-1\end{align}\)

で定める。このとき、Theorem 4.a によってバッハマン系\(\_[\_]_2\)を定めたとき、

	\(\_[n]_2\) の値
\(\omega^\omega+\omega^3\)	\(\omega^\omega+\omega^2\cdot 3,\omega^\omega+\omega^2\cdot 4,\cdots\)

例3．\(\alpha<\varepsilon_0\) に対して、\(N_3(\alpha)\) を以下で定める：

\(\begin{align}N_3(0)&= 0\\ N_3(\omega^{\alpha_1}+\cdots+\omega^{\alpha_m})&=N_3(\alpha_1)+\cdots+N_3(\alpha_m)+m\end{align}\)

	\(n<\omega\) に対する値
\(N_3(n)\)	0,1,2,3,4,...
\(N_3(\omega+n)\)	2,3,4,5,6,...
\(N_3(\omega\cdot 2+n)\)	4,5,6,7,8,...
\(N_3(\omega^2+n)\)	3,4,5,6,7,...
\(N_1(\omega^\omega+\omega^3+n)\)	7,8,9,10,11,...

\(p_3:\varepsilon_0\to\mathbb{N}\) を、

\(\begin{align}p_3(n)&=n\quad(n<\omega)\\ p_3(\alpha)&=N_3(\alpha)-1\quad(\omega\leq\alpha)\end{align}\)

で定める。このとき、Theorem 4.a によってバッハマン系\(\_[\_]_3\)を定めたとき、

	\(\_[n]_3\) の値
\(\omega^\omega+\omega^3\)	\(\omega^\omega+\omega^2,\omega^\omega+\omega^2+1,\omega^\omega+\omega^2+\omega,\dots\)

Wainerの基本列系

Wainerなどによりよく知られた \(\varepsilon_0\) までの基本列を基本列系として表示することを考える。\(\alpha<\varepsilon_0\) に対して、基本列系 \(\langle\varepsilon_0,\_[\_]_W\rangle\) を以下で定義する。

\(\begin{align}0[n]_W&=0\\ (\alpha+1)[n]_W&=\alpha\\ (\omega^{\gamma+1}\cdot(\beta+1))[n]_W&=\omega^{\gamma+1}\cdot\beta+\omega^\gamma\cdot n\\ (\omega^\gamma\cdot(\beta+1))[n]_W&=\omega^\gamma\cdot\beta+\omega^{\gamma[n]_W}\quad(\gamma\in\mathrm{Lim}_\tau)\end{align}\)

命題
基本列系 \(\langle\varepsilon_0,\_[\_]_W\rangle\) はバッハマン系ではない。

証明．\(0<N<\omega\) を適当に固定する。このとき、\(\alpha=\omega^\omega, \beta=\omega^{N+1}\) とすると、\(\alpha[N]=\omega^N<\beta<\alpha\) かつ \(\beta[0]=0<\omega^N=\alpha[N]\) である。

回避方法の1つはとても単純で、\(\omega^{\beta+1}[0]=\omega^\beta\) とすることである。すなわち、

\(\begin{align}0[n]_U&=0\\ (\alpha+1)[n]_U&=\alpha\\ (\omega^{\gamma+1}\cdot(\beta+1))[n]_U&=\omega^{\gamma+1}\cdot\beta+\omega^\gamma\cdot(n+1)\\ (\omega^\gamma\cdot(\beta+1))[n]_U&=\omega^\gamma\cdot\beta+\omega^{\gamma[n]_U}\quad(\gamma\in\mathrm{Lim}_\tau)\end{align}\)

とすればよい。このとき、バッハマン系 \(\langle\varepsilon_0,\_[\_]_U\rangle\) に対して Lemma.2 によって誘導されるノルムは \(N_3\) と一致する。

また、\(\_[\_]_U\) で定まる各基本列は \(N_3\) と \(p_3\) から Lemma.2 によって定まる基本列の部分列になっているため、適当に \(p_U:\varepsilon_0\to\mathbb{N}\) を決めることにより、\(N_3\) と \(p_U\) から Lemma.2 によって定まる基本列として \(\_[\_]_U\) を復元できることもわかる。

考察

(Googology的に) 良いふるまいをするノルムの条件の1つとして、以上の観察結果から次の2条件が挙げられる：

\(N(0)=0\)

\(N(\alpha+1)=N(\alpha)+1\)

\(N_1,N_3,N_U\) はこの条件を満たす。また、この2条件は Theorem 4.a よりも強い条件を課しているため、適切な \(p:\tau\to\mathbb{N}\) を選ぶことによりよい基本列系を選べる可能性が生まれる。

一方で、0と1の算術的な性質の影響により、記法から自然に考えられる基本列系ですらバッハマン系とならない可能性が示されている。これに関しては、例えば条件 (B2) を次の (Q2) に弱めたものを擬バッハマン系とすることで包括ができるかもしれない。

(Q2)　\(\forall\alpha,\beta<\tau.\forall n<\omega.(\alpha[n]<\beta<\alpha\Longrightarrow \alpha[n]\leq\beta[1])\)

この定義によって何かしらの特徴付けや定理が得られるかは現状わからない。ただ見栄えがよくなりやすいだけかもしれない。