レーブの定理

数理論理学におけるレーブの定理 (Löb's theorem) は、ペアノ算術 (PA) (またはPAを含む任意の形式体系)において、任意の論理式Pについて、﹁PがPAで証明可能ならばPである﹂ことがPAで証明可能ならば、PはPAで証明可能であることを述べている。Prov(P)が論理式Pが証明可能であることを意味する場合、レーブの定理をより形式的に表現すると次のようになる。

もし

${\displaystyle {\mathit {PA}}\vdash {\mathrm {Prov} ($P)\rightarrow P}} ${\mathit {PA}}\vdash {\mathrm {Prov} (P)\rightarrow P}$
ならば

${\mathit {PA}}\vdash P$${\mathit {PA}}\vdash P$
レーブの定理の直接的な帰結(対偶)は、PがPAで証明可能でない場合、﹁PがPAで証明可能ならば、Pである﹂はPAで証明可能でないということである。例えば、﹁$1+1=3$$1+1=3$がPAで証明可能ならば、$1+1=3$$1+1=3$である﹂はPAでは証明可能でない。

レーブの定理は、1955年にそれを定式化したマルティン・フーゴー・レーブにちなんで名付けられた。これはカリーのパラドックスに関連している。

証明可能性論理におけるレーブの定理

証明可能性論理は、ゲーデルの不完全性定理で使用される符号化の詳細を様相論理の言語を使って抽象化するものであり、具体的には与えられた体系における$\phi$$\phi$の証明可能性を様相$\Box \phi$$\Box \phi$を用いて表現する。

すると、レーブの定理を以下の公理として形式化できる。

$\Box (\Box P\rightarrow P)\rightarrow \Box P$$\Box (\Box P\rightarrow P)\rightarrow \Box P$
これは、ゲーデル＝レーブ (Gödel–Löb) の公理GLとして知られている。これは、次のような推論規則によって形式化されることもある。

もし

$\vdash \Box P\rightarrow P$$\vdash \Box P\rightarrow P$
ならば

$\vdash P$$\vdash P$
様相論理 K4 (あるいは、公理スキーマ4 ($\Box A\rightarrow \Box \Box A$$\Box A\rightarrow \Box \Box A$)は冗長であるため単にK)に上記の公理GLを追加した結果得られる証明可能性論理GLは、証明可能性論理において最も集中的に研究されている体系である。

レーブの定理の様相論理による証明

レーブの定理は、証明可能性演算子($/Box$$/Box$)に関するいくつかの基本的な規則(K4体系)と様相不動点の存在のみを用いて、様相論理内で証明することができる。

様相論理式

様相論理式 (modal formula)の文法として、以下を仮定する。

(一)$X$$X$が命題変数であれば、$X$$X$は論理式である。

(二)$K$$K$が命題定数であれば、$K$$K$は論理式である。

(三)$A$$A$が論理式であれば、$\Box A$$\Box A$は論理式である。

(四)$A$$A$と$B$$B$が論理式であれば、$\neg A$$\neg A$、$A\rightarrow B$$A\rightarrow B$、$A\wedge B$$A\wedge B$、$A\vee B$$A\vee B$、$A\leftrightarrow B$$A\leftrightarrow B$も論理式である。

様相文(modal sentence)とは、命題変数を含まない様相論理式のことである。$\vdash A$$\vdash A$は、$A$$A$が定理であることを意味する。

様相不動点

${\displaystyle F($X)} $F(X)$が命題変数$X$$X$を1つだけ持つ様相論理式であれば、${\displaystyle F($X)} $F(X)$の様相不動点は次のような文$\Psi$$\Psi$である。

$\vdash \Psi \leftrightarrow F(\Box \Psi )$$\vdash \Psi \leftrightarrow F(\Box \Psi )$
1つの自由変数を持つすべての様相論理式に対して、このような不動点が存在すると仮定する。これはもちろん自明な仮定ではないが、$\Box$$\Box$をペアノ算術における証明可能性として解釈すれば、様相不動点の存在は対角線補題から導かれる。

様相推論規則

様相不動点の存在に加えて、証明可能性演算子$\Box$$\Box$に対する以下の推論規則を仮定する。これらはヒルベルト＝ベルナイス証明可能性条件として知られている。

(一)(必然化規則) $\vdash A$$\vdash A$から$\vdash \Box A$$\vdash \Box A$を結論づける: これは非形式的には、Aが定理であればAが証明可能であることを意味する。

(二)(内部必然化法則) $\vdash \Box A\rightarrow \Box \Box A$$\vdash \Box A\rightarrow \Box \Box A$: Aが証明可能であれば、それが証明可能であることが証明可能である。

(三)(ボックス分配律) $\vdash \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)$$\vdash \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)$: この規則は、証明可能性演算子の内部でモーダスポネンスの適用を可能にする。AがBを含意することが証明可能であり、Aが証明可能であれば、Bも証明可能である。

レーブの定理の証明

証明の大部分は仮定$\Box P\to P$$\Box P\to P$を使用しないので、理解を容易にするために以下の証明は$\Box P\to P$$\Box P\to P$に依存する部分を最後の方に分離して記載する。

$P$$P$を任意の様相文とする。

(一)様相不動点の存在を論理式${\displaystyle F($X)=X\rightarrow P} $F(X)=X\rightarrow P$に適用する。すると、$\vdash \Psi \leftrightarrow (\Box \Psi \rightarrow P)$$\vdash \Psi \leftrightarrow (\Box \Psi \rightarrow P)$となるような文$\Psi$$\Psi$が存在することがわかる。

(二)$\vdash \Psi \rightarrow (\Box \Psi \rightarrow P)$$\vdash \Psi \rightarrow (\Box \Psi \rightarrow P)$ ︹1より︺。

(三)$\vdash \Box (\Psi \rightarrow (\Box \Psi \rightarrow P))$$\vdash \Box (\Psi \rightarrow (\Box \Psi \rightarrow P))$ ︹2と必然化規則により︺。

(四)$\vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)$$\vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)$ ︹3とボックス分配律より︺。

(五)$\vdash \Box (\Box \Psi \rightarrow P)\rightarrow (\Box \Box \Psi \rightarrow \Box P)$$\vdash \Box (\Box \Psi \rightarrow P)\rightarrow (\Box \Box \Psi \rightarrow \Box P)$ ︹$A=\Box \Psi$$A=\Box \Psi$および$B=P$$B=P$としてボックス分配律を適用することにより︺。

(六)$\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$$\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$ ︹4と5より︺。

(七)$\vdash \Box \Psi \rightarrow \Box \Box \Psi$$\vdash \Box \Psi \rightarrow \Box \Box \Psi$ ︹6と内部必然化規則により︺。

(八)$\vdash \Box \Psi \rightarrow \Box P$$\vdash \Box \Psi \rightarrow \Box P$ ︹6と7より︺。

ここから、証明の仮定を使用する部分に入る。


(九)$\vdash \Box P\rightarrow P$$\vdash \Box P\rightarrow P$と仮定する。大雑把に言えば、$P$$P$が証明可能であれば、それは実際には真であるという定理である。これは健全性 (soundness) の主張である。

(十)$\vdash \Box \Psi \rightarrow P$$\vdash \Box \Psi \rightarrow P$ ︹8と9より︺。

(11)$\vdash (\Box \Psi \rightarrow P)\rightarrow \Psi$$\vdash (\Box \Psi \rightarrow P)\rightarrow \Psi$ ︹1より︺。

(12)$\vdash \Psi$$\vdash \Psi$ ︹10と11より︺。

(13)$\vdash \Box \Psi$$\vdash \Box \Psi$ ︹12と必然化規則により︺。

(14)$\vdash P$$\vdash P$ ︹13と10より︺。

より非公式には、証明を次のように概説できる。

(一)仮定より${\displaystyle {\mathit {PA}}\vdash {\mathrm {Prov} _{PA}($P)\rightarrow P}} ${\mathit {PA}}\vdash {\mathrm {Prov} _{PA}(P)\rightarrow P}$なので、${\displaystyle {\mathit {PA}}\vdash {\neg P\rightarrow \neg \mathrm {Prov} _{PA}($P)}} ${\mathit {PA}}\vdash {\neg P\rightarrow \neg \mathrm {Prov} _{PA}(P)}$も成り立ち、これは${\displaystyle \{{\mathit {PA}},\neg P\}\vdash {\neg \mathrm {Prov} _{PA}($P)}} $\{{\mathit {PA}},\neg P\}\vdash {\neg \mathrm {Prov} _{PA}(P)}$を意味する。

(二)ここで、ハイブリッド理論$\{{\mathit {PA}},\neg P\}$$\{{\mathit {PA}},\neg P\}$について以下の推論ができる。
(一)$\{{\mathit {PA}},\neg P\}$$\{{\mathit {PA}},\neg P\}$が矛盾している(inconsistent)と仮定すると、PAから$\neg P\to \bot {}$$\neg P\to \bot {}$が証明でき、これは$P$$P$と同じである。

(二)しかし、$\{{\mathit {PA}},\neg P\}$$\{{\mathit {PA}},\neg P\}$について${\displaystyle \neg \mathrm {Prov} _{PA}($P)} $\neg \mathrm {Prov} _{PA}(P)$とわかっているので、矛盾が生じる。

(三)したがって、$\{{\mathit {PA}},\neg P\}$$\{{\mathit {PA}},\neg P\}$は無矛盾(consistent)である。

(三)ゲーデルの第2不完全性定理により、これは$\{{\mathit {PA}},\neg P\}$$\{{\mathit {PA}},\neg P\}$が矛盾していることを意味する。

(四)したがって、PAから$\neg P\to \bot {}$$\neg P\to \bot {}$が証明でき、これは$P$$P$と同じである。

例

レーブの定理の直接的な帰結は、PがPAで証明可能でない場合、﹁PがPAで証明可能ならば、Pは真である﹂はPAで証明可能でないということである。PAが無矛盾であるとして(ただし、PAはPAが無矛盾であることを知らない)、以下に簡単な例をいくつか挙げる。

●﹁$1+1=3$$1+1=3$がPAで証明可能ならば、$1+1=3$$1+1=3$である﹂はPAでは証明可能でない。なぜなら、$1+1=3$$1+1=3$はPAでは証明可能でない(偽であるため)からである。

●﹁$1+1=2$$1+1=2$がPAで証明可能ならば、$1+1=2$$1+1=2$である﹂はPAで証明可能である。﹁Xならば、$1+1=2$$1+1=2$である﹂という形式の文はすべて証明可能である。

●﹁強化版有限ラムゼーの定理がPAで証明可能ならば、強化版有限ラムゼーの定理が成り立つ﹂はPAで証明可能でない。なぜなら、﹁強化版有限ラムゼーの定理が成り立つ﹂はPAでは証明可能でない(標準モデルにおいて真であるにもかかわらず)からである。

信念論理において、レーブの定理は、形式系が反射的(reflexive)な﹁4型﹂の推論者として分類されるならば、その形式系は謙虚 (modest) でもある必要があることを示している。つまり、そのような推論者は、Pを信じるときのみ﹁私がPを信じるならばPである﹂と信じる。

ゲーデルの第2不完全性定理は、レーブの定理において偽の文$\bot$$\bot$をPに代入することによって導かれる。

逆: レーブの定理から様相不動点の存在を導く

様相不動点の存在からレーブの定理を導けるだけでなく、その逆も導ける。レーブの定理が公理(スキーマ)として与えられた場合、pが様相化された任意の論理式A(p)に対して、(互いに証明可能な文を同一視した)不動点${\displaystyle p\leftrightarrow A($p)} $p\leftrightarrow A(p)$の存在が導かれる。したがって、正規様相論理において、レーブの公理は公理スキーマ4 ($\Box A\rightarrow \Box \Box A$$\Box A\rightarrow \Box \Box A$)および様相不動点の存在の連言と同値である。

注釈

参考文献

●Boolos, George S. (1995). The Logic of Provability. ケンブリッジ大学出版局 (Cambridge University Press). ISBN 978-0-521-48325-4. https://archive.org/details/logicofprovabili0000bool 

●Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 978-1-56881-262-5 

●Japaridze, Giorgi; De Jongh, Dick (1998). “Chapter VII - The Logic of Provability”. In Buss, Samuel R.. Handbook of Proof Theory. Studies in Logic and the Foundations of Mathematics. 137. エルゼビア (Elsevier). pp. 475–546. doi:10.1016/S0049-237X(98)80022-0 

●Lindström, Per (June 2006). “Note on Some Fixed Point Constructions in Provability Logic”. Journal of Philosophical Logic 35 (3): 225–230. doi:10.1007/s10992-005-9013-8. 

●Löb, Martin (1955). “Solution of a Problem of Leon Henkin”. Journal of Symbolic Logic 20 (2): 115–118. doi:10.2307/2266895. JSTOR 2266895. 

●Smullyan, Raymond M. (1986). "Logicians who reason about themselves". Proceedings of the 1986 conference on Theoretical aspects of reasoning about knowledge, Monterey (CA). San Francisco (CA): Morgan Kaufmann Publishers Inc. pp. 341–352. doi:10.1016/B978-0-934613-04-0.50028-4. ISBN 9780934613040。

外部リンク

●“Löb's theorem” (2013年3月22日). 2023年12月14日閲覧。


●Provability Logic ︵英語︶ - スタンフォード哲学百科事典﹁Rineke (L.C.) Verbrugge﹂の項目。

●Yudkowsky, Eliezer (2008年8月17日). “The Cartoon Guide to Löb’s Theorem”. 2023年12月14日閲覧。