Buchholz、Cichon、Weiermannの論文「A Uniform Approach to Fundamental Sequences and Hierarchies[1]」を基に、よい基本列の特徴付けについて考えます。
文章中の命題番号は全て[BCW][1]によるものです。
定義
\(\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\) がノルム付きバッハマン系であるとき、以下が成り立つ:
|
証明. 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]でも一般の基本列系に関してはそれほど深堀りされてはいない。
バッハマン系とノルムの相互関係
基本列系 \(\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\}\) で与える。このとき、
|
定理 (Theorem 4.a) |
---|
\(N:\tau\to\mathbb{N}\) は \(\tau\) 上のノルムであり、さらに
の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\) はノルム付きバッハマン系である:
|
例
[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,... |
例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,... |
例3.\(\alpha<\varepsilon_0\) に対して、\(N_3(\alpha)\) を以下で定める:
- \(\begin{align}N_3(0)&= 0\\ N_3(\omega^{\alpha_1}+\cdots+\omega^{\alpha_m})&=1+N_3(\alpha_1)+\cdots+N_3(\alpha_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)\) | 3,4,5,6,7,... |
\(N_3(\omega^2+n)\) | 3,4,5,6,7,... |
参考文献
- ↑ 1.0 1.1 [BCW] Buchholz, W., Cichon, A., Weiermann, A.: A Uniform Approach to Fundamental Sequences and Hierarchies. Mathematical Logic Quarterly, 40 (1994), pp. 273–286. doi:10.1002/malq.19940400212