タルスキの定義不可能性定理
次の定理は、「 T* は一階算術の式で定義できるだろうか」という問いに答えるものである。
タルスキの定義不可能性定理 ― T* を定義する L-式 True(n) は存在しない。 すなわち、L-式 True(n) で、全ての L-文 A に対して True(g(A)) ↔ A が N で成り立つようなものは存在しない。
この定理は、大まかに言えば、一階算術の文の真理の概念を一階算術の式で定義できないことを主張する。これは"自己表現"の範囲における重要な制限を意味する。True(n) を定義すること自体は可能であるが、それは L を超える表現力を持つメタ言語を引き合いに出すことによってのみ可能である。例えば、一階算術の真理述語は二階算術の中で定義することが可能である。しかしながら、この式は元々の語彙 L の真理述語しか定義できない。メタ言語の真理述語を定義するには、さらに高位のメタ言語を必要とする、といった具合になる。
この定理を証明するために、背理法で進める。
証明 — 示すべきことに反し、L-式 True(n) が存在して以下を満たすと仮定する:N で真である L-文のゲーデル数が n であるときかつそのときに限り True(n) が真である。
1931年、クルト・ゲーデルはゲーデルの不完全性定理を発表した。この定理は形式論理の構文を一階算術で表現する方法を示すことで証明された。算術の形式言語の各表現には個別の番号を割り振ることができ、この手続きはゲーデル数化、コード化、より一般に算術化などと呼ばれて知られている。特に、様々な式の集合は数の集合としてコード化される。様々な構文的性質(式であること、文であること、など)について、これらの集合は帰納的集合である。さらに、数の計算可能な集合は何らかの算術的な式によって定義することができる。例えば、算術の言語には算術式や証明可能な算術文のコードの集合を定義する式がある。
定義不可能性定理は、真理のような意味論的概念をこのようにコード化することができないことを示す。これは、十分に豊かに解釈される言語で、自身の意味論を表現できるものはないことを示している。このことから、対象言語の意味論を表現できるようなメタ言語は、その対象言語の意味論を超える表現能力を持たなければならないことになる。メタ言語は、対象言語にはない原始概念(英語版)、公理、規則を含んでおり、対象言語では証明できない定理であってメタ言語では証明可能であるものがある。