扇定理

同義語:fan theoremBrouwerの扇定理Brouwer's fan theorem

概要

扇定理(fan theorem)とは、2 分木などの有限分岐の木(扇)の障壁は一様である、すなわちどの無限列もある有限の長さで障壁にかかるなら、その長さを列によらず一様にとれるという主張で、Brouwer が直観主義数学の原理として立てた。古典論理では弱Königの補題の対偶だが、構成的数学では非自明で、決定可能な障壁の場合は Cantor 空間上の正の一様連続関数が正の下界をもつことと同値になる。計算可能な列だけの世界では Kleene の木が反例を与える。

$$\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空間

扇定理(fan theorem)とは、2 分木(より一般に有限分岐の木、扇)の 障壁 は 一様 である、すなわち「どの無限列もある有限の長さで障壁にかかる」ならば「その長さを列によらず一様にとれる」という主張である。Brouwer が直観主義数学の原理として立てた(SEP22 §3.1)。古典論理 では 弱Königの補題 の対偶にすぎないが、構成的数学 では、列ごとに見つかる長さから共通の上界を取り出す点が非自明になる。
この記事では、障壁が決定可能な場合の扇定理 $\mathrm{FAN}_D$ を扱う。主定理は、Bishop の流儀の構成的数学の上で $\mathrm{FAN}_D$ が「Cantor 空間上の正の一様連続関数は正の数で下から抑えられる」という解析の主張と同値になることである(thm-fan-pos)。区間 $[0,1]$ での同じ形の同値は Julian と Richman による(JR84 Corollary 2.6)。一方、すべての列が計算可能であるとする立場では、Kleeneの木 から $\mathrm{FAN}_D$ の反例が作られる(thm-fan-kleene)。
「扇」は直観主義数学では有限分岐の展開(spread)を指す語であり、グラフ理論の扇(ある頂点から出る道の束)とは別の語である。

記号と定義

$2^{<\omega}$ を $0,1$ の有限列の全体、$2^\omega$ を $0,1$ の無限列の全体(Cantor空間)とする。$\alpha\in2^\omega$ と $n$ について、$\alpha$ の最初の $n$ 項からなる列を $\alpha\restriction n$ と書く。有限列 $\sigma$ の長さを $|\sigma|$、$\sigma$ が $\tau$ の始切片であることを $\sigma\preceq\tau$ と書く。$\sigma$ の後に $0$ を並べた無限列を $\sigma0^\omega$ と書く。論理は 直観主義論理 とし、古典論理を使う箇所はそう断る。

障壁と扇定理

$B\subseteq2^{<\omega}$ とする。

  1. $B$ が 障壁(bar)であるとは、すべての $\alpha\in2^\omega$ に、$\alpha\restriction n\in B$ となる $n$ があることをいう。
  2. $B$ が 一様(uniform)であるとは、ある $N$ があって、すべての $\alpha\in2^\omega$ に $\alpha\restriction n\in B$ となる $n\le N$ があることをいう。
  3. $B$ が 決定可能(detachable)であるとは、各 $\sigma\in2^{<\omega}$ について $\sigma\in B$ か $\sigma\notin B$ かが決まることをいう。
  4. 決定可能な障壁についての扇定理 $\mathrm{FAN}_D$ とは、「決定可能な障壁はすべて一様である」という主張である。決定可能性の条件を外した「障壁はすべて一様である」を $\mathrm{FAN}$ と書く。

SEP22 §3.1 は $\mathrm{FAN}_D$ を FT${}_D$ と書いている。障壁を $\Pi^0_1$ の形のものや c-障壁に限る中間の形もあり、Bishop の構成的数学の上では $\mathrm{FAN}\Rightarrow\mathrm{FAN}_{\Pi^0_1}\Rightarrow\mathrm{FAN}_c\Rightarrow\mathrm{FAN}_D$ で、どの逆も成り立たない(Lubarsky と Diener。SEP22 §5.1)。
木の言葉に直すこともできる。障壁 $B$ に対し、$B$ の元を始切片にもたない列の全体
$$ T_B:=\{\sigma\in2^{<\omega}\mid\tau\preceq\sigma\text{ なら }\tau\notin B\} $$
は始切片で閉じた集合(2 分木)であり、$B$ が決定可能なら $T_B$ も決定可能である($\sigma$ の始切片は $|\sigma|+1$ 個しかない)。$B$ が障壁であることは「$T_B$ のどの無限列も途中で $T_B$ から出る」ことであり、$B$ が一様であることは「$T_B$ に長さ $N$ の列がない $N$ がある」ことである(JR84 p. 335 は前者を branch-bounded、後者を bounded とよぶ)。

障壁の例
  1. $B=\{\sigma\mid|\sigma|=5\}$ は決定可能で、$N=5$ で一様な障壁である。
  2. $B=\{\sigma\mid\sigma\text{ が }1\text{ を含む}\}\cup\{\sigma\mid|\sigma|=10\}$ も決定可能で一様($N=10$)である。
  3. $B=\{\sigma\mid\sigma\text{ が }1\text{ を含む}\}$ は障壁でない。$0^\omega$ はどの長さでも $B$ にかからない。古典論理では「$1$ を含まない列は $0^\omega$ だけ」だが、障壁であるかを判定するには $0^\omega$ を調べなければならない。

古典論理での証明

古典論理では扇定理が成り立つ

古典論理を仮定する。このとき決定可能性によらず、$2^{<\omega}$ の障壁はすべて一様である。逆に、この主張から 弱Königの補題 が従う。

道のない木は有限

$B$ を障壁とし、$T_B$ を上のとおりとする。$T_B$ の道 $\alpha$(すべての $n$ で $\alpha\restriction n\in T_B$)があれば、$\alpha\restriction n\in B$ となる $n$ がないので、$B$ が障壁であることに反する。よって $T_B$ は道をもたず、弱 Kőnig の補題(無限の 2 分木は道をもつ)により $T_B$ は有限である。$T_B$ の元の長さの最大値より大きい $N$ をとると、どの $\alpha$ についても $\alpha\restriction N\notin T_B$ なので、ある $\tau\preceq\alpha\restriction N$ が $B$ に属する。$\tau=\alpha\restriction n$($n\le N$)であり、$B$ は一様である。
逆に、$T$ を道のない 2 分木とし、$B:=2^{<\omega}\setminus T$ とおく。道がないので $B$ は障壁であり、一様なので $N$ がとれる。長さ $N$ の $\sigma$ について $\alpha:=\sigma0^\omega$ をとると、ある $n\le N$ で $\alpha\restriction n\notin T$ であり、$T$ は始切片で閉じているので $\sigma\notin T$ である。よって $T$ は有限である。$\square$

この同値は SEP22 §3.1 が述べる「$\mathrm{FAN}_D$ の古典的な対偶は Kőnig の補題」ということの中身である。証明の前半では、$T_B$ が有限であることを弱 Kőnig の補題から背理法で得ている。構成的数学では、この背理法の段が使えない。

計算可能な列だけの世界での反例

ロシア構成主義のように、すべての列が計算可能であるとする立場を考える。そこでは「すべての $\alpha$」は「すべての計算可能な $\alpha$」と読まれる。Kleeneの木 は、計算可能な無限の 2 分木で、計算可能な道を 1 本ももたないものであり、その存在は 弱Königの補題 の定理「計算可能な道をもたない計算可能な木」で証明されている。以下この節では古典論理で論じる。

Kleene の木による反例

$T$ を Kleene の木とし、$B:=2^{<\omega}\setminus T$ とおく。

  1. $B$ は決定可能である。
  2. 計算可能なすべての $\alpha$ に、$\alpha\restriction n\in B$ となる $n$ がある。
  3. どの $N$ についても、計算可能な $\alpha$ で、$n\le N$ のどの $\alpha\restriction n$ も $B$ に属さないものがある。
    したがって、計算可能な列に限って読んだ $\mathrm{FAN}_D$ は成り立たない。

1 は $T$ が計算可能なことによる。2:計算可能な $\alpha$ は $T$ の道でないので、$\alpha\restriction n\notin T$ となる $n$ がある。3:$T$ は無限で、始切片で閉じているので、長さ $N$ の元 $\sigma\in T$ がある。$\alpha:=\sigma0^\omega$ は計算可能で、$n\le N$ では $\alpha\restriction n\preceq\sigma$ なので $\alpha\restriction n\in T$、すなわち $\alpha\restriction n\notin B$ である。$\square$

Julian と Richman は、Church の提言の帰結「部分関数の全体は可算である」だけを仮定して、Bishop の構成的数学の中で同じ形の反例(長さの上界のない、決定可能な branch-bounded な扇)を作った(JR84 Theorem 1.3)。これにより、$\mathrm{FAN}_D$ は Bishop の構成的数学では証明できない(Church の提言が構成的に反証されない限り)。一方、直観主義数学では、Brouwer は決定可能性の条件なしに扇定理を立てており、$\mathrm{FAN}$ は標準の原理である(SEP22 §3.1、§5.1)。

主定理:正の一様連続関数の下界

ここからは直観主義論理に戻り、実数は 構成的数学 の定義「構成的な実数」に従う。実数は正則な有理数列 $x=(x_n)_{n\ge1}$(すべての $m,n$ で $|x_m-x_n|\le\frac1m+\frac1n$)であり、有理数 $q$ について $q\le x$ は「すべての $n$ で $q\le x_n+\frac2n$」、$0< x$ は「ある $n$ で $x_n>\frac2n$」を意味する。次の 3 つの事実を使う。

  • (a) すべての $n$ で $x_n-\frac1n\le x$。実際、どの $m$ でも $x_m\ge x_n-\frac1n-\frac1m\ge(x_n-\frac1n)-\frac2m$ である。
  • (b) $q\le x$ ならすべての $n$ で $x_n\ge q-\frac2n$(定義そのもの)。
  • (c) $0< x$ は「ある有理数 $c>0$ で $c\le x$」と同値である。$x_n>\frac2n$ なら (a) より $c:=x_n-\frac1n>\frac1n$ が使え、逆に $c\le x$ なら $n>4/c$ で $x_n\ge c-\frac2n>\frac2n$ である。
    実数の加法と順序の基本性質($q\le x$ かつ $|x-y|\le\varepsilon$ なら $q-\varepsilon\le y$ など)は断らずに使う。
一様連続関数と正値の原理
  1. 関数 $f\colon2^\omega\to\mathbb R$ と写像 $\omega\colon\mathbb N\to\mathbb N$ が、すべての $k$ と $\alpha,\beta\in2^\omega$ について
    $$ \alpha\restriction\omega(k)=\beta\restriction\omega(k)\ \Longrightarrow\ |f(\alpha)-f(\beta)|\le2^{-k} $$
    を満たすとき、$f$ は 連続の度合い $\omega$ をもつ 一様連続 関数であるという。
  2. 正値の原理 $\mathrm{POS}$ とは、「連続の度合いをもつ一様連続関数 $f\colon2^\omega\to\mathbb R$ が、すべての $\alpha$ で $0< f(\alpha)$ を満たすなら、ある $k$ ですべての $\alpha$ について $2^{-k}\le f(\alpha)$ となる」という主張である。

古典論理では、$2^\omega$ はコンパクトで連続関数は最小値をとるので、$\mathrm{POS}$ は当然成り立つ。構成的には、最小値をとる点を見つけられないので、「各点で正」から「一様に正」へ移る段が問題になる。これは扇定理と同じ形の問題である。

扇定理と正値の原理

直観主義論理のもとで、$\mathrm{FAN}_D$ と $\mathrm{POS}$ は同値である。

障壁の深さと関数の値を入れ替える

$\mathrm{FAN}_D\Rightarrow\mathrm{POS}$. $f$ を連続の度合い $\omega$ をもつ一様連続関数とし、すべての $\alpha$ で $0< f(\alpha)$ とする。有限列 $\sigma$ について $x^\sigma:=f(\sigma0^\omega)$ とおき(実数、すなわち有理数列)、
$$ B:=\Bigl\{\sigma\in2^{<\omega}\Bigm|\ \text{ある }k\le|\sigma|\text{ で }\omega(k)\le|\sigma|\text{ かつ }x^\sigma_{2^k}>3\cdot2^{-k}\Bigr\} $$
とおく。条件は有限個の $k$ についての、自然数の比較と有理数の比較だけなので、$B$ は決定可能である。
$B$ は障壁である. $\alpha$ をとる。$0< f(\alpha)$ と (c) により、有理数 $c>0$ で $c\le f(\alpha)$ となるものがある。$7\cdot2^{-k}\le c$ となる $k$ をとり、$M:=\max(k,\omega(k))$、$\sigma:=\alpha\restriction M$ とおく。$\sigma0^\omega$ と $\alpha$ は最初の $M\ge\omega(k)$ 項が一致するので $|x^\sigma-f(\alpha)|\le2^{-k}$ であり、$c-2^{-k}\le x^\sigma$ となる。(b) を $n=2^k$ で使うと
$$ x^\sigma_{2^k}\ge c-2^{-k}-2\cdot2^{-k}\ge7\cdot2^{-k}-3\cdot2^{-k}=4\cdot2^{-k}>3\cdot2^{-k} $$
である。$k\le M=|\sigma|$、$\omega(k)\le|\sigma|$ なので $\alpha\restriction M\in B$ である。
一様な下界. $\mathrm{FAN}_D$ により、すべての $\alpha$ に $\alpha\restriction n\in B$ となる $n\le N$ がある $N$ がとれる。$\alpha$ をとり、そのような $n$ と、$B$ の定義の $k\le n$ をとる。$\sigma:=\alpha\restriction n$ について、(a) より $3\cdot2^{-k}< x^\sigma_{2^k}$ から $2\cdot2^{-k}\le x^\sigma$ が従う。$\omega(k)\le n$ なので $\sigma0^\omega$ と $\alpha$ の最初の $\omega(k)$ 項は一致し、$|f(\alpha)-x^\sigma|\le2^{-k}$ である。よって $2^{-k}\le f(\alpha)$ であり、$k\le n\le N$ から $2^{-N}\le f(\alpha)$ を得る。$N$ は $\alpha$ によらない。
$\mathrm{POS}\Rightarrow\mathrm{FAN}_D$. $B$ を決定可能な障壁とする。各 $\alpha$ には $\alpha\restriction n\in B$ となる $n$ があり、$B$ が決定可能なので、$n=0,1,2,\dots$ と順に調べれば最小のもの $n(\alpha)$ が求まる。$f(\alpha):=2^{-n(\alpha)}$ とおくと $0< f(\alpha)$ である。
$f$ は連続の度合い $\omega(k)=k$ をもつ. $\alpha\restriction k=\beta\restriction k$ とする。$n(\alpha)\le k$ か $n(\alpha)>k$ かは決定できる。$n(\alpha)\le k$ なら、$j\le n(\alpha)$ で $\beta\restriction j=\alpha\restriction j$ なので $n(\beta)=n(\alpha)$ であり、$f(\alpha)=f(\beta)$ である。$n(\alpha)>k$ なら、同じ理由で $n(\beta)\le k$ はありえず(そうなら $n(\alpha)=n(\beta)\le k$)、$n(\beta)>k$ である。このとき $0< f(\alpha),f(\beta)\le2^{-k-1}$ なので $|f(\alpha)-f(\beta)|\le2^{-k}$ である。
$\mathrm{POS}$ により、すべての $\alpha$ で $2^{-k}\le2^{-n(\alpha)}$ となる $k$ がある。すなわち $n(\alpha)\le k$ であり、$\alpha\restriction n(\alpha)\in B$ なので、$B$ は $N=k$ で一様である。$\square$

後半の証明の $f$ は、障壁 $B$ にかかるまでの深さを値に写したものである。前半はその逆で、関数が一様に正になる深さを障壁として読む。Julian と Richman は $[0,1]$ 上で、扇の点を平面に配置してそこからの距離で関数を作り、同じ同値を示した(JR84 Theorem 2.4、Corollary 2.6、pp. 337–338)。

計算可能な列だけの世界で正値の原理が成り立たないこと

古典論理で論じる。$T$ を Kleeneの木 とし、計算可能な $\alpha$ について $n(\alpha)$ を $\alpha\restriction n\notin T$ となる最小の $n$、$f(\alpha):=2^{-n(\alpha)}$ とおく。$f$ は計算可能な列の上で定義され、連続の度合い $\omega(k)=k$ をもち、すべての計算可能な $\alpha$ で正だが、計算可能な列の上での値の下限は $0$ である。

thm-fan-kleene の $B=2^{<\omega}\setminus T$ に、thm-fan-pos の後半の構成を当てはめる。定義と連続の度合いは同じ議論による。thm-fan-kleene の 3 により、どの $N$ にも $n(\alpha)>N$ となる計算可能な $\alpha$ があり、$f(\alpha)\le2^{-N-1}$ である。$\square$

$[0,1]$ 上でも同じことが起きる。Church の提言の帰結のもとで、$[0,1]$ 上の一様連続関数で、どの点でも正だが下限が $0$ のものがある(JR84 Corollary 2.5)。

有限分岐の扇と一様連続性

有限分岐の木への一般化

$S\subseteq\mathbb N^{<\omega}$ を決定可能な木で、各 $\sigma\in S$ の子の集合 $\{i\mid\sigma^\frown i\in S\}$ が空でない有限集合で、その一覧が $\sigma$ から計算できるものとする(これを 扇 とよぶ)。$\mathrm{FAN}_D$ を仮定すると、$S$ の無限の枝の全体についての決定可能な障壁も一様である。

子を 2 進で符号化する

要点:$S$ の各頂点の子に $0,1$ の列で番号を付け、$S$ の枝を $2^\omega$ の元で表す。

詳しい証明を開く

$\sigma\in S$ の子を小さい順に番号 $0,\dots,c_\sigma-1$ で呼び($c_\sigma\ge1$)、番号 $j< c_\sigma-1$ を「$j$ 個の $1$ のあとに $0$」、番号 $c_\sigma-1$ を「$c_\sigma-1$ 個の $1$」($c_\sigma=1$ のときは $0$ か $1$ の任意の 1 項)で表す。どの $0,1$ 列も、先頭から高々 $c_\sigma$ 項を読めばちょうど 1 つの符号で始まることがわかる。$\alpha\in2^\omega$ を先頭から読み、各段で符号を 1 つ読み取って子を選ぶと、$S$ の枝 $\Phi(\alpha)$ が得られる。各段は少なくとも 1 項を読むので、$\alpha$ の長さ $m$ の始切片 $\tau$ からは、長さ $m$ 以下の枝の始切片 $\Phi^*(\tau)$(読み終えた段の分)が計算できる。$S$ の枝の決定可能な障壁 $B$ に対し、$B':=\{\tau\mid\Phi^*(\tau)\text{ のある始切片が }B\text{ に属する}\}$ は決定可能である。$\alpha$ ごとに $\Phi(\alpha)\restriction n\in B$ となる $n$ があり、十分長い $\tau\preceq\alpha$ では $\Phi^*(\tau)$ が $\Phi(\alpha)\restriction n$ を含むので、$B'$ は障壁である。$\mathrm{FAN}_D$ により $B'$ は $N$ で一様である。$S$ のどの枝 $\beta$ も、各段の子の番号を符号に直せば $\beta=\Phi(\alpha)$ となる $\alpha$ が得られるので、$\beta$ は長さ $N$ 以下で $B$ にかかる。$\square$

直観主義数学では、$\mathrm{FAN}$ を Brouwer の連続性の原理($\mathbb N^\omega$ から $\mathbb N$ への関数はすべて連続である)と組み合わせ、コンパクトな距離空間上の関数はすべて一様連続であることを導く(SEP22 §3.1)。JR84 p. 338 も、扇定理を全面的に使えば $[0,1]$ 上の関数は自動的に一様連続になり、正値の原理で連続性を仮定する必要がないことに触れている。これは古典数学と矛盾するように見えるが、直観主義数学の「関数」がすべて連続であることによる。逆に、計算可能な列だけの世界では、$[0,1]$ 上の各点で連続だが一様連続でない関数がある(SEP22 §3.2)。

例と反例

主張反例満たされない条件
決定可能な障壁は一様である$\mathbb N^{<\omega}$ の障壁 $B=\{\sigma\mid\lvert\sigma\rvert\ge1,\ \lvert\sigma\rvert>\sigma(0)\}$有限分岐(木が $2^{<\omega}$ か扇であること)
決定可能な障壁は一様である(計算可能な列だけで読む)thm-fan-kleene の $2^{<\omega}\setminus T$計算可能でない列も障壁にかかる対象に含めること
各点で正の関数は正の下界をもつ$f(0^\omega)=1$、$\alpha\ne0^\omega$ では最初の $1$ の位置 $n$ に対し $f(\alpha)=2^{-n}$$f$ の連続性(古典論理でも下界がない)
各点で正の一様連続関数は正の下界をもつ(計算可能な列だけで読む)cor-fan-kleene-function の $f$$\mathrm{FAN}_D$(thm-fan-pos で同値)
1 行目と 3 行目の確かめを開く

1 行目:$\alpha\in\mathbb N^\omega$ は長さ $\alpha(0)+1$ で $B$ にかかるので障壁であり、$B$ は決定可能である。しかし $\alpha(0)=N$ の列は長さ $N$ 以下では $B$ にかからない。仮定が満たされないのは、根の子が無限個あることだけによる。

3 行目:古典論理で考える。$0^\omega$ でない $\alpha$ では最初の $1$ の位置 $n$ があり $f(\alpha)=2^{-n}>0$ である。$\alpha=0^n10^\omega$ で $f(\alpha)=2^{-n}$ なので下界は $0$ であり、$0^\omega$ の近くで値が $1$ から跳ぶので連続でない。

関連項目

参考文献

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