ゲーデルの不完全性定理
帰納的公理化可能な理論が自然数論を含むならば、当該理論における証明可能性が原始帰納的述語として表現できる。この証明可能性述語を用いて、「Gは証明できない」と同値となる証明不能命題G(ゲーデル文)が構成できる。ゲーデル文を構成するためには自然数論の式を自然数に変換するゲーデル数および自己言及で用いられる対角化の技法(を形式化したもの)が必要である。後者は対角化補題と呼ばれる。
自然数を変数とする述語「xは...である」の対角化は、上記の述語のxに「xは...である」自身のゲーデル数を代入した命題である。その意味は
「「xは...である」は...である」
となる。ゲーデル文Gは
「「xで表される述語の対角化は証明できない」で表される述語の対角化は証明できない」
と表される。「xで表される述語の対角化は証明できない」の対角化は、G自身と同値になる。
廣瀬健、横田一正『ゲーデルの世界 完全性定理と不完全性定理』海鳴社、1985年5月10日。ISBN 4-87525-106-8。 - ゲーデルの完全性定理と不完全性定理の解説書。両方の原論文の日本語訳が収録されている。
ゲーデル 著、林晋・八杉満利子 訳『ゲーデル 不完全性定理』岩波書店〈岩波文庫 青944-1〉、2006年9月15日。ISBN 4-00-339441-0。 - 前半の58頁が原論文の邦訳、残りの233頁が歴史的な背景を中心とした解説、という構成。
田中一之『ゲーデルに挑む 証明不可能なことの証明』藤村まりこ イラストレーション、東京大学出版会、2012年4月26日。ISBN 978-4-13-063900-2。 - 原論文の邦訳と解説。
前原昭二『数学基礎論入門(復刊)』朝倉書店〈基礎数学シリーズ 23〉、2006年3月20日(原著1977年6月1日)。ISBN 978-4-254-11723-3。
新井敏康『数学基礎論』岩波書店、2016年8月16日(原著2011年5月18日)。ISBN 978-4-00-005536-9 ISBN 978-4-00-730459-0。
田中一之 編著『数学基礎論講義 不完全性定理とその発展』日本評論社、1997年3月。ISBN 4-535-78241-5。
田中一之 編『ゲーデルと20世紀の論理学 1 ゲーデルの20世紀』東京大学出版会、2006年7月。ISBN 978-4-13-064095-4。
田中一之 編『ゲーデルと20世紀の論理学 2 完全性定理とモデル理論』東京大学出版会、2006年10月。ISBN 978-4-13-064096-1。
田中一之 編『ゲーデルと20世紀の論理学 3 不完全性定理と算術の体系』東京大学出版会、2007年3月。
P r o v a b l e A R G ( z , x ) {\displaystyle ProvableARG(z,x)} : 「 ∃ y : P r o o f ( y , z , x ) {\displaystyle \exists y:Proof(y,z,x)} 」である。すなわち、 z {\displaystyle z} をゲーデル数に持つ論理式を Q {\displaystyle Q} とするとき、 Q {\displaystyle Q} 中の変数に自然数 x {\displaystyle x} を代入した論理式 Q ( x ) {\displaystyle Q(x)} は証明可能である。
という論理式も作ることができる(上では P {\displaystyle P} は引数を持たず、 Q {\displaystyle Q} の引数は1つである)。
論理式 ¬ P r o v a b l e A R G ( x , x ) {\displaystyle \lnot ProvableARG(x,x)} のゲーデル数を m {\displaystyle m} とすると、 x {\displaystyle x} に m {\displaystyle m} を代入した論理式 ¬ P r o v a b l e A R G ( m , m ) {\displaystyle \lnot ProvableARG(m,m)} がゲーデル文となる(対角化)。
592-617, ISBN 978-0-674-32449-7, https://books.google.com/books?id=v4tBTBlU05sC&pg=PA592
Gödel, Kurt (2004), “On Formally Undecidable Propositions of the Principia Mathematica and Related Systems. I.”, in Davis, Martin, The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Dover Books on Mathematics, Courier Corporation, pp. 4-38, ISBN 978-0-486-43228-1, https://books.google.com/books?id=qW8x7sQ4JXgC&pg=PA4
自然数論の無矛盾性を
「自然数論において矛盾を証明できない」...(C)
と表す。このとき、自然数論による自然数論の無矛盾性証明とは、(C)が自然数論で証明できるということである。 (C)が自然数論で証明できれば、第一不完全定理での議論中の(B)より
「Gは証明できない」
と証明できる。しかし、
「Gは証明できない」
とはGと同値であるから、Gも証明されることとなり、そこから第一不完全性定理での議論中の(A)により、矛盾が証明される。
したがって自然数論が無矛盾、すなわち自然数論で矛盾が証明されないならば、そのこと自体も自然数論では証明できない(第二不完全性定理)。
前述のように自然数論は「命題に言及する命題」を取り扱うことはできないが、「命題のゲーデル数に言及する命題」なら取り扱うことができる。
A x i o m ( x ) {\displaystyle Axiom(x)} や M P ( x , y , z ) {\displaystyle MP(x,y,z)} などを組み合わせれば、
P r o o f ( y , z ) {\displaystyle Proof(y,z)} : z {\displaystyle z} をゲーデル数に持つ論理式を P {\displaystyle P} とするとき、 y {\displaystyle y} をゲーデル数に持つ論理式の列が論理式 P {\displaystyle P} の証明になっている。
という論理式も作ることができる。
さらに P r o o f {\displaystyle Proof} を「 ∃ {\displaystyle \exists } 」と組み合わせることで、
P r o v a b l e ( z ) {\displaystyle Provable(z)} : 「 ∃ y : P r o o f ( y , z ) {\displaystyle \exists y:Proof(y,z)} 」である。すなわち、 z {\displaystyle z} をゲーデル数に持つ論理式を P {\displaystyle P} とするとき論理式Pは証明可能である。
ゲーデルの定理は「帰納的公理化可能な自然数論を含む無矛盾理論」に対して示されているが、ここでは簡単の為、帰納的公理化可能な自然数論のみを扱う。一般の場合も同様。