逆数学

同義語:reverse mathematics

概要

逆数学(reverse mathematics)とは、弱い基礎理論の上で数学的定理と集合存在公理の両方向の含意を証明し、その定理に必要な公理の強さを測る研究方法である。二階算術の部分体系を用い、多くの定理は $\mathsf{RCA}_0$ 上で $\mathsf{RCA}_0$、$\mathsf{WKL}_0$、$\mathsf{ACA}_0$、$\mathsf{ATR}_0$、$\Pi^1_1\text{-}\mathsf{CA}_0$ のビッグ・ファイブのいずれかと同値になる。対象となるのは通常の解析定理そのものではなく二階算術の中でコード化された版であり、古典論理を用いる点で構成的数学とは異なる。

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

前提知識: 計算可能関数, 数理論理学

逆数学の考え方

定理から公理を測る方法

逆数学(reverse mathematics)とは、弱い基礎理論 $B$ を固定し、数学的定理 $T$ と公理体系 $S$ について $B+S\vdash T$ かつ $B+T\vdash S$ の両方を証明することで、$T$ に必要な集合存在公理の強さを測る研究方法である。このとき「$T$ は $B$ 上で $S$ と同値である」という。通常は公理から定理を導く($B+S\vdash T$)のに対し、逆向き $B+T\vdash S$ も証明することが名称の由来である。

ここで「$S$ が $T$ を証明する」という含意と、「$B$ 上で $T$ と $S$ が同値である」という結論は異なる。後者には逆向きの証明が必要であり、一方の含意だけでは公理の必要性は分からない。

二階算術

二階算術

二階算術(second-order arithmetic)は、数変数 $m,n,\ldots$ と、自然数の集合を表す集合変数 $X,Y,\ldots$ を持つ二種類の変数の一階理論(一階述語論理)である。標準的な言語 $L_2$ は $0,1,+,\cdot,<,\in$ を持ち、$n\in X$ だけが数と集合の間の所属を表す。
完全な二階算術 $\mathsf Z_2$ は、自然数算術の基本公理、数学的帰納法の公理、および $L_2$ の式で定義される自然数集合の存在を主張する内包公理図式(二階論理)を持つ。ここでいう「二階」は集合変数があることを指し、集合変数を標準的な冪集合全体にわたらせる完全二階意味論を採用する、という意味ではない。逆数学では、この形式理論の部分体系を比較する。Sim06

数量化子だけを持ち、集合量化子を持たない $L_2$ の式を算術的という。$\Delta^0_1$ 内包は、$\varphi$ を $\Sigma^0_1$ 式、$\psi$ を $\Pi^0_1$ 式(いずれも $X$ を自由に含まない)として、図式
$$ \forall n\,(\varphi(n)\leftrightarrow\psi(n))\to\exists X\,\forall n\,(n\in X\leftrightarrow\varphi(n)) $$
の各事例を公理とする公理図式である。すなわち、$\Sigma^0_1$ 式と $\Pi^0_1$ 式が同じ述語を定めるとき、その述語の外延を集合として取る。算術的内包は、任意の算術的な式 $\varphi$ について $\exists X\,\forall n\,(n\in X\leftrightarrow\varphi(n))$ を公理とし、算術的な式の外延を集合として取る。

数学的対象のコード化

二階算術の集合対象は自然数の部分集合なので、実数、連続関数、可算距離空間、開集合族などを扱うときは自然数によるコードを用いる。例えば実数は、所定の収束率を持つ有理数の Cauchy列のコードとして表せる。したがって逆数学で解析定理を述べるには、対象のコード、等号、連続性、被覆などの表現を固定しなければならない。同じ日本語名を持つ通常数学の定理と、特定のコード化を施した $L_2$ の文は同一の文ではない。

二階算術のモデル

$L_2$ のモデルは、数の領域と集合の領域を別に持つ。数の領域が標準自然数 $\mathbb N$ であるものを $\omega$-モデルという。$\mathsf{RCA}_0$ の最小 $\omega$-モデルの集合領域は計算可能集合(計算可能関数)全体であり、$\mathsf{ACA}_0$ の最小 $\omega$-モデルの集合領域は算術的集合(算術的階層)全体である。これらの記述は、形式体系そのものと、そのモデルの集合領域とを区別した記述である。Sim06

ビッグ・ファイブ

五つの基本体系

逆数学で繰り返し現れる次の五体系をビッグ・ファイブ(Big Five)という。

  • $\mathsf{RCA}_0$(再帰的内包公理系)は、基本算術公理、$\Sigma^0_1$ 帰納法、$\Delta^0_1$ 内包を持つ。多くの議論で基礎理論 $B$ として用いられる。
  • $\mathsf{WKL}_0$ は $\mathsf{RCA}_0$ に弱 König 補題、すなわち「コード化された無限二分木 $T\subseteq 2^{<\mathbb N}$ は無限枝を持つ」を加えた体系である。
  • $\mathsf{ACA}_0$(算術的内包公理系)は、算術的な式についての内包を許す体系である。
  • $\mathsf{ATR}_0$(算術的超限再帰)は、コード化された可算整列順序に沿う算術的な超限再帰を許す体系である。
  • $\Pi^1_1\text{-}\mathsf{CA}_0$ は、$\Pi^1_1$ 式についての内包を許す体系である。
    これらの説明は主公理を示したものである。帰納法や内包・分離図式を使う別の標準的表示は、共通の弱い基礎の上で同値になることを確認してから交換する必要がある。Sim06

共通言語で証明できる文の集合を $\operatorname{Th}(S)$ と書けば、標準的な定式化のもとで
$$ \operatorname{Th}(\mathsf{RCA}_0) \subsetneq \operatorname{Th}(\mathsf{WKL}_0) \subsetneq \operatorname{Th}(\mathsf{ACA}_0) \subsetneq \operatorname{Th}(\mathsf{ATR}_0) \subsetneq \operatorname{Th}(\Pi^1_1\text{-}\mathsf{CA}_0) $$
となる。これは単なる公理列の文字列としての集合包含ではなく、各体系が証明する文の強さの比較である。真の包含の証明には分離するモデルや保存定理を用いる部分があり、本記事では外部結果として採用する。Sim06

基本的な包含

再帰的内包から算術的内包への包含

$\mathsf{RCA}_0$ の各公理は $\mathsf{ACA}_0$ で証明できる。したがって
$$ \operatorname{Th}(\mathsf{RCA}_0)\subseteq \operatorname{Th}(\mathsf{ACA}_0) $$
である。

$\mathsf{ACA}_0$ の算術的内包は、とくに $\Delta^0_1$ 式についての内包を含む。また算術的帰納法は $\Sigma^0_1$ 式についての帰納法を含む。基本算術公理は共通である。ゆえに $\mathsf{RCA}_0$ の各公理図式の各事例が $\mathsf{ACA}_0$ で証明できる。証明の翻訳により、$\mathsf{RCA}_0$ の定理はすべて $\mathsf{ACA}_0$ の定理でもある。$\square$

算術的内包から弱König補題を導く

$\mathsf{ACA}_0$ は、任意のコード化された無限二分木 $T\subseteq 2^{<\mathbb N}$ が無限枝を持つことを証明する。したがって
$$ \operatorname{Th}(\mathsf{WKL}_0)\subseteq \operatorname{Th}(\mathsf{ACA}_0) $$
である。

$T\subseteq2^{<\mathbb N}$ を無限二分木とする。節点 $\sigma\in T$ について
$$ P(\sigma)\;:\Longleftrightarrow\;(\forall m)(\exists\tau\in T)\bigl(|\tau|\ge m\ \land\ \sigma\preceq\tau\bigr) $$
とおく。これは数についてだけ量化する算術的条件なので、算術的内包により $P(\sigma)$ を満たす節点全体 $T^*$ を集合として取れる。$T$ が無限で木であることから空列は $T^*$ に属する。
$\sigma\in T^*$ なら、$\sigma{}^\frown0$ と $\sigma{}^\frown1$ の少なくとも一方が $T^*$ に属する。実際、両方が無限に延長できないなら、それぞれの延長の長さに上限があり、その二つの上限の大きい方が $\sigma$ の延長の長さの上限となって $P(\sigma)$ に反する。
そこで $f(0)$ を空列とし、$f(n)\in T^*$ から、$f(n){}^\frown0\in T^*$ ならそれを $f(n+1)$ とし、そうでなければ $f(n){}^\frown1$ を $f(n+1)$ とする。この原始再帰で定めた有限列の和は $T$ の無限枝である。以上の構成は算術的内包と数についての再帰の範囲で行えるので、$\mathsf{ACA}_0$ は弱 König 補題を証明する(Sim06 Example I.8.8, p. 31 は有限分岐の木について同じ議論をしている)。$\square$

この証明は $\mathsf{WKL}_0$ と $\mathsf{ACA}_0$ の同値を示してはいない。逆向きは成り立たず、両者の間の包含は真である。

ω-モデルによる非証明性

ある文が体系 $S$ で証明できないことを示すには、$S$ のモデルでその文が偽になるものを一つ見つければよい(健全性:$S\vdash\varphi$ なら $S$ のすべてのモデルで $\varphi$ が成り立つ)。逆数学でよく使うのは、数の領域が標準自然数 $\omega$ で、集合の領域が $\omega$ の部分集合の族 $\mathcal S\subseteq\mathcal P(\omega)$ である $\omega$-モデルである。以下 $\omega$-モデルを集合の族 $\mathcal S$ で表す。
計算可能集合全体 $\mathrm{REC}$ は $\mathsf{RCA}_0$ の $\omega$-モデルであり、しかも最小の $\omega$-モデルである(Sim06 Remark I.7.5, p. 25。この記事では証明しない)。直観的には、$\Delta^0_1$ 内包は「計算で判定できる集合」だけを作る公理であり、$\Sigma^0_1$ 帰納法は標準自然数では自動的に成り立つ。

再帰的内包は算術的内包を証明しない

$\mathsf{RCA}_0$ は算術的内包を証明しない。すなわち $\mathsf{ACA}_0$ の公理のうち $\mathsf{RCA}_0$ で証明できないものがある。

停止問題の集合 $K=\{e\in\omega\mid e\text{ 番目の計算手続きが入力 }e\text{ で停止する}\}$ は、計算可能性理論の基本的な事実として、$L_2$ の $\Sigma^0_1$ 式 $\varphi(e)$(集合変数を含まない)で $\omega$ 上定義でき、しかも計算可能でない(Sim06 p. 24 の注意と Example I.8.4, p. 29 に使われる事実。この記事では証明しない)。算術的内包の事例 $\exists X\,\forall e\,(e\in X\leftrightarrow\varphi(e))$ が $\omega$-モデル $\mathrm{REC}$ で成り立つとすると、$X$ は $\mathrm{REC}$ の元で、数の領域が標準なので $X=K$ となり、$K$ が計算可能になって矛盾する。よってこの事例は $\mathrm{REC}$ で偽である。$\mathrm{REC}$ は $\mathsf{RCA}_0$ のモデルなので、健全性によりこの事例は $\mathsf{RCA}_0$ で証明できない。$\square$

上限原理と算術的内包の同値

逆数学の典型的な結果を一つ、両方向とも証明する。$\mathsf{RCA}_0$ では、実数を有理数列 $x=\langle q_m\rangle$ で $m< n$ なら $|q_m-q_n|< 2^{-m}$ を満たすものとしてコード化する(Sim06 Definition I.8.1, p. 28)。このコード化では、実数の間の $x< y$ は $\Sigma^0_1$ 式、$x\le y$ は $\Pi^0_1$ 式で書ける。

  • 上限原理:有界な単調増加有理数列 $\langle a_i\rangle$ に対し、実数 $c$ で、すべての $i$ について $a_i\le c$ であり、任意の $n$ に対しある $i$ で $c-a_i< 2^{-n}$ となるものが存在する($c$ は列の上限であり極限でもある)。
Σ⁰₁ 内包で足りる

$\mathsf{RCA}_0$ 上で、$\Sigma^0_1$ 内包($\Sigma^0_1$ 式 $\varphi(n)$ について $\exists X\,\forall n\,(n\in X\leftrightarrow\varphi(n))$、集合の母数を許す)から算術的内包が従う。

対 $(m,n)$ を数 $(m+n)^2+m$ で表す($\mathsf{RCA}_0$ で単射であることが示せる)。算術的な式 $\varphi(\vec n)$(数の自由変数 $\vec n$、集合の母数を含む)の構成に関する(体系の外での)帰納法で、各 $\varphi$ について「$\varphi$ の外延の集合 $\{\vec n\mid\varphi(\vec n)\}$ が存在する」ことが、$\mathsf{RCA}_0$ と $\Sigma^0_1$ 内包から証明できることを示す。

  • 原子式($t=s$、$t< s$、$t\in X$):有界量化子式なので $\Sigma^0_1$ 式でもあり、$\Sigma^0_1$ 内包で外延が取れる。
  • $\neg\psi$:$\psi$ の外延 $Y$ があれば、$\neg(\vec n\in Y)$ は有界量化子式なので、補集合が $\Sigma^0_1$ 内包で取れる。
  • $\psi\wedge\chi$:外延 $Y,Z$ があれば、$\vec n\in Y\wedge\vec n\in Z$ の外延が同様に取れる。
  • $\exists m\,\psi(m,\vec n)$:$\psi$ の外延 $Y$($(m,\vec n)$ の集合)があれば、$\exists m\,((m,\vec n)\in Y)$ は $Y$ を母数とする $\Sigma^0_1$ 式なので、外延が $\Sigma^0_1$ 内包で取れる。
    $\vee$、$\to$、$\forall$ はこれらで書き換えられ、有界量化子 $\exists m< t$ は $\exists m\,(m< t\wedge\cdots)$ の特別な場合である。どの段でも、新しい外延 $W$ について $\forall\vec n\,(\vec n\in W\leftrightarrow\varphi(\vec n))$ が、前の段の外延の性質から論理だけで従う。よって任意の算術的な $\varphi$ について外延が存在し、これは算術的内包である。$\square$

逆向き(算術的内包から $\Sigma^0_1$ 内包)は $\Sigma^0_1$ 式が算術的であることから明らかなので、$\mathsf{RCA}_0$ 上で両者は同値である。

上限原理は算術的内包と同値

$\mathsf{RCA}_0$ 上で、上限原理は $\mathsf{ACA}_0$ と同値である。すなわち $\mathsf{ACA}_0\vdash$ 上限原理 であり、$\mathsf{RCA}_0+$ 上限原理 $\vdash$ 算術的内包 である。

$\mathsf{ACA}_0$ から上限原理。 $\langle a_i\rangle$ を単調増加で、すべての $i$ で $a_i\le b$($b$ は有理数)とする。$\mathsf{ACA}_0$ は算術的な式についての帰納法をもつ(Sim06 p. 7)。算術的内包により
$$S:=\{(k,i)\mid\forall j\,(a_j-a_i\le2^{-k-1})\}$$
をとる。各 $k$ についてある $i$ で $(k,i)\in S$ となる。実際そうでなければ、任意の $i$ に $a_j>a_i+2^{-k-1}$ となる $j$ があり、$t$ についての算術的帰納法で「ある $i$ で $a_i\ge a_0+t\cdot2^{-k-1}$」がすべての $t$ で成り立つ。$t> (b-a_0)2^{k+1}$ で $a_i> b$ となり矛盾する。算術的な式についての最小数原理(算術的帰納法から従う)により、$i(k)$ を $(k,i)\in S$ となる最小の $i$ とし、$q_k:=a_{i(k)}$ とおく(列 $\langle q_k\rangle$ は算術的内包で取れる)。$k< l$ なら $(l,i)\in S$ は $(k,i)\in S$ を含意するので $i(k)\le i(l)$、したがって $q_k\le q_l$ であり、$(k,i(k))\in S$ から $q_l-q_k\le2^{-k-1}< 2^{-k}$ である。よって $c:=\langle q_k\rangle$ は実数のコードである。任意の $j$ と $k$ で $a_j\le q_k+2^{-k-1}$ なので $a_j\le c$、また $j\ge i(k)$ なら $q_k\le a_j\le c$ かつ $c-q_k\le2^{-k-1}$ なので $c-a_j\le 2^{-k-1}< 2^{-k}$。これが上限原理の結論である。
上限原理から算術的内包(Sim06 Theorem I.9.1 の証明)。 $\mathsf{RCA}_0$ の中で上限原理を仮定する。lem-reverse-math-sigma01-ca により $\Sigma^0_1$ 内包を示せばよい。$\varphi(n)\equiv\exists m\,\theta(m,n)$($\theta$ は有界量化子式)とし、
$$c_k:=\sum\{2^{-n}\mid n< k\ \wedge\ (\exists m< k)\,\theta(m,n)\}$$
とおく。$c_k$ は有界量化子だけで決まる有理数なので、列 $\langle c_k\rangle$ は $\Delta^0_1$ 内包で存在し、単調増加で $2$ 以下である。上限原理により、すべての $k$ で $c_k\le c$、任意の $n$ にある $k$ で $c-c_k< 2^{-n}$ となる実数 $c$ がある。このとき
$$\varphi(n)\ \leftrightarrow\ \forall k\,\bigl(c-c_k< 2^{-n}\ \to\ (\exists m< k)\,\theta(m,n)\bigr)$$
が成り立つ。($\to$)$\theta(m_0,n)$ とし、$c-c_k< 2^{-n}$ だが $(\exists m< k)\theta(m,n)$ でない $k$ があったとする。$k'> \max(k,n,m_0)$ をとると、$2^{-n}$ の項は $c_{k'}$ に入るが $c_k$ には入らず、ほかの項は $c_k$ の項を含むので $c_{k'}\ge c_k+2^{-n}$、したがって $c-c_k\ge2^{-n}$ となり矛盾する。($\leftarrow$)上限原理の性質から $c-c_k< 2^{-n}$ となる $k$ があり、右辺によりある $m< k$ で $\theta(m,n)$、すなわち $\varphi(n)$ である。右辺の $c-c_k< 2^{-n}$ は $\Sigma^0_1$ なので、右辺全体は $\Pi^0_1$ 式である。よって $\Delta^0_1$ 内包により $\{n\mid\varphi(n)\}$ が存在する。$\square$

prop-reverse-math-rca-not-aca と合わせると、上限原理は $\mathsf{RCA}_0$ では証明できず、$\mathsf{ACA}_0$ がそれを証明する最も弱い体系(ビッグ・ファイブの中で)であることが分かる。これが「定理に必要な公理を測る」ことの具体的な意味である。Bolzano–Weierstrass の定理についても同じ同値が成り立つ(Sim06 Theorem I.9.1, p. 34、Theorem I.9.3, p. 35)。

解析・代数の定理を測る例

次の各例は通常数学の定理をそのまま文字列として二階算術へ移したものではない。数列、実数、開区間列、体、ベクトル空間を自然数集合でコード化した版についての同値である。

有界実数列の収束部分列

$\mathsf{RCA}_0$ 上で、「コード化された有界実数列は収束部分列を持つ」は $\mathsf{ACA}_0$ と同値である。これは通常の Bolzano-Weierstrassの定理 の逆数学での定式化である。Sim06

Heine-Borel被覆補題

$\mathsf{RCA}_0$ 上で、「閉区間 $[0,1]$ を覆うようにコード化された開区間の列には有限部分被覆がある」は $\mathsf{WKL}_0$ と同値である。任意の開被覆を集合として量化する通常の Heine–Borelの定理と、開区間列で表された被覆とを一括りにしてはいけない。Sim06

可算ベクトル空間の基底

$\mathsf{RCA}_0$ 上で、「任意の可算体上のコード化された可算ベクトル空間は基底を持つ」は $\mathsf{ACA}_0$ と同値である。ここで対象は集合論的に任意の濃度を持つベクトル空間ではない。Sim06

基礎理論だけで証明できる場合

コード化された連続実関数についての 中間値の定理 は $\mathsf{RCA}_0$ で証明できる。したがって「解析学の定理なら必ず $\mathsf{WKL}_0$ 以上を必要とする」という含意は成り立たない。この例は、分野名だけで強さを決めず、定理の定式化ごとに両方向を調べる必要を示す。Sim06

反例:強さの判定で成り立たないこと

逆数学の結論は「どの公理が必要か」という主張なので、一方向の証明や分野名からの推測では決まらない。次の表は、条件を外すと結論が成り立たなくなる典型である。

外す条件反例成り立たなくなること
算術的内包計算可能集合だけの $\omega$-モデル $\mathrm{REC}$上限原理・Bolzano–Weierstrass の定理
弱 König 補題$\mathrm{REC}$ と、計算可能な枝をもたない計算可能な無限二分木弱 König 補題・Heine–Borel 被覆補題
逆向きの証明 $B+T\vdash S$中間値の定理と $\mathsf{ACA}_0$「$\mathsf{ACA}_0$ で証明できる定理は $\mathsf{ACA}_0$ と同値」
定理ごとの両方向の検討中間値の定理「解析学の定理なら $\mathsf{WKL}_0$ 以上が必要」
反例の確かめ

1 行目:thm-reverse-math-lub-aca により $\mathsf{RCA}_0$ 上で上限原理は算術的内包を導くので、上限原理が $\mathrm{REC}$ で成り立てば算術的内包も成り立つが、prop-reverse-math-rca-not-aca の証明で見たとおり $\mathrm{REC}$ では算術的内包の事例が偽である。具体的には、停止問題の集合 $K$ を単射な計算可能関数 $f$ で数え上げ、$a_k:=\sum_{m\le k}2^{-f(m)}$ とおくと、$\langle a_k\rangle$ は $\mathrm{REC}$ に属する有界単調増加列だが、その上限 $\sum_{n\in K}2^{-n}$ は計算可能な実数でなく、$\mathrm{REC}$ の中に上限がない(Sim06 Example I.8.4, pp. 29–30)。
2 行目:互いに素な二つの計算可能枚挙可能集合で、どの計算可能集合でも分離できないものを使うと、計算可能な無限二分木で計算可能な無限枝をもたないものが作れる(Sim06 Example I.8.8, pp. 31–32。この記事では証明しない)。したがって弱 König 補題は $\mathrm{REC}$ で偽であり、$\mathsf{RCA}_0$ で証明できない。Heine–Borel 被覆補題は $\mathsf{RCA}_0$ 上で弱 König 補題と同値なので(Sim06 Theorem I.10.3, p. 37)、同じく証明できない。
3 行目:中間値の定理(コード化した連続関数についての形)は $\mathsf{RCA}_0$ で証明できる(Sim06 Theorem I.8.3, p. 29)。prop-reverse-math-rca-in-aca により $\mathsf{ACA}_0$ でも証明できる。しかし $\mathsf{RCA}_0+$ 中間値の定理 は $\mathsf{RCA}_0$ と同じ定理しか持たず、prop-reverse-math-rca-not-aca により算術的内包を証明しない。よって $\mathsf{ACA}_0\vdash T$ だけからは $T$ が $\mathsf{ACA}_0$ を必要とすることは分からず、逆向き $\mathsf{RCA}_0+T\vdash\mathsf{ACA}_0$ の証明が必要である。
4 行目:同じく中間値の定理は解析学の定理だが $\mathsf{RCA}_0$ で証明できる(rem-reverse-math-nonexample)。一方、同じ解析学の上限原理は $\mathsf{ACA}_0$ を必要とする。分野名ではなく、定理の定式化ごとに両方向を調べなければならない。

構成的数学との区別

古典的逆数学と構成的数学

標準的な逆数学は古典論理を用い、弱い古典的基礎理論の上で定理と集合存在公理の同値を調べる。構成的数学は、証明や存在の意味、採用する論理を構成的に制限する研究を含む。$\mathsf{RCA}_0$ が計算可能数学と近い内容を持つことだけから、逆数学を構成的数学の一種と同一視することはできない。構成的な基礎の上で同様の較正を行う構成的逆数学は、古典的逆数学と区別して扱う。

関連項目

参考文献

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