対角化定理

数理論理学では、対角化定理 (対角線補題(diagonal lemma)、対角化補題(diagonalization lemma)、自己言及補題(self-reference lemma)または不動点定理(fixed point theorem)としても知られる)は、自然数の特定の形式理論、特にすべての計算可能関数を表すのに十分な強力な理論における、自己言及的文の存在を示す定理である。対角化定理によって存在が保証される文は、ゲーデルの不完全性定理やタルスキの定義不可能性定理などの基本的な限界を証明するために使用できる。

背景

$\mathbb {N}$を自然数の集合とする。算術の言語における一階理論 $T$は、計算可能関数$f:\mathbb {N} \rightarrow \mathbb {N}$について、もし$T$の言語における「グラフ」論理式${\mathcal {G}}_{f}(x,y)$が存在し、各$n\in \mathbb {N}$に対して以下が成り立つ場合に、$f$を表現(represent)する。

$\vdash _{T}\,(\forall y)[(^{\circ }f(n)=y)\Leftrightarrow {\mathcal {G}}_{f}(^{\circ }n,\,y)]$.

ここで、${}^{\circ }n$は自然数$n$に対応する数詞(numeral)であり、$T$における最初の数詞$0$の$n$番目の後者(successor)と定義される。

対角化定理はまた、すべての式${\mathcal {A}}$に、そのゲーデル数と呼ばれる自然数$\#({\mathcal {A}})$($\#_{\mathcal {A}}$とも表記される)を割り当てる体系的な方法を必要とする。すると、式は$T$内でそのゲーデル数に対応する数詞によって表現できる。例えば、${\mathcal {A}}$は$^{\circ }\#_{\mathcal {A}}$によって表現される。

対角化定理は、原始再帰関数を全て表せる理論に適用される。そのような理論には、一階ペアノ算術や、より弱いロビンソン算術、さらにはRとして知られるはるかに弱い理論も含まれる。定理の一般的なステートメント(後述)は、理論が全ての計算可能関数を表せるというより強い仮定を立てるが、前述の各理論はその能力を持っている。

定理のステートメント

定理 ― $T$を算術の言語における一階理論であって全ての計算可能関数を表せるものとし、${\mathcal {F}}(y)$を$T$における論理式であって1つの自由変数を持つものとする。すると、以下のような文${\mathcal {C}}$が存在する。

$\vdash _{T}\,{\mathcal {C}}\Leftrightarrow {\mathcal {F}}({}^{\circ }\#_{\mathcal {C}})$

直感的には、${\mathcal {C}}$は自己言及的文である。${\mathcal {C}}$は、${\mathcal {C}}$が性質${\mathcal {F}}$を持つことを述べている。また、文${\mathcal {C}}$は、与えられた文${\mathcal {A}}$の同値類に対して、文${\mathcal {F}}(^{\circ }\#_{\mathcal {A}})$の同値類を割り当てる操作の不動点と見なすこともできる(文の同値類とは、理論$T$において論理的に同値なすべての文の集合である)。証明の中で構成された文${\mathcal {C}}$は、${\mathcal {F}}(^{\circ }\#_{\mathcal {C}})$と字面上は同じではないが、理論$T$において論理的に同値である。

証明

$f:\mathbb {N} \to \mathbb {N}$を、理論$T$における1つの自由変数$x$のみを持つ各論理式${\mathcal {A}}(x)$に対して以下のように定義された関数とする。

$f(\#_{\mathcal {A}})=\#[{\mathcal {A}}(^{\circ }\#_{\mathcal {A}})]$

ただし、$\#_{\mathcal {A}}=\#({\mathcal {A}}(x))$は式${\mathcal {A}}(x)$のゲーデル数を表す。また、$\#_{\mathcal {A}}$以外の$n$に対しては$f(n)=0$とする。この関数$f$は計算可能である(これは根源的にはゲーデル数の割り当て方法(Gödel numbering scheme)に関する仮定である)ので、$T$において$f$を表す式${\mathcal {G}}_{f}(x,\,y)$が存在する。すなわち

$\vdash _{T}\,(\forall y)\{{\mathcal {G}}_{f}(^{\circ }\#_{\mathcal {A}},\,y)\Leftrightarrow [y={}^{\circ }f(\#_{\mathcal {A}})]\}$

つまり

$\vdash _{T}\,(\forall y)\{{\mathcal {G}}_{f}(^{\circ }\#_{\mathcal {A}},\,y)\Leftrightarrow [y={}^{\circ }\#({\mathcal {A}}(^{\circ }\#_{\mathcal {A}}))]\}$

ここで、1つの自由変数$y$を持つ任意の式${\mathcal {F}}(y)$が与えられたとき、式${\mathcal {B}}(z)$を以下のように定義する。

${\mathcal {B}}(z):=(\forall y)[{\mathcal {G}}_{f}(z,\,y)\Rightarrow {\mathcal {F}}(y)]$

すると、1つの自由変数を持つ全ての式${\mathcal {A}}(x)$に対して以下が成り立つ。

$\vdash _{T}\,{\mathcal {B}}(^{\circ }\#_{\mathcal {A}})\Leftrightarrow (\forall y)\{[y={}^{\circ }\#({\mathcal {A}}(^{\circ }\#_{\mathcal {A}}))]\Rightarrow {\mathcal {F}}(y)\}$

つまり

$\vdash _{T}\,{\mathcal {B}}(^{\circ }\#_{\mathcal {A}})\Leftrightarrow {\mathcal {F}}(^{\circ }\#[{\mathcal {A}}(^{\circ }\#_{\mathcal {A}})])$

ここで、${\mathcal {A}}$を${\mathcal {B}}$に置き換え、文${\mathcal {C}}$を以下のように定義する。

${\mathcal {C}}:={\mathcal {B}}(^{\circ }\#_{\mathcal {B}})$

すると、前の行は以下のように書き直すことができる。

$\vdash _{T}\,{\mathcal {C}}\Leftrightarrow {\mathcal {F}}(^{\circ }\#_{\mathcal {C}})$

これが求める結果である。

(異なる用語による同じ議論は、[Raatikainen (2015a)]で与えられている。)

歴史

対角化定理はカントールの対角線論法と類似しているため、「対角化」と呼ばれる。「対角化定理」または「不動点」という用語は、クルト・ゲーデルの1931年の論文やアルフレト・タルスキの1936年の論文には登場しない。

ルドルフ・カルナップ (1934)は、一般自己言及補題(general self-reference lemma)を最初に証明した。これは、特定の条件を満たす理論Tにおける任意の式Fに対して、ψ ↔ F(°#(ψ))がTで証明可能であるような式ψが存在することを述べている。カルナップの研究は異なる用語で表現されていた。なぜなら、計算可能関数の概念は1934年にはまだ開発されていなかったからである。メンデルソン (1997, p. 204)は、対角化定理のようなものがゲーデルの推論に暗黙的に含まれていると述べたのはカルナップが最初であると信じている。ゲーデルは1937年までにはカルナップの研究を知っていた。

対角化定理は、計算可能性理論におけるクリーネの再帰定理と密接に関連しており、それぞれの証明は類似している。

関連項目

• 間接的自己言及
• 不動点定理の一覧
• 原始帰納的算術
• 自己言及
• 自己言及のパラドックス

参考文献

• George Boolos and Richard Jeffrey, 1989. Computability and Logic, 3rd ed. Cambridge University Press. ISBN 0-521-38026-X ISBN 0-521-38923-2
• Rudolf Carnap, 1934. Logische Syntax der Sprache. (English translation: 2003. The Logical Syntax of Language. Open Court Publishing.)
• Haim Gaifman, 2006. 'Naming and Diagonalization: From Cantor to Gödel to Kleene'. Logic Journal of the IGPL, 14: 709–728.
• Hinman, Peter, 2005. Fundamentals of Mathematical Logic. A K Peters. ISBN 1-56881-262-0
• Mendelson, Elliott, 1997. Introduction to Mathematical Logic, 4th ed. Chapman & Hall.
• Panu Raatikainen, 2015a. The Diagonalization Lemma. In Stanford Encyclopedia of Philosophy, ed. Zalta. Supplement to Raatikainen (2015b).
• Panu Raatikainen, 2015b. Gödel's Incompleteness Theorems. In Stanford Encyclopedia of Philosophy, ed. Zalta.
• Raymond Smullyan, 1991. Gödel's Incompleteness Theorems. Oxford Univ. Press.
• Raymond Smullyan, 1994. Diagonalization and Self-Reference. Oxford Univ. Press.
• Alfred Tarski (1936). “Der Wahrheitsbegriff in den formalisierten Sprachen”. Studia Philosophica 1: 261–405. オリジナルの9 January 2014時点におけるアーカイブ。. https://web.archive.org/web/20140109135345/http://www.ifispan.waw.pl/studialogica/s-p-f/volumina_i-iv/I-07-Tarski-small.pdf 2013年6月26日閲覧。. 
  • Alfred Tarski, tr. J. H. Woodger, 1983. "The Concept of Truth in Formalized Languages". English translation of Tarski's 1936 article. In A. Tarski, ed. J. Corcoran, 1983, Logic, Semantics, Metamathematics, Hackett.