対角化定理

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

## 背景
\mathbb{N}を自然数の集合とする。算術の言語における一階 Tと計算可能関数f: \mathbb{N}\rightarrow\mathbb{N}について、「Tがfを*表現*（represent）する」とは、各n \in \mathbb{N}に対して以下が成り立つ「グラフ」論理式\mathcal{G}_f(x, y)がTの言語に存在することをいう。
: \vdash_{T}\,(\forall y)[(^\circ f(n)=y) \Leftrightarrow \mathcal{G}_f(^\circ n,\,y)]
ここで、{}^\circ nは自然数nに対応する数詞（numeral）であり、Tにおける最初の数詞0のn番目の後者（successor）と定義される（^\circ0=0,\,^\circ(n+1)=S(^\circ n)）。

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

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

## 定理のステートメント
)
| name = 定理
}}

直感的には、\mathcal{C}は自己言及的文である。\mathcal{C}は、\mathcal{C}が性質\mathcal{F}を持つことを述べている。また、文\mathcal{C}は、与えられた文\mathcal{A}の同値類に対して、文\mathcal{F}(^\circ \#_{\mathcal{A}})の同値類を割り当てる操作の不動点と見なすこともできる。証明の中で構成された文\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)で与えられている。)

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

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

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

## 関連項目
*
*不動点定理の一覧
*原始帰納的算術
*自己言及
*自己言及のパラドックス

## 脚注
### 出典

### 注釈

## 参考文献
* George Boolos and Richard Jeffrey, 1989. *Computability and Logic*, 3rd ed. Cambridge University Press.  
* 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. 
* 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. *[https://philpapers.org/rec/SMUDAS Diagonalization and Self-Reference]*. Oxford Univ. Press.
* 
** 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.