証明可能性論理

同義語:provability logic証明可能性の論理logic of provabilityGödel–Löb論理

概要

証明可能性論理(provability logic)とは、算術の理論の「証明できる」を様相 $\Box$ と読み、証明可能性について命題論理の形で言えることを調べる分野で、中心の体系は様相論理の $\mathbf{K}$ に Löb の公理 $\Box(\Box A\to A)\to\Box A$ を加えた $\mathbf{GL}$ である。$\mathbf{GL}$ は推移的かつ逆整礎なフレームの論理で、推移的で非反射的な有限フレームについて完全なので決定可能である。Solovay の算術的完全性定理により、$\mathsf{PA}$ が命題の形で証明できる証明可能性の法則は $\mathbf{GL}$ の定理に尽きる。箱の中の変数の不動点は $\mathbf{GL}$ の中で明示的に書け、たとえば Gödel 文は無矛盾性の文と同値である。

$$\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}} $$

前提知識: 様相論理, Löbの定理, Gödelの不完全性定理

証明可能性論理(provability logic)は、算術の理論の「証明できる」を様相 $\Box$ と読み、証明可能性について命題論理の形で言えることを調べる分野である。中心の体系は、様相論理の体系 $\mathbf K$ に Löb の公理 $\Box(\Box A\to A)\to\Box A$ を加えた $\mathbf{GL}$ である。
Löbの定理 は、$\mathbf{GL}$ の定理が算術で証明できることを保証する。逆に Solovay の算術的完全性定理は、$\mathsf{PA}$ が証明可能性について命題の形で証明できることは $\mathbf{GL}$ の定理に尽きることを主張する。$\mathbf{GL}$ は決定可能なので、自己言及の議論の命題論理の部分は機械的に判定できる。
この記事では、算術的健全性、Löb の図式が妥当なフレームの特徴づけ、有限フレームについての完全性と決定可能性、文字を含まない論理式の標準形、不動点の一意性を証明する。不動点の存在は主張と例を述べ、Solovay の定理は主張と証明の筋を述べる。これらの一般の証明はこの記事では与えない。

体系 GL

論理式、フレーム、モデル、$\Vdash$、妥当性、正規様相論理、$\mathbf K\Lambda$、$\Sigma\vdash A$、$\operatorname{Sub}(A)$ は 様相論理 の定義のとおりとする。$A,B,C$ は様相論理式を表す。

体系 GL

Löb の図式 を
$$ \mathrm L:\ \Box(\Box A\to A)\to\Box A $$
とし、これを含む最小の正規様相論理 $\mathbf K\mathrm L$ を $\mathbf{GL}$ と書く。すなわち $\mathbf{GL}$ は、恒真式の代入例、K 公理、$\mathrm L$ の形の論理式を公理とし、モーダスポネンスと必然化を規則とする体系である。

同じ体系は Gödel–Löb 論理ともよばれ、文献により $\mathbf L$、$\mathbf G$、$\mathbf{KW}$、$\mathbf{K4W}$、$\mathbf{PrL}$ とも書かれる(Ver24 §2.1)。$\mathbf K\Lambda$ は図式で定義されるので、$\mathbf{GL}$ の定理の命題変数に任意の論理式を一斉に代入しても定理である。$\boxdot A:=A\land\Box A$ と略記する。
次の 2 つは Löb の図式の基本的な帰結である。どちらも 様相論理 の補題「単調性と連言」($\Sigma\vdash\psi_1\land\dots\land\psi_n\to\varphi$ なら $\Sigma\vdash\Box\psi_1\land\dots\land\Box\psi_n\to\Box\varphi$)を使う。

図式 4 の導出

$\mathbf{GL}\vdash\Box B\to\Box\Box B$ である。

証明を開く

$D:=B\land\Box B$ とおく。単調性により $\mathbf{GL}\vdash\Box D\to\Box B$ なので、命題論理により $\mathbf{GL}\vdash B\to(\Box D\to D)$ である。単調性をもう一度使うと $\mathbf{GL}\vdash\Box B\to\Box(\Box D\to D)$ であり、Löb の図式を $D$ に使うと $\mathbf{GL}\vdash\Box B\to\Box D$ を得る。$D\to\Box B$ に単調性を使うと $\mathbf{GL}\vdash\Box D\to\Box\Box B$ である。2 つをつなげばよい。$\square$

箱の中の Löb の図式

$\mathbf{GL}\vdash\Box(\Box B\to B)\leftrightarrow\Box B$ である。

左から右は Löb の図式である。右から左は、恒真式 $B\to(\Box B\to B)$ に単調性を使えば得られる。$\square$

$B:=\bot$ とすると $\mathbf{GL}\vdash\Box(\Box\bot\to\bot)\leftrightarrow\Box\bot$ である。$\lnot\Box\bot$ と $\Box\bot\to\bot$ は恒真式の代入例で同値なので、$\mathbf{GL}\vdash\Box\lnot\Box\bot\leftrightarrow\Box\bot$ であり、対偶をとると
$$ \mathbf{GL}\vdash\lnot\Box\bot\to\lnot\Box\lnot\Box\bot $$
を得る。これは形式化された第2不完全性定理の様相の形である。

算術での読み方

$T$ を Robinson の算術 $\mathsf Q$ を含む理論、$\mathrm P(y)$ を $T$ の証明可能性述語、つまり Löbの定理 の定義「導出可能性条件」の (D1)〜(D3) を満たす論理式とする。$\bot$ は文 $0=S0$ を表す。

実現と証明可能性論理

命題変数に算術の文を対応させる写像 $f$ を、次の規則で様相論理式全体へ延長したものを 実現 という。
$$ f(\bot):=\bot,\quad f(A\to B):=f(A)\to f(B)\ \ (\lnot,\land,\lor\text{ も同様}),\quad f(\Box A):=\mathrm P(\ulcorner f(A)\urcorner). $$
すべての実現 $f$ で $T\vdash f(A)$ となる様相論理式 $A$ の全体を、$\mathrm P$ に関する $T$ の 証明可能性論理 という。

算術的健全性

$\mathbf{GL}\vdash A$ ならば、すべての実現 $f$ で $T\vdash f(A)$ である。

$T$ の証明可能性論理を $\Sigma_T$ と書く。$\mathbf{GL}$ は Löb の図式を含む最小の正規様相論理なので、$\Sigma_T$ が正規様相論理で Löb の図式の形の論理式を含むことを示せばよい。$f$ を任意の実現とする。

  • 恒真式の代入例 $C$ について、$f$ は命題の結合子を保つので $f(C)$ も恒真式の代入例であり、$T\vdash f(C)$ である。
  • K 公理の $f$ による像は、(D2) の $\varphi:=f(A)$、$\psi:=f(B)$ の場合である。
  • Löb の図式の像は、$\varphi:=f(A)$ として $\mathrm P(\ulcorner\mathrm P(\ulcorner\varphi\urcorner)\to\varphi\urcorner)\to\mathrm P(\ulcorner\varphi\urcorner)$ である。これは Löbの定理 の定理「Löb の定理の形式化」により $T$ で証明できる。
  • モーダスポネンスで閉じることは、$f(A\to B)=f(A)\to f(B)$ による。
  • 必然化:$A\in\Sigma_T$ なら $T\vdash f(A)$ なので、(D1) により $T\vdash\mathrm P(\ulcorner f(A)\urcorner)$、すなわち $T\vdash f(\Box A)$ である。$\square$

読み方の対応を表にする。$\mathsf{PA}$ と自然に作った $\mathrm{Prov}_{\mathsf{PA}}$ が (D1)〜(D3) を満たすことは OLT26 §37.6 で述べられている(この記事では証明しない)。

$\mathbf{GL}$ の定理算術での内容
$\Box(A\to B)\to(\Box A\to\Box B)$(D2):前件肯定を理論の中で行える
$\Box A\to\Box\Box A$(D3):証明できることを理論の中で証明できる
$\Box(\Box A\to A)\to\Box A$形式化された Löbの定理
$\lnot\Box\bot\to\lnot\Box\lnot\Box\bot$形式化された第2不完全性定理

一方、$\Box A\to A$ は $\mathbf{GL}$ の定理ではない。$\mathsf{PA}$ の健全性により、$f(\Box A\to A)$ は標準モデル $\mathfrak N$ で真である。しかし $A:=\bot$ の場合が $\mathsf{PA}$ の無矛盾性にあたるので証明できない。「真である」と「証明できる」の差が、後の節の 2 つの Solovay の定理の差になる。

Kripke 意味論

逆整礎

フレーム $(W,R)$ の $R$ が 逆整礎(conversely well-founded)であるとは、$w_0Rw_1Rw_2R\cdots$ となる無限列がないことをいう。

逆整礎な $R$ は非反射的である($wRw$ なら $w,w,\dots$ が無限列になる)。$W$ が有限で $R$ が推移的なら、逆に非反射的な $R$ は逆整礎である。無限列には同じ世界が 2 度現れ、推移性により $wRw$ となるからである。

Löb の図式とフレームの対応

フレーム $\mathcal F=(W,R)$ について、次は同値である。

  1. Löb の図式の形の論理式がすべて $\mathcal F$ で妥当である。
  2. 命題変数 $p$ について、$\Box(\Box p\to p)\to\Box p$ が $\mathcal F$ で妥当である。
  3. $R$ は推移的かつ逆整礎である。

1 ⇒ 2 は明らかである。
3 ⇒ 1. $\mathcal F$ 上のモデルと世界 $w$ をとり、$w\not\Vdash\Box A$ とする。$wRv_0$、$v_0\not\Vdash A$ となる $v_0$ がある。$v_n$ に対し、$v_nRu$、$u\not\Vdash A$ となる $u$ があればそれを $v_{n+1}$ とする。$R$ は逆整礎なのでこの操作は有限回で止まり、止まった点 $v$ について $v\not\Vdash A$ かつ $v\Vdash\Box A$ である。推移性により $wRv$ である。$v$ で $\Box A\to A$ は偽なので、$w\not\Vdash\Box(\Box A\to A)$ である。よって Löb の図式の形の論理式は $w$ で真である。
2 ⇒ 3. 対偶を示す。$R$ が推移的でないとして、$wRv$、$vRu$ で $wRu$ でないものをとり、$V(p):=W\setminus\{v,u\}$ とする。$w\not\Vdash\Box p$ である($v\not\Vdash p$)。$wRx$ とする。$x\ne v$ なら $x\ne u$ でもあるので $x\Vdash p$ である。$x=v$ なら $u\not\Vdash p$ なので $v\not\Vdash\Box p$ である。どちらでも $x\Vdash\Box p\to p$ なので、$w\Vdash\Box(\Box p\to p)$ であり、2 の論理式は $w$ で偽である。
$w_0Rw_1R\cdots$ という無限列があるとして、$S:=\{w_i\mid i\ge1\}$、$V(p):=W\setminus S$ とする。$w_1\in S$ なので $w_0\not\Vdash\Box p$ である。$w_0Rx$ とする。$x\notin S$ なら $x\Vdash p$ である。$x=w_i$($i\ge1$)なら $w_{i+1}\in S$ なので $x\not\Vdash\Box p$ である。どちらでも $x\Vdash\Box p\to p$ なので、2 の論理式は $w_0$ で偽である。$\square$

証明の無限列の取り出しは従属選択を使う。この性質は一階の文では書けない(様相論理 の注意「一階の性質で書けない対応」)。

完全性と決定可能性

$\mathbf{GL}$ の完全性は Segerberg(1971 年)による。de Jongh と Kripke も独立に示した(Ver24 §3.2)。下の証明の形は JdJ97 定理 2.4 と同じである。

有限フレームについての完全性

様相論理式 $A$ について、次は同値である。

  1. $\mathbf{GL}\vdash A$。
  2. $A$ は推移的かつ逆整礎なすべてのフレームで妥当である。
  3. $A$ は世界の個数が $2^{|\operatorname{Sub}(A)|}$ 以下で、推移的かつ非反射的なすべてのフレームで妥当である。

1 ⇒ 2 は thm-pl-frame と 様相論理 の定理「健全性」による。とくに、1 点で $R=\emptyset$ のフレームで $\bot$ は偽なので、$\bot\notin\mathbf{GL}$ である。2 ⇒ 3 は def-pl-conversely-wf の後の注意による。
3 ⇒ 1 の対偶を示す。$\mathbf{GL}\not\vdash A$ とする。$\Phi:=\operatorname{Sub}(A)$ とし、$\mathbf{GL}$ 極大無矛盾集合 $\Delta$(様相論理 の定義「極大無矛盾集合と標準モデル」)から作る $\Delta\cap\Phi$ の全体を $W$ とする。$W$ の元は $\Phi$ の部分集合なので、$|W|\le2^{|\Phi|}$ である。$X,Y\in W$ について、$XRY$ を次の 2 条件で定める。

  • (i) $\Box B\in X$ なら $B\in Y$ かつ $\Box B\in Y$。
  • (ii) $\Box C\in Y$ かつ $\Box C\notin X$ となる $C$ がある。
    (ii) により $R$ は非反射的である。$XRY$、$YRZ$ とする。(i) を 2 回使うと $XRZ$ の (i) を得る。$XRY$ の (ii) の $\Box C$ は $YRZ$ の (i) により $Z$ に属するので、$XRZ$ の (ii) も成り立つ。よって $R$ は推移的である。$p\in\Phi$ なら $V(p):=\{X\mid p\in X\}$、そうでなければ $V(p):=\emptyset$ とする。

真理補題. $B\in\Phi$、$X\in W$ について $X\Vdash B\iff B\in X$ である。$B$ の組み立てに関する帰納法で示す。$\bot$ と命題変数は定義による。$X=\Delta\cap\Phi$ と書くと、$\lnot,\land,\lor,\to$ の場合は $\Delta$ が真理値表どおりにふるまうこと(様相論理 の補題「極大無矛盾集合の性質」)と帰納法の仮定による。
$B=\Box C$ とする。$\Box C\in X$ で $XRY$ なら、(i) により $C\in Y$、帰納法の仮定により $Y\Vdash C$ である。よって $X\Vdash\Box C$ である。
$\Box C\notin X$ とする。$\Box C\in\Phi$ なので $\Box C\notin\Delta$ である。次の集合が $\mathbf{GL}$ 無矛盾であることを示す。
$$ \Gamma:=\{D,\Box D\mid\Box D\in X\}\cup\{\Box C,\lnot C\}. $$
矛盾するとすると、有限個の $\Box D_i\in X$ で
$$ \mathbf{GL}\vdash\bigwedge_i(D_i\land\Box D_i)\to(\Box C\to C) $$
となる。単調性と連言の補題により $\mathbf{GL}\vdash\bigwedge_i\Box(D_i\land\Box D_i)\to\Box(\Box C\to C)$ である。$\Box D_i\in\Delta$ であり、prop-pl-four により $\Box\Box D_i\in\Delta$ なので、$\Box(D_i\land\Box D_i)\in\Delta$ である。よって $\Box(\Box C\to C)\in\Delta$ であり、Löb の図式により $\Box C\in\Delta$ となって矛盾する。
$\Gamma$ を含む極大無矛盾集合 $\Delta'$ をとり、$Y:=\Delta'\cap\Phi$ とする。(i) は $\Gamma$ の作り方から成り立つ。$\Box C\in Y$、$\Box C\notin X$ なので (ii) も成り立ち、$XRY$ である。$\lnot C\in\Delta'$ なので $C\notin Y$ であり、帰納法の仮定により $Y\not\Vdash C$ である。よって $X\not\Vdash\Box C$ である。
結論. $\{\lnot A\}$ は $\mathbf{GL}$ 無矛盾なので、$\lnot A\in\Delta$ となる $\Delta$ がある。$X:=\Delta\cap\Phi$ とすると $A\notin X$ なので、真理補題により $X\not\Vdash A$ である。$(W,R)$ は 3 の形のフレームで、$A$ はそこで妥当でない。$\square$

決定可能性

$\mathbf{GL}$ の定理であるかどうかは決定可能である。

世界の個数が $2^{|\operatorname{Sub}(A)|}$ 以下の推移的かつ非反射的なフレームと、$A$ に現れる命題変数の付値は有限個しかない。そのすべてで $A$ の真偽を計算すればよい(thm-pl-completeness の 1 と 3 の同値)。$\square$

$\mathbf{GL}$ は有限の推移的かつ非反射的な木についても完全である(この形も Segerberg による。Pak17 §2)。

木にする方法を開く

世界 $w$ から始まる $wRx_1Rx_2\cdots Rx_m$ の形の有限列の全体を世界とし、列の真の始切片の関係を到達可能関係とし、付値は列の最後の世界で定める。$R$ の推移性により、列の最後の世界に写す写像は論理式の真偽を保つ($\Box$ の帰納法)。


標準モデルを使う 様相論理 の完全性の証明は $\mathbf{GL}$ には通らない。無矛盾な集合がモデルをもつとは限らないからである(JdJ97 §2)。

コンパクト性が成り立たない

$\Gamma:=\{\Diamond p_0\}\cup\{\Box(p_i\to\Diamond p_{i+1})\mid i\in\mathbb N\}$ は $\mathbf{GL}$ 無矛盾だが、推移的かつ逆整礎なフレームのどの世界でも、$\Gamma$ の元がすべて同時に真になることはない。

証明を開く

$\Gamma$ の有限部分は、ある $n$ までの $\Box(p_i\to\Diamond p_{i+1})$ と $\Diamond p_0$ に含まれる。世界を $w,x_0,\dots,x_{n+1}$ とし、この順に後ろの世界へ到達できる関係を $R$ とし、$V(p_i):=\{x_i\}$($i\le n+1$)とする。この有限のフレームは推移的かつ非反射的で、$w$ でこれらの論理式はすべて真である。thm-pl-completeness の 1 ⇒ 2 により、$\Gamma$ の有限部分は矛盾しない。

推移的なフレームの世界 $w$ で $\Gamma$ の元がすべて真なら、$wRx_0$、$x_0\Vdash p_0$ となる $x_0$ がある。$wRx_i$、$x_i\Vdash p_i$ なら、$w\Vdash\Box(p_i\to\Diamond p_{i+1})$ により $x_iRx_{i+1}$、$x_{i+1}\Vdash p_{i+1}$ となる $x_{i+1}$ があり、推移性により $wRx_{i+1}$ である。こうして無限列ができるので、$R$ は逆整礎でない。$\square$

文字を含まない論理式

命題変数を含まない論理式を 文字を含まない 論理式という。$\Box^0\bot:=\bot$、$\Box^{n+1}\bot:=\Box\Box^n\bot$ とおく。実現 $f$ は命題変数にしか依存しないので、文字を含まない $A$ の像 $f(A)$ は $f$ によらない。これを $A^\ast$ と書く。$(\lnot\Box\bot)^\ast$ は $T$ の無矛盾性を表す文である。
推移的かつ非反射的な有限フレームの世界 $w$ の 高さ $\rho(w)$ を、$wRv$ となる $v$ がなければ $0$、あれば $1+\max\{\rho(v)\mid wRv\}$ と定める。$wRv$ なら $\rho(v)<\rho(w)$ である。逆に $m<\rho(w)$ なら、$\rho$ が $1$ ずつ下がる列をたどり推移性を使うと、$wRv$、$\rho(v)=m$ となる $v$ がある。したがって $w$ の到達先の高さの全体はちょうど $\{0,\dots,\rho(w)-1\}$ である。
文字を含まない論理式 $A$ に $S(A)\subset\mathbb N$ を次で対応させる。
$$ S(\bot):=\emptyset,\quad S(\lnot A):=\mathbb N\setminus S(A),\quad S(A\land B):=S(A)\cap S(B),\quad S(\Box A):=\{n\mid\{0,\dots,n-1\}\subset S(A)\}, $$
$\lor,\to$ は真理値表のとおりとする。

標準形

$A,B$ を文字を含まない論理式とする。

  1. 推移的かつ非反射的な有限フレームの世界 $w$ について、$w\Vdash A\iff\rho(w)\in S(A)$ である。
  2. $\mathbf{GL}\vdash A\iff S(A)=\mathbb N$ である。$S(A)\subset S(B)$ なら $\mathbf{GL}\vdash A\to B$ である。
  3. $S(\Box^n\bot)=\{0,\dots,n-1\}$ である。$S(A)$ は有限集合または補有限集合であり、$A$ は $\Box^n\bot$ たちの Boole 結合と $\mathbf{GL}$ で同値である。
証明を開く

1:$A$ の組み立てに関する帰納法による。$\Box A$ の場合は、$w$ の到達先の高さの全体が $\{0,\dots,\rho(w)-1\}$ であることによる。

2:$S(A)=\mathbb N$ なら、1 により $A$ は thm-pl-completeness の 3 の形のフレームで妥当なので定理である。$n\notin S(A)$ なら、$\{0,\dots,n\}$ に $i>j$ で $iRj$ と定めたフレームの世界 $n$ の高さは $n$ なので、1 により $A$ は偽であり、定理でない。後半は $S(A\to B)=\mathbb N$ による。

3:前半は $n$ についての帰納法による。$S(\Box A)$ は、$S(A)=\mathbb N$ なら $\mathbb N$、そうでなければ $k:=\min(\mathbb N\setminus S(A))$ として $\{0,\dots,k\}$ である。したがって帰納法により $S(A)$ は有限集合または補有限集合である。1 点集合は $\{n\}=S(\Box^{n+1}\bot\land\lnot\Box^n\bot)$ なので、$S(A)$ は $S(B)$ の形に書ける($B$ は Boole 結合)。2 により $\mathbf{GL}\vdash A\leftrightarrow B$ である。$\square$

文字を含まない文の真偽と証明可能性

$T=\mathsf{PA}$ とし、$\mathrm P$ は (D1)〜(D3) を満たす $\mathrm{Prov}_{\mathsf{PA}}$ とする。文字を含まない $A$ について次が成り立つ。

  1. $\mathfrak N\models A^\ast\iff S(A)$ は補有限集合である。
  2. $\mathsf{PA}\vdash A^\ast\iff S(A)=\mathbb N\iff\mathbf{GL}\vdash A$ である。
証明を開く

すべての $n$ について $(\Box^n\bot)^\ast$ は $\mathfrak N$ で偽である。実際、$n=0$ では明らかで、$(\Box^{n+1}\bot)^\ast$ が真なら、Gödelの不完全性定理 の補題「証明可能性の表現」の 2 により $\mathsf{PA}\vdash(\Box^n\bot)^\ast$ であり、$\mathfrak N$ が $\mathsf{PA}$ のモデルなので $(\Box^n\bot)^\ast$ は真となる。

1:prop-pl-letterless の 3 の Boole 結合 $B$ と thm-pl-arithmetical-soundness により、$\mathfrak N\models A^\ast\iff\mathfrak N\models B^\ast$ である。$B$ の各成分 $\Box^n\bot$ の $S$ は有限で文は偽なので、$\mathfrak N\models B^\ast$ と「$S(B)$ が補有限」は Boole 結合で同じように変わる。

2:$S(A)=\mathbb N$ なら prop-pl-letterless の 2 と thm-pl-arithmetical-soundness により $\mathsf{PA}\vdash A^\ast$ である。$n\notin S(A)$ とする。$S(A)\subset\mathbb N\setminus\{n\}=S(\Box^{n+1}\bot\to\Box^n\bot)$ なので、$\mathbf{GL}\vdash A\to(\Box^{n+1}\bot\to\Box^n\bot)$ である。$\mathsf{PA}\vdash A^\ast$ なら、$\psi:=(\Box^n\bot)^\ast$ として $\mathsf{PA}\vdash\mathrm P(\ulcorner\psi\urcorner)\to\psi$ となり、Löbの定理 により $\mathsf{PA}\vdash\psi$ である。これは $\psi$ が $\mathfrak N$ で偽であることに反する。$\square$

$A$$S(A)$$\mathfrak N$ で$\mathsf{PA}$ で
$\lnot\Box\bot$(無矛盾性)$\mathbb N\setminus\{0\}$真証明できない
$\Box\bot$$\{0\}$偽証明できない
$\Box\lnot\Box\bot$$\{0\}$偽証明できない
$\lnot\Box\bot\to\lnot\Box\lnot\Box\bot$$\mathbb N$真証明できる
$\Box\Box\bot\to\Box\bot$$\mathbb N\setminus\{1\}$真証明できない

表の右の 2 列は cor-pl-letterless-pa による。

不動点定理

$A(p)$ を様相論理式とする。$p$ のすべての現れが $\Box$ の作用域の中にあるとき、$p$ は $A(p)$ で 箱の中にある という。$A(B)$ は $p$ に $B$ を代入した論理式を表す。対角化補題 は $\mathrm P$ を含む算術の論理式の不動点の存在を与えるが、箱の中にある $p$ については、不動点が $\mathbf{GL}$ の中で明示的に書ける。

不動点の一意性

$p$ が $A(p)$ で箱の中にあり、$q$ は $A(p)$ に現れないとする。このとき
$$ \mathbf{GL}\vdash\boxdot(p\leftrightarrow A(p))\land\boxdot(q\leftrightarrow A(q))\to(p\leftrightarrow q) $$
である。

証明を開く

thm-pl-completeness により、推移的かつ非反射的な有限フレームの上のモデルの世界 $w$ で前件が真なら、$w$ で $p,q$ の真偽が一致することを示せばよい。$U:=\{w\}\cup\{x\mid wRx\}$ とする。推移性により $U$ は到達で閉じ、$U$ の各点で $p\leftrightarrow A(p)$ と $q\leftrightarrow A(q)$ は真である。

$x\in U$ で $p,q$ の真偽が一致することを、$\rho(x)$ についての帰納法で示す。$x$ の到達先のすべての点で $p,q$ の真偽が一致するとする。$x$ の到達先から到達できる点も $x$ の到達先なので、任意の論理式 $C(p)$ と $x$ の到達先の $y$ について、$C$ の組み立てに関する帰納法により $y\Vdash C(p)\iff y\Vdash C(q)$ である。よって $x\Vdash\Box C(p)\iff x\Vdash\Box C(q)$ である。$p$ は箱の中にあるので、$A(p)$ は $p$ 以外の命題変数と $\Box C(p)$ の形の論理式の Boole 結合である。したがって $x\Vdash A(p)\iff x\Vdash A(q)$ となり、$x$ で $p,q$ の真偽が一致する。$\square$

一意性は Bernardi が最初に示した(JdJ97 §4)。$B,C$ が $\mathbf{GL}\vdash B\leftrightarrow A(B)$、$\mathbf{GL}\vdash C\leftrightarrow A(C)$ を満たすなら、代入と必然化により $\mathbf{GL}\vdash B\leftrightarrow C$ である。

de Jongh–Sambin の不動点定理

$p$ が $A(p)$ で箱の中にあるなら、$p$ を含まず、$A(p)$ に現れる命題変数だけを含む論理式 $B$ で
$$ \mathbf{GL}\vdash B\leftrightarrow A(B) $$
となるものがある。

所在

de Jongh と Sambin が 1975 年に独立に証明した(Ver24 §2.2、JdJ97 定理 4.3)。一般の証明はこの記事では与えない。

次の例では $B$ を直接確かめられる。

$A(p)$不動点 $B$算術の文の例
$\lnot\Box p$$\lnot\Box\bot$Gödel 文
$\Box p$$\top$「私は証明できる」と述べる文
$\Box\lnot p$$\Box\bot$「私の否定は証明できる」と述べる文
$\lnot\Box\lnot p$$\bot$「私は無矛盾である」と述べる文
$\Box p\to q$$\Box q\to q$Löb の証明の文
$\Box(p\to q)$$\Box q$
表の確かめ

2・4 行目以外は lem-pl-box-loeb に帰着する。$\Box\lnot\Box\bot$ と $\Box(\Box\bot\to\bot)$ は単調性で同値なので、$\mathbf{GL}\vdash\Box\lnot\Box\bot\leftrightarrow\Box\bot$ である。

各行を開く

1 行目:$A(B)=\lnot\Box\lnot\Box\bot$ は $\lnot\Box\bot$ と同値である。2 行目:$\Box\top$ は定理である。3 行目:$A(B)=\Box\lnot\Box\bot$ は $\Box\bot$ と同値である。4 行目:$A(\bot)=\lnot\Box\lnot\bot$ で、$\Box\lnot\bot$ は定理なので $\bot$ と同値である。5 行目:$A(B)=\Box(\Box q\to q)\to q$ は lem-pl-box-loeb により $\Box q\to q$ と同値である。6 行目:$A(B)=\Box(\Box q\to q)$ は $\Box q$ と同値である。

算術の不動点の決定

$T,\mathrm P$ を def-pl-realization のとおりとし、$p$ が $A(p)$ で箱の中にあり、$B$ を thm-pl-fp-existence の不動点とする。$f$ を実現とし、文 $\sigma$ について、$p$ の値だけを $\sigma$ に替えた実現を $f'$ とする。$T\vdash\sigma\leftrightarrow f'(A(p))$ ならば $T\vdash\sigma\leftrightarrow f(B)$ である。

証明を開く

thm-pl-fp-uniqueness の $q$ に $B$ を代入すると、$\boxdot(B\leftrightarrow A(B))$ は定理なので、$\mathbf{GL}\vdash\boxdot(p\leftrightarrow A(p))\to(p\leftrightarrow B)$ である。$f'$ で写し、thm-pl-arithmetical-soundness を使う。仮定と (D1) により $T\vdash f'(\boxdot(p\leftrightarrow A(p)))$ である。$B$ は $p$ を含まないので $f'(B)=f(B)$ であり、$T\vdash\sigma\leftrightarrow f(B)$ を得る。$\square$

$A(p)=\lnot\Box p$ の場合、これは Gödel 文が無矛盾性の文と $T$ で同値であることを述べている(Gödelの不完全性定理)。$A(p)=\Box p$ の場合は Löbの定理 の系「自分の証明可能性を主張する文」である。このように、箱の中にある $p$ の不動点は $\Box$ と命題の結合子だけで書ける文に同値であり、対角化で新しい種類の文は得られない。証明の順序を使う Rosser の文は、$\Box$ だけでは書けないのでこの枠の外にある(JdJ97 §4)。

Solovay の算術的完全性定理

以下、$T$ は再帰的に枚挙できる公理系で、$\mathrm P$ はその自然な証明可能性述語とする。

Solovay の第 1 算術的完全性定理

$T$ が $\mathrm I\Sigma_1$ を含み、$\Sigma_1$ 健全($T$ で証明できる $\Sigma_1$ 文は $\mathfrak N$ で真)なら、
$$ \mathbf{GL}\vdash A\iff\text{すべての実現 }f\text{ で }T\vdash f(A) $$
である。

所在と適用範囲

$\mathsf{PA}$ の場合が Solovay(1976 年)の定理である(Ver24 §4.2、JdJ97 定理 1.1)。$\Rightarrow$ は (D1)〜(D3)(JdJ97 §3)と thm-pl-arithmetical-soundness による。$\Leftarrow$ はこの記事では証明しない。$\Sigma_1$ 健全性は、$\mathrm P$ についての無矛盾性の反復 $\lnot\Box^n\bot$ の像がすべて $\mathfrak N$ で真であること(無限の高さ)にまで弱められる(Visser の定理。$T\supset\mathsf{PA}$ の場合、JdJ97 定理 6.1)。$\mathrm I\Sigma_1$ を含むという条件も、$\mathrm I\Delta_0+\mathrm{EXP}$ を含むという条件に弱められる(de Jongh–Jumelet–Montagna。JdJ97 §6)。

実現がすべて $\mathfrak N$ で 真 になる論理式は、反映の図式を足した体系で表せる。論理式 $A$ が $\mathbf S$ の定理 であるとは、ある $B_1,\dots,B_k$ で $\mathbf{GL}\vdash\bigwedge_i(\Box B_i\to B_i)\to A$ となることをいう。$\mathbf S$ はモーダスポネンスで閉じているが、必然化では閉じていない。

Solovay の第 2 算術的完全性定理

$T\supset\mathsf{PA}$ が $\mathfrak N$ で健全なら、
$$ \mathbf S\vdash A\iff\text{すべての実現 }f\text{ で }\mathfrak N\models f(A) $$
である。

所在

JdJ97 定理 1.2・6.2。$\Leftarrow$ はこの記事では証明しない。$\Rightarrow$ は thm-pl-arithmetical-soundness と、$\mathfrak N$ で $f(\Box B\to B)$ が真であることによる。$B_i$ は $A$ の部分論理式 $\Box B$ の $B$ に限ってよいので、$\mathbf S$ も決定可能である(同定理 2.7 とその証明)。

2 つの定理により、$\mathsf{PA}$ が証明できることと、$\mathsf{PA}$ について真であることの差は、命題の形では $\Box B\to B$ の形の文だけで表される。
第 1 定理の $\Leftarrow$ の証明は、有限モデルの世界を算術の文に埋め込み、到達可能関係を「$T$ が無矛盾と認める」関係に写す。

Solovay の証明の筋

JdJ97 §3 の筋を述べる。

筋を開く

段 1:$\mathbf{GL}\not\vdash A$ なら、thm-pl-completeness により、世界が $1,\dots,n$、根が $1$ の有限モデルで $1\not\Vdash A$ となるものがある。$1$ の下に新しい根 $0$ を加える。

段 2:再帰定理を使い、原始再帰的な関数 $h$ と「$h$ の極限は $w$」と述べる文 $\mathrm{Lim}_w$($w=0,\dots,n$)を同時に定義する。$h(0)=0$ とし、$x$ が $h(x)Rw$ となる $w$ についての $\lnot\mathrm{Lim}_w$ の $T$ での証明の番号なら $h(x+1)=w$、それ以外なら $h(x+1)=h(x)$ とする。

段 3:$T$ で次が示せる。$\mathrm{Lim}_w$ のどれかが成り立ち、2 つは同時に成り立たない。$wRu$ なら $\mathrm{Lim}_w$ は $\lnot\mathrm{Lim}_u$ の証明がないことを導く。$w\ne0$ で $wRu$ でないなら、$\mathrm{Lim}_w$ は $\lnot\mathrm{Lim}_u$ の証明があることを導く。さらに $\Sigma_1$ 健全性により $\mathrm{Lim}_0$ は真で、$\mathrm{Lim}_1$ は $T$ と無矛盾である。

段 4:$f(p):=\bigvee\{\mathrm{Lim}_w\mid w\ne0,\ w\Vdash p\}$ とおくと、$w\ne0$ について、$w\Vdash B$ なら $T+\mathrm{Lim}_w\vdash f(B)$、$w\not\Vdash B$ なら $T+\mathrm{Lim}_w\vdash\lnot f(B)$ である。$w=1$、$B=A$ として $T\not\vdash f(A)$ を得る。

Pak17 は、文の定義に不動点を使わない別の証明を与えている。たとえば $0=1$ の最小の証明の番号 $x$ について、$x$ の反復対数の偶奇を述べる文を使う。
実現を 1 つに固定できる強い形もある。$\mathsf{PA}$ の文の列 $\sigma_0,\sigma_1,\dots$ で、$p_i\mapsto\sigma_i$ で定まる実現 $f$ について、すべての $A$ で $\mathbf{GL}\vdash A\iff\mathsf{PA}\vdash f(A)$ となるものがある(JdJ97 系 5.2)。
適用範囲については次のことが知られている。

  • 有界算術 $\mathrm I\Delta_0+\Omega_1$ の証明可能性論理が $\mathbf{GL}$ かどうかは、2024 年の時点の解説 Ver24 §5.1 で未解決とされている。
  • 述語論理の形では事情が異なる。$\mathsf{PA}$ を含み $\mathfrak N$ で健全な再帰的に枚挙できる $T$ について、実現がすべて $T$ で証明できる述語様相論理式の全体は再帰的に枚挙できない(Vardanyan。JdJ97 §16)。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなること
thm-pl-frame の推移性$W=\{a,b,c\}$、$R=\{(a,b),(b,c)\}$、$V(p)=\emptyset$Löb の図式が $a$ で真
同じ定理の逆整礎性(無限のフレーム)$(\mathbb N,<)$、$V(p)=\emptyset$Löb の図式が $0$ で真
thm-pl-completeness の非反射性1 点 $w$、$R=\{(w,w)\}$、$V(p)=\emptyset$Löb の図式が $w$ で真
thm-pl-completeness の論理式が有限個であることprop-pl-noncompact の $\Gamma$無矛盾な集合がモデルをもつこと
導出可能性条件の (D2)・(D3)$\mathrm P:=\mathrm{Prov}^\ast_T$(Löbの定理 の反例の表のもの)thm-pl-arithmetical-soundness
thm-pl-solovay-1 の $\Sigma_1$ 健全性$T:=\mathsf{PA}+\lnot\mathrm{Con}_{\mathsf{PA}}$、$A:=\Box\bot$「すべての $f$ で $T\vdash f(A)$ なら $\mathbf{GL}\vdash A$」
体系 $\mathbf S$ が必然化で閉じないこと$\Box\bot\to\bot$ に必然化を使う無矛盾性
不動点定理の「箱の中」(存在)$A(p)=\lnot p$不動点の存在
不動点定理の「箱の中」(一意性)$A(p)=p$不動点の一意性
反例の確かめ

フレームの反例は、それぞれ外した条件だけを満たしていない。

各行を開く

$a,b,c$ のフレーム:$R$ は非反射的で無限列をもたない。$(a,c)\notin R$ なので推移的でない。$b\not\Vdash\Box p$ なので $b\Vdash\Box p\to p$ であり、$a$ の到達先は $b$ だけなので $a\Vdash\Box(\Box p\to p)$ である。$a\not\Vdash\Box p$ である。

$(\mathbb N,<)$:推移的かつ非反射的である。どの $n$ でも $n\not\Vdash\Box p$ なので $n\Vdash\Box p\to p$ であり、$0\Vdash\Box(\Box p\to p)$、$0\not\Vdash\Box p$ である。

1 点の反射的なフレーム:推移的かつ有限である。$w\not\Vdash\Box p$ なので $w\Vdash\Box p\to p$ であり、$w\Vdash\Box(\Box p\to p)$、$w\not\Vdash\Box p$ である。

$\mathrm{Prov}^\ast_T$:$T$ を $\mathsf Q$ を含む無矛盾な決定可能な公理系とする。Löbの定理 の例「反例の確かめ」により、これは (D1) を満たし、$T\vdash\lnot\mathrm{Prov}^\ast_T(\ulcorner\bot\urcorner)$ である。$\Box$ をこの述語で読むと、$T\vdash\Box\bot\to\bot$、(D1) により $T\vdash\Box(\Box\bot\to\bot)$ である。Löb の図式のこの例が $T$ で証明できるなら $T\vdash\Box\bot$ となり、$T$ が矛盾する。

$T=\mathsf{PA}+\lnot\mathrm{Con}_{\mathsf{PA}}$:第2不完全性定理により $T$ は無矛盾である。$T\vdash\mathrm{Prov}_{\mathsf{PA}}(\ulcorner\bot\urcorner)$ で、$\mathsf{PA}$ の導出は $T$ の導出なので $T\vdash\mathrm{Prov}_T(\ulcorner\bot\urcorner)$ である。一方 $W=\{a,b\}$、$R=\{(a,b)\}$ のフレームの $a$ で $\Box\bot$ は偽なので、$\mathbf{GL}\not\vdash\Box\bot$ である。偽の $\Sigma_1$ 文 $\lnot\mathrm{Con}_{\mathsf{PA}}$ を証明するので $T$ は $\Sigma_1$ 健全でない。

$\mathbf S$ の必然化:$\Box(\Box\bot\to\bot)$ を足すと、lem-pl-box-loeb により $\Box\bot$ が出て、反映 $\Box\bot\to\bot$ と合わせて $\bot$ が出る。したがって $\mathbf{GL}$ に反映の図式を足して正規様相論理にすると矛盾する。

$A(p)=\lnot p$:$B\leftrightarrow\lnot B$ は恒真式の否定の形で、定理になると $\mathbf{GL}$ が矛盾する。$A(p)=p$:すべての $B$ が不動点で、$\top$ と $\bot$ は同値でない。

関連項目

参考文献

[1]
Giorgi Japaridze, Dick de Jongh, The Logic of Provability, ILLC Prepublication Series ML-1997-01(Handbook of Proof Theory, Elsevier, 1998, Chapter VII, pp. 475–546 の原稿), 1997, §1 定理 1.1・1.2、§2 定理 2.4・2.7(非コンパクト性の注意を含む)、§3(Solovay の定理の証明、補題 3.2・3.3)、§4 定理 4.1–4.3、§5 系 5.2、§6 定理 6.1・6.2、§16(述語の場合、Vardanyan の結果)

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