ゲーデルの不完全性定理
カービーとパリスは後にグッドスタインの定理(自然数の数列に関する命題であり、パリス・ハーリントンの原理よりもいくらか易しい)がペアノ算術では決定不能であることを示した。
計算機科学で応用される Kruskal の木定理(英語版)はペアノ算術では決定不能だが集合論では証明できる。実際、Kruskalの木定理(またはその有限版)は、可述主義(英語版)と呼ばれる数学的哲学に基づいて構築されたもっと強い体系の下でも決定不能である。これに関連し、更に一般的な graph minors 定理(英語版)(2003年)は計算複雑性理論に影響する。
グレゴリー・チャイティンはアルゴリズム情報理論における決定不能命題を発見し、その状況下で新たな不完全性定理を得た。チャイティンの定理によると、十分な算術を表現可能ないかなる理論においても、どのような数であっても c {\displaystyle c} よりも大きなコルモゴロフ複雑性を有することがその理論上では証明できないような、上限 c {\displaystyle c} が存在する。ゲーデルの定理が嘘つきのパラドックスと関係しているのに対し、チャイティンの結果はベリーのパラドックスに関係している。
第一不完全性定理の拡張として、証明の定義に、命題の証明より小さな、否定命題の証明が存在しないという性質を追加した上で、前提のω無矛盾性を無矛盾性に弱めた定理がジョン・バークリー・ロッサー (1936年) によって示された。この事実はω矛盾した算術理論を考える場合などにおいて重要となる。なお算術を内包する真である体系(自然数の標準モデルで真である公理に基づく体系)はω無矛盾なので、第1不完全性定理は原型のままでも適用できる。今日ではこちらの無矛盾性のみを仮定する強い定理もゲーデルの不完全性定理と呼ばれるが、単にロッサーの定理、ゲーデル・ロッサーの定理などと呼ばれることもある。
第二不完全性定理に関しては、ゲーデルによる証明の定義に代えて、ロッサーによる上記の証明の定義を用いれば、体系自身の無矛盾性が証明できることが、クライゼル (1960) によって指摘されている。2つの証明の定義の同値性は体系内では証明できないため、第2不完全性定理とは矛盾しない。
レオン・ヘンキンは、対角化により「Hは証明できる」と同値となる命題H(ヘンキン文)を構成し、その証明可能性に関する問題を1952年に提起した。この問題は3年後の1955年に、マーティン・レープによって解かれた。彼は、「Hの証明が存在すればHである」が証明可能であれば、Hもまた証明可能であることを示した(レープの定理)。Hに矛盾を代入すれば、レープの定理から第二不完全性定理が示せる。
m {\displaystyle m} をゲーデル数に持つ論理式に m {\displaystyle m} を代入したものは n p m m {\displaystyle npmm} であるから
¬ P r o v a b l e A R G ( m , m ) ⇔ ¬ P r o v a b l e ( n p m m ) {\displaystyle \lnot ProvableARG(m,m)\Leftrightarrow \lnot Provable(npmm)}
が証明可能である。したがって、
¬ P r o v a b l e ( n p m m ) {\displaystyle \lnot Provable(npmm)}
は証明可能である。
したがって P r o v a b l e ( n p m m ) {\displaystyle Provable(npmm)} および ¬ P r o v a b l e ( n p m m ) {\displaystyle \lnot Provable(npmm)} が証明され、これは矛盾であるが、これは自然数論が無矛盾であるという仮定に反する。