弱Kőnigの補題

同義語:弱Königの補題weak Kőnig's lemmaweak König's lemma

概要

弱Kőnigの補題(weak Kőnig's lemma)とは、$0$ と $1$ の有限列からなる無限の木(先頭部分について閉じた集合)には無限の道がある、という主張で、選択公理なしに、いちばん左の道として証明できる。Cantor 空間のコンパクト性と同じ内容で、$[0,1]$ の Heine–Borel の定理は 2 進区間の木に当てはめて得られる。計算可能な無限 2 分木で計算可能な道をもたないものがある一方、低い道は必ずある(低基底定理)。逆数学では、この補題を加えた体系 $\mathsf{WKL}_0$ が Heine–Borel の定理や Brouwer の不動点定理などと同値になる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Königの補題, Cantor空間, 計算可能関数

弱Kőnigの補題(weak Kőnig's lemma)とは、$0$ と $1$ の有限列からなる無限の木には無限の道がある、という主張である。分岐が有限であるどの木にも無限の道があるという Königの補題 を、各頂点の子が $0$ と $1$ の 2 つに限られる 2 分木 に制限したものである。
主張そのものは易しく、選択公理も要らない(thm-wkl-main)。この補題が重要なのは、易しさの割に「強さ」をはかる物差しになるからである。$[0,1]$ の Heine–Borelの定理(可算個の開区間による被覆には有限部分被覆がある)は、2 進の区間の木に弱 Kőnig の補題を当てはめるだけで出る(thm-wkl-heine-borel)。逆に、Cantor空間 $2^\omega$ のコンパクト性はこの補題と同じ内容である(prop-wkl-compact)。一方で、計算可能な無限 2 分木で、計算可能な道を 1 本ももたないものがある(thm-wkl-kleene-tree)。道の存在は保証されるが、道を「計算して見つける」ことはできない。それでも、計算可能に近い道(低い道)は必ずある(thm-wkl-low-basis)。
逆数学 では、この補題を基礎の体系 $\mathsf{RCA}_0$ に加えた体系 $\mathsf{WKL}_0$ が、Heine–Borel の定理・最大値の定理・Brouwer の不動点定理などの多くの定理とちょうど同じ強さをもつ(rem-wkl-reverse)。

2 分木と道

$0,1$ の有限列の全体を $2^{<\omega}$ と書き、空列を $\langle\rangle$、列 $\sigma$ の長さを $|\sigma|$、$\sigma$ の後ろに $i\in\{0,1\}$ を付けた列を $\sigma^\frown i$ と書く。$\sigma$ が $\tau$ の先頭部分であることを $\sigma\preceq\tau$ と書く。$0,1$ の無限列(写像 $x\colon\mathbb{N}\to\{0,1\}$)の全体を $2^\omega$ とし、$x$ の最初の $n$ 項からなる列を $x\restriction n$ と書く。

2 分木と道
  1. $T\subset2^{<\omega}$ が 2 分木 であるとは、$\tau\in T$ かつ $\sigma\preceq\tau$ なら $\sigma\in T$ であることをいう。
  2. $x\in2^\omega$ が $T$ の 道(path)であるとは、すべての $n$ で $x\restriction n\in T$ であることをいう。$T$ の道の全体を $[T]$ と書く。
  3. $\sigma\in T$ について $T_\sigma:=\{\tau\in T\mid\sigma\preceq\tau\text{ または }\tau\preceq\sigma\}$ とおく。

長さ $n$ の列は $2^n$ 個しかないので、2 分木 $T$ が無限であることと、すべての $n$ で $T$ に長さ $n$ の列があることは同値である。

弱 Kőnig の補題

無限の 2 分木 $T$ には道がある。さらに、$T$ の道のうち辞書式順序で最小のもの(いちばん左の道)がある。

先が無限に続く側をたどる

$x(0),x(1),\dots$ を次の再帰で定める。$\sigma_n:=\langle x(0),\dots,x(n-1)\rangle$ とし、$T_{\sigma_n^\frown0}$ が無限なら $x(n):=0$、そうでなければ $x(n):=1$ とする。
すべての $n$ で $T_{\sigma_n}$ が無限であることを $n$ についての帰納法で示す。$T_{\sigma_0}=T$ は無限である。$T_{\sigma_n}$ が無限とする。$T_{\sigma_n}$ の元のうち長さが $n$ 以下のものは高々 $2^{n+1}$ 個なので、残りの無限個は $\sigma_n^\frown0$ か $\sigma_n^\frown1$ を先頭部分にもち、$T_{\sigma_n^\frown0}$ と $T_{\sigma_n^\frown1}$ の少なくとも一方は無限である。$x(n)$ の定め方から、$T_{\sigma_{n+1}}$ は無限である。
無限の $T_{\sigma_n}$ は空でないので、その元 $\tau$ で $\sigma_n\preceq\tau$ となるものがあり、木の条件から $\sigma_n\in T$ である。よって $x\in[T]$ である。
$y\in[T]$ が $x$ より辞書式順序で小さいとすると、最初に異なる番号 $n$ で $y(n)=0$、$x(n)=1$ であり、$y\restriction n=\sigma_n$ である。$x(n)=1$ だったので $T_{\sigma_n^\frown0}$ は有限だが、$y\restriction m$($m>n$)はすべて $T_{\sigma_n^\frown0}$ に属し、無限個ある。これは矛盾である。$\square$

この証明は各段で「$0$ の側を優先する」という規則で選ぶので、選択公理を使わない。分岐の数が有限でも、子に自然な順序がない木では事情が違い、一般の Königの補題は ZF の上で有限集合の可算選択公理と同値である(Königの補題 の定理「König の補題と有限集合の可算選択」)。

道が 1 本だけの木と、道が連続体濃度ある木
  1. $T=\{\langle\rangle,\langle0\rangle,\langle0,0\rangle,\dots\}$($0$ だけの列の全体)は無限の 2 分木で、道は $x=(0,0,0,\dots)$ だけである。
  2. $T=2^{<\omega}$ の道の全体は $2^\omega$ 全体である。
  3. 「$1$ が 2 つ続かない列」の全体 $T$ は 2 分木で、長さ $n$ の元の個数は Fibonacci 数 $F_{n+2}$($F_1=F_2=1$)である。いちばん左の道は $(0,0,0,\dots)$ である。

コンパクト性との関係

$\sigma\in2^{<\omega}$ について $[\sigma]:=\{x\in2^\omega\mid\sigma\preceq x\}$($\sigma$ を先頭部分にもつ無限列の全体)とおく。これらは Cantor空間 $2^\omega$ の開基をなす。

道のない木と被覆

2 分木 $T$ について、$\mathcal{U}_T:=\{[\sigma]\mid\sigma\in2^{<\omega}\setminus T\}$ とおく。

  1. $[T]=\emptyset$ であることと、$\mathcal{U}_T$ が $2^\omega$ を覆うことは同値である。
  2. $\mathcal{U}_T$ の有限個で $2^\omega$ が覆えることと、$T$ が有限であることは同値である。
    したがって、「$2^\omega$ の開基 $[\sigma]$ による被覆には有限部分被覆がある」ことと、thm-wkl-main の主張「無限の 2 分木には道がある」は、互いにもう一方から直ちに従う。

1:$x\notin[T]$ は、ある $n$ で $x\restriction n\notin T$、すなわち $x\in[x\restriction n]\in\mathcal{U}_T$ であることと同じである。
2:$T$ が有限なら、ある $L$ で長さ $L$ の列はどれも $T$ に属さないので、長さ $L$ の $2^L$ 個の $[\sigma]$ が $2^\omega$ を覆う。逆に $\sigma_1,\dots,\sigma_m\notin T$ で $[\sigma_1]\cup\cdots\cup[\sigma_m]=2^\omega$ とし、$L:=\max|\sigma_i|$ とおく。長さ $L$ の列 $\tau$ に $0$ を無限に続けた列はある $[\sigma_i]$ に属すので $\sigma_i\preceq\tau$ であり、木の条件から $\tau\notin T$ である。よって $T$ の元の長さは $L$ 未満で、$T$ は有限である。
最後の主張:被覆のコンパクト性を仮定し、$T$ を無限の 2 分木とする。$[T]=\emptyset$ なら 1 により $\mathcal{U}_T$ は被覆であり、有限部分被覆があるので 2 により $T$ は有限となって矛盾する。逆に弱 Kőnig の補題を仮定し、$\{[\sigma_k]\}_k$ を $2^\omega$ の被覆とする。$T:=\{\tau\mid\text{すべての }k< |\tau|\text{ で }\sigma_k\not\preceq\tau\}$ は 2 分木である。$x\in[T]$ があれば、$x\in[\sigma_k]$ となる $k$ について $n>\max(k,|\sigma_k|)$ で $\sigma_k\preceq x\restriction n\in T$ となって矛盾するので、$[T]=\emptyset$ であり、弱 Kőnig の補題から $T$ は有限である。$T$ に長さ $L$ の列がないとすると、長さ $L$ のどの $\tau$ もある $k< L$ で $\sigma_k\preceq\tau$ を満たし、$[\sigma_0],\dots,[\sigma_{L-1}]$ が $2^\omega$ を覆う。$\square$

$[0,1]$ の Heine–Borel の定理も、2 進の区間の木を使って弱 Kőnig の補題から出る。$\sigma\in2^{<\omega}$ に、$\sigma$ を 2 進小数の最初の桁とみた閉区間
$$ I_\sigma:=\Bigl[\,\sum_{i< |\sigma|}\sigma(i)2^{-i-1},\ \sum_{i< |\sigma|}\sigma(i)2^{-i-1}+2^{-|\sigma|}\,\Bigr] $$
を対応させる。$I_{\langle\rangle}=[0,1]$ で、$I_\sigma$ は $I_{\sigma^\frown0}$ と $I_{\sigma^\frown1}$ の和である。

Heine–Borel の定理の導出

開区間の列 $(a_k,b_k)$($k\in\mathbb{N}$)が $[0,1]$ を覆うならば、ある $L$ で $(a_0,b_0),\dots,(a_{L-1},b_{L-1})$ が $[0,1]$ を覆う。この結論は、被覆の列から定まる 1 つの 2 分木に弱 Kőnig の補題を当てはめて得られる。

覆われない 2 進区間の木

$T:=\{\tau\in2^{<\omega}\mid I_\tau\not\subset(a_0,b_0)\cup\cdots\cup(a_{|\tau|-1},b_{|\tau|-1})\}$ とおく($\tau=\langle\rangle$ では右辺は空集合)。$\sigma\preceq\tau$ なら $I_\tau\subset I_\sigma$ で、$\sigma$ の側の和集合のほうが小さいので、$\tau\in T$ なら $\sigma\in T$ であり、$T$ は 2 分木である。
$T$ が無限だとする。弱 Kőnig の補題により道 $x$ がある。区間 $I_{x\restriction n}$ は減少し、長さが $2^{-n}$ なので、ただ 1 点 $p$ に縮む。$p\in(a_k,b_k)$ となる $k$ をとると、$n$ が十分大きければ $I_{x\restriction n}\subset(a_k,b_k)$ であり、さらに $n>k$ なら $x\restriction n\notin T$ となって矛盾する。よって $T$ は有限である。
$T$ に長さ $L$ の列がないとすると、長さ $L$ のどの $\tau$ でも $I_\tau\subset(a_0,b_0)\cup\cdots\cup(a_{L-1},b_{L-1})$ であり、$I_\tau$ の全体は $[0,1]$ を覆う。$\square$

区間の包含 $I_\tau\subset\bigcup_{k< L}(a_k,b_k)$ は有限個の端点の比較で判定でき、端点が有理数なら $T$ は被覆の列から計算できる。証明が使う「無限集合の存在」は、この計算できる木の道だけである。これが、逆数学で Heine–Borel の定理が $\mathsf{WKL}_0$ で証明できる仕組みである(rem-wkl-reverse)。

計算可能な木と道

列 $\sigma\in2^{<\omega}$ を自然数で番号付けしておき、2 分木 $T$ が番号の集合として決定可能なとき、$T$ を 計算可能な木 という。$\varphi_e$ を番号 $e$ の部分計算可能関数とし(計算可能関数 の定義「標準の番号付け」)、$\varphi_{e,s}(x)=y$ で「$\varphi_e(x)$ の計算が $s$ ステップ未満で止まり値 $y$ を出す」ことを表す。この関係は $(e,x,y,s)$ について決定可能である(計算可能関数 の補題「停止した計算の読み取り」)。

計算可能に分離できない集合

$A:=\{e\mid\varphi_e(e)=0\}$、$B:=\{e\mid\varphi_e(e)=1\}$ とおく($\varphi_e(e)$ が定義されて、その値がそれぞれ $0$、$1$ である $e$ の集合)。$A,B$ は交わらない 帰納的可算集合 であり、$A\subset C$ かつ $C\cap B=\emptyset$ となる決定可能な集合 $C$ はない。

$A,B$ が交わらないのは $\varphi_e(e)$ の値が 1 つだからであり、$e\in A\iff\exists s\ \varphi_{e,s}(e)=0$ なので帰納的可算である($B$ も同じ)。決定可能な $C$ が $A\subset C$、$C\cap B=\emptyset$ を満たすとする。$x\in C$ なら $1$、$x\notin C$ なら $0$ を返す関数は全域的な計算可能関数なので、ある $e$ で $\varphi_e$ に等しい。$e\in C$ なら $\varphi_e(e)=1$ で $e\in B$ となり、$C\cap B=\emptyset$ に反する。$e\notin C$ なら $\varphi_e(e)=0$ で $e\in A\subset C$ となり矛盾する。$\square$

計算可能な道をもたない計算可能な木

計算可能な無限の 2 分木で、計算可能な道を 1 本ももたないものがある。

分離する集合の近似を木にする

lem-wkl-inseparable の $A,B$ について、$\sigma\in T$ を「すべての $e< |\sigma|$ で、$\varphi_{e,|\sigma|}(e)=0$ なら $\sigma(e)=1$、$\varphi_{e,|\sigma|}(e)=1$ なら $\sigma(e)=0$」で定める。条件は $e$ と $|\sigma|$ を上限とする有限個の決定可能な判定なので、$T$ は計算可能である。$\sigma\preceq\tau\in T$ なら、$e< |\sigma|$ で $\varphi_{e,|\sigma|}(e)=y$ のとき $\varphi_{e,|\tau|}(e)=y$ でもあるので $\sigma\in T$ であり、$T$ は 2 分木である。
$x\in2^\omega$ が $T$ の道であることと、$C_x:=\{e\mid x(e)=1\}$ が $A\subset C_x$、$C_x\cap B=\emptyset$ を満たすことは同値である。実際、$C_x$ がこれを満たせば、$x\restriction n$ はどの $n$ でも条件を満たす。逆に $x\in[T]$ で $e\in A$ なら、$\varphi_{e,s}(e)=0$ となる $s$ について $n>\max(e,s)$ とすると $x\restriction n\in T$ から $x(e)=1$ である。$e\in B$ についても同様である。
$A$ の特性関数は $C_x$ の条件を満たすので $[T]\ne\emptyset$ であり、$T$ は無限である。$T$ に計算可能な道 $x$ があれば $C_x$ は決定可能で、lem-wkl-inseparable に反する。$\square$

計算可能な集合だけを集合とみなす世界(逆数学の $\omega$ モデル $\mathrm{REC}$)では、この木が弱 Kőnig の補題の反例になる。同じ $A,B$ から、計算可能な実数をすべて覆うが $[0,1]$ を覆わない、計算可能な開区間の列も作れる(Sim06 Example I.8.6、pp. 30–31。木の形は Example I.8.8、p. 32)。

低い道の存在

道を計算できなくても、道の「計算の難しさ」は小さくできる。集合 $X\subset\mathbb{N}$ の値を問い合わせながら計算する機械($X$ を オラクル とする計算)の番号付けを $\varphi^X_e$ とし、$X$ の ジャンプ を $X':=\{e\mid\varphi^X_e(e)\text{ が定義される}\}$ とおく。$\emptyset'$ は自己停止集合 $K$(停止問題)にほかならない。集合 $Y$ が $X$ から計算できることを $Y\le_TX$ と書く。$X'\le_T\emptyset'$ となる $X$ を 低い(low)集合という。$X$ が計算可能なら $X'$ は $K$ と同じ難しさなので低いが、低い集合は計算可能とは限らない。

オラクルつきの計算について使う事実

次の 3 つは、オラクルつきの機械の定義からすぐに確かめられる標準的な事実である。$\sigma\in2^{<\omega}$ をオラクルの一部とし、$\varphi^\sigma_{e,s}(e)\!\downarrow$ で「$\sigma$ の範囲($|\sigma|$ 未満の数)だけを問い合わせ、$s$ ステップ未満で計算が止まる」ことを表す。

  1. 関係 $\varphi^\sigma_{e,s}(e)\!\downarrow$ は $(e,\sigma,s)$ について決定可能である。
  2. $\sigma\preceq\tau$、$s\le t$ で $\varphi^\sigma_{e,s}(e)\!\downarrow$ なら $\varphi^\tau_{e,t}(e)\!\downarrow$ である(同じ問い合わせに同じ答えが返る)。
  3. $\varphi^X_e(e)$ が定義されることと、ある $n$ で $\varphi^{X\restriction n}_{e,n}(e)\!\downarrow$ となることは同値である(止まる計算が問い合わせる数は有限個で、ステップ数も有限である)。
    また、決定可能な関係 $P(d,n)$ について「$\exists n\,P(d,n)$ かどうか」は $d$ について一様に $K$ から計算できる。これは、入力によらず $n$ を探し続ける機械の番号を $d$ から計算し、その番号が $K$ に属すかを問えばよいからである。
低基底定理

計算可能な無限の 2 分木 $T$ には、低い道 $X$($X'\le_T\emptyset'$ となる道)がある。

ジャンプの各点を木の縮小で決める

計算可能な無限の 2 分木の列 $T=T_0\supset T_1\supset T_2\supset\cdots$ を次のように作る。$T_e$ ができたとき
$$ U_e:=\{\sigma\in T_e\mid\varphi^\sigma_{e,|\sigma|}(e)\!\downarrow\text{ でない}\} $$
とおく。rem-wkl-oracle-facts の 1 により $U_e$ は計算可能で、2 により $\tau\in U_e$、$\sigma\preceq\tau$ なら $\sigma\in U_e$ なので 2 分木である。$U_e$ が無限なら $T_{e+1}:=U_e$、有限なら $T_{e+1}:=T_e$ とする。どちらでも $T_{e+1}$ は計算可能な無限の 2 分木である。
「$U_e$ が有限」は「ある $n$ で長さ $n$ の列が $U_e$ にない」と同じで、括弧の中は有限個の列の判定なので決定可能である。rem-wkl-oracle-facts の最後の事実により、この問いは $K$ から答えられる。$T_{e+1}$ の決定の手順は $T_e$ の手順と答え 1 つから書けるので、$e$ ごとの答え($U_e$ が有限かどうか)の列は $K$ から計算できる。
$S:=\bigcap_eT_e$ とおく。各長さ $n$ について、$T_e$ の長さ $n$ の元の集合は $e$ について減少する空でない有限集合なので、ある所から一定で空でない。よって $S$ は無限の 2 分木であり、thm-wkl-main により道 $X$ がある。$X$ はすべての $T_e$ の道であり、とくに $T$ の道である。
$e\in X'$ と「$U_e$ が有限」が同値であることを示す。$U_e$ が無限なら、$X$ は $T_{e+1}=U_e$ の道なので、すべての $n$ で $\varphi^{X\restriction n}_{e,n}(e)\!\downarrow$ でなく、rem-wkl-oracle-facts の 3 により $e\notin X'$ である。$U_e$ が有限なら、長さ $n$ の元をもたない $n$ がある。$X\restriction n\in T_e$ なので $X\restriction n\notin U_e$、すなわち $\varphi^{X\restriction n}_{e,n}(e)\!\downarrow$ であり、$e\in X'$ である。前段により $X'\le_T K=\emptyset'$ である。$\square$

thm-wkl-kleene-tree の木に当てはめると、計算可能でない低い集合が得られる。この定理は Jockusch と Soare によるもので、Sim06 は $\mathsf{WKL}_0$ のモデルの節でこれを扱い、計算可能な集合の全体 $\mathrm{REC}$ が $\mathsf{WKL}_0$ のすべての $\omega$ モデルの共通部分であることを導いている(p. 58 の概観)。

逆数学での位置

体系 WKL₀ と同値な定理

逆数学 の基礎の体系 $\mathsf{RCA}_0$ に、弱 Kőnig の補題(「$2^{<\mathbb{N}}$ の無限の部分木には無限の道がある」)を加えた体系を $\mathsf{WKL}_0$ という(Sim06 Definition I.10.1、p. 37)。

  1. $\mathsf{RCA}_0\subsetneq\mathsf{WKL}_0\subsetneq\mathsf{ACA}_0$ である(同 Remark I.10.2、p. 37)。$\mathsf{RCA}_0$ が弱 Kőnig の補題を証明しないのは、thm-wkl-kleene-tree の木が $\mathrm{REC}$ での反例になるからである。$\mathsf{ACA}_0$ が弱 Kőnig の補題を証明することは 逆数学 の命題「算術的内包から弱König補題を導く」で示されている。
  2. $\mathsf{RCA}_0$ の上で、$\mathsf{WKL}_0$ は次の主張のそれぞれと同値である(同 Theorem I.10.3、pp. 37–38 の 14 項目から抜粋):$[0,1]$ の Heine–Borel の定理、$[0,1]$ 上の連続関数は有界で最大値をもつこと、$[0,1]$ 上の連続関数は一様連続であること、Gödelの完全性定理(可算の無矛盾な文の集合はモデルをもつ)、可算の可換環は素イデアルをもつこと、Brouwerの不動点定理、可分な Banach 空間の Hahn–Banach の定理。
  3. $\mathsf{WKL}_0$ の一階の部分は $\mathsf{RCA}_0$ と同じであり、$\mathsf{WKL}_0$ は原始再帰的算術 PRA に対して $\Pi^0_2$ 文について保存的である(同 Remark I.10.5、p. 38)。弱 Kőnig の補題を使う多くの非構成的な証明が、有限の立場に還元できるという意味をもつ(Hilbertのプログラム)。

thm-wkl-heine-borel は 2 の最初の項目の、弱 Kőnig の補題から Heine–Borel の定理への向きを、prop-wkl-compact は Cantor 空間での両方向を、通常の数学の言葉で示したものである。

反例:仮定を外すと成り立たないこと

外す仮定反例成り立たなくなること
各頂点の子が有限個(thm-wkl-main)自然数の列の木 $\{\langle\rangle\}\cup\{\langle n\rangle\mid n\in\mathbb{N}\}$無限の木だが道がない
道に計算可能性を求めない(thm-wkl-main)thm-wkl-kleene-tree の木計算可能な無限の 2 分木に計算可能な道がない
子の値が $0,1$ の 2 つに限られる(thm-wkl-low-basis)自然数の列の計算可能な木 $T_K$(下の ex-wkl-table)各頂点の子は高々 2 個だが、ただ 1 本の道が $K$ を計算し、低くない
区間の列が $[0,1]$ を覆う(thm-wkl-heine-borel)$[0,1)$ を覆う開区間 $(-1,1-2^{-k})$ の列有限部分被覆がない($[0,1]$ を覆っておらず、木 $T$ は無限で、道は $(1,1,1,\dots)$)
表の確かめ

1 行目.$\langle n\rangle$ の形の列が無限個あるので木は無限だが、長さ 2 の列がないので無限の道はない。子が無限個ある頂点 $\langle\rangle$ だけが仮定を満たさない。
2 行目.prf-wkl-kleene-tree で示した。木は計算可能で無限だが、道はどれも $A,B$ を分離する集合の特性関数であり、計算可能でない。
3 行目.自然数の列 $\sigma$ が $T_K$ に属することを、「すべての $e< |\sigma|$ で、$\sigma(e)=0$ なら $\varphi_e(e)$ の計算が $|\sigma|$ ステップ未満で止まらず、$\sigma(e)=s+1$ なら計算がちょうど $s$ ステップ目に止まる」で定める。$T_K$ は計算可能な木で、各頂点の子は $0$ と(止まる時刻があればその $s+1$)の高々 2 個である。道 $f$ では、$f(e)=s+1$ なら $\varphi_e(e)$ は $s$ ステップで止まり、$f(e)=0$ なら $f\restriction n\in T_K$ がすべての $n$ で成り立つので計算は止まらない。よって道は「$\varphi_e(e)$ が止まらなければ $0$、止まれば止まる時刻 $+1$」というただ 1 つの関数で、$e\in K\iff f(e)\ne0$ から $K\le_Tf$ である。$f$ が低いなら $K'\le_Tf'\le_TK$ となるが、ジャンプは真に難しくなる($K'\le_TK$ は成り立たない。$K$ をオラクルとした 停止問題 の決定不能性による)ので矛盾する。子の値が $\{0,1\}$ に収まらず、その上限も計算できないことだけが仮定を満たさない。
4 行目.$1\in[0,1]$ はどの区間にも入らないので、列は $[0,1]$ を覆わない(Heine–Borel の定理の仮定が外れる)。prf-wkl-heine-borel の木 $T$ では、右端の区間 $I_{\langle1,\dots,1\rangle}=[1-2^{-n},1]$ が $1$ を含んで覆われないので、長さ $n$ の列 $\langle1,\dots,1\rangle$ がすべて $T$ に属して $T$ は無限である。道 $(1,1,1,\dots)$ の縮む点は $1$ で、覆われていない点である。$\square$

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する