低基底定理
low basis theorem
ここでは木は可算集合$ \Gammaの有限列の集合であって以下を満たすものとする $ \sigma \preceq \tauかつ$ \tau \in Tならば$ \sigma \in T
木の道の集合を$ [T] とする
$ [T] \coloneqq \{s \colon \omega \to \Gamma\ |\ \forall_n [s\upharpoonright_n \in T]\}
有限列$ \sigma \in \Gamma^{<\omega}と比較可能な$ Tの有限列の集合を$ T_\sigmaとする
$ T_\sigma \coloneqq \{\tau \in T\ |\ \sigma \preceq \tau \lor \tau \preceq \sigma\}
以下を満たす計算可能関数$ F \colon \omega \to \omegaが存在するとき, $ \Delta_1-estimatedであるという 任意の$ \sigma \in Tについて$ \sigma < F(|\sigma|)
有限列は適当な方法で$ \omegaにコードされているとする
任意の$ n \in \omegaについて$ |\sigma| = nとなる$ \sigma \in Tが存在するとき、$ Tを非有界であるという 補題
$ T_\sigmaが非有界ならばある$ z \in \Gammaが存在して$ T_{\sigma^\frown \braket{z}}は非有界
記法
定理
すなわち$ Z^\prime \le_\mathrm T \emptyset^\prime となるような道$ Z \in [T] が存在する
証明の概略.
$ Zの断片$ \sigma_eと並行して$ Z^\primeの部分的な進行$ \{i < e|i \notin W^Z_{i}\}の情報がコードされた列$ c_eを定義する
Proof.
定義
要件
ステップ$ e, 有限列$ \sigmaについて要件$ \mathcal R_i(\sigma), 集合$ T_\sigma^cを以下のように定義する $ \mathcal R_i(\sigma) \equiv i \notin W_{i, |\sigma|}^{\sigma}
$ T_\sigma^c \coloneqq \{\mu \in T_{\sigma}\ |\ (\forall i < |c|)[(c)_i = 1 \implies \mathcal R_i(\mu)]\}
$ (c)_i = 1となる$ iにのみ$ \mathcal R_i(\mu)であるような$ \sigmaとcomparableな$ \muの集合
定義
$ e \in \omegaについて長さ$ eの$ \Gamma有限列$ \sigma_e, $ 2の有限列$ c_eを定義する. また同時に$ T_{\sigma_e}^{c_e}が非有界であることを示す
$ 0
$ (\sigma_0, c_0) \coloneqq (\emptyset, \emptyset)
$ T_\emptyset^\emptyset = Tは仮定より非有界
$ e + 1
$ \emptyset^\primeの神託を用いて$ T_{\sigma_e}^{c_e^\frown\braket{1}}が非有界であるか決定する
$ T が非有界$ \iff $ (\forall n)(\exists \sigma < F(n))[\sigma \in T] より
ケース1: $ T_{\sigma_e}^{c_e^\frown\braket{1}}が非有界であるとき
$ \Longleftrightarrow 道$ b \subseteq T_{\sigma}が存在して任意の$ nについて$ \mathcal R_e(b\upharpoonright_n)は真偽を変えない
$ (\sigma_{e+1}, c_{e+1}) \coloneqq (\sigma_e^\frown\braket{z}, c_e^\frown \braket{1})
$ T_{\sigma_e^\frown \braket{z}}^{c_e^\frown\braket{1}}が非有界となるような$ zを選ぶ
ケース2: $ T_{\sigma_e}^{c_e^\frown\braket{1}}が有界であるとき
$ \Longleftrightarrow あらゆる道$ b \subseteq T_{\sigma}はある$ nについて$ \mathcal \lnot \mathcal R_e(b\upharpoonright_n)
$ (\sigma_{e+1}, c_{e+1}) \coloneqq (\sigma_e^\frown\braket{z}, c_e^\frown \braket{0})
$ T_{\sigma_e^\frown \braket{z}}^{c_e^\frown\braket{0}}が非有界となるような$ zを選ぶ
$ T_{\sigma_e^\frown \braket{z}}^{c_e^\frown\braket{0}} = T_{\sigma_e^\frown \braket{z}}^{c_e}なので低基底定理#65851c824507aa00004aaeacより$ z; \sigma_e^\frown\braket{z} < F(e)は存在する $ Z \coloneqq \{\sigma_e\ |\ e\in \omega\}とする
定義より$ Z \in [T]
ここで
$ e \in Z^\prime \iff e \in W^Z_{e}
$ \iff ある$ nが存在して任意の$ \sigma \succeq Z\upharpoonright_nについて$ \lnot\mathcal R_e(\sigma)
$ \iff $ T_{\sigma_e}^{c_e^\frown\braket{1}}は有界
$ \iff c_{e+1}(e) = 0
より$ Z^\prime \le_\mathrm T \emptyset^\prime