ゲーデルの不完全性定理
また、選択公理もZF(ZFCに含まれる公理から選択公理を除いたもの)では証明も否定の証明もできない。これらの結果は不完全性定理を必要としない。1940年、ゲーデルはこれらの命題が何れも ZF または ZFC 集合論では否定を証明できないことを証明した。1960年代、コーエンはこれらがいずれも ZF から証明できず、また連続体仮説が ZFC から証明できないことを証明した。
マチャセビッチによるヒルベルトの第10問題の解決により、決定不能な命題の例が得られる。そのような例はディオファントス方程式の外側に存在量化子を幾つか並べた形として得られる。すなわち不完全性定理の前提条件を満たす形式的体系において、解の存在が証明も反証もできないようなディオファントス方程式が存在する。
1973年、群論におけるホワイトヘッドの問題(英語版)が標準的な集合論では決定不能であることが示された。
1977年、パリスとハーリントンは、ラムゼーの定理の一種であるパリス=ハーリントンの定理が、一階算術の公理体系であるペアノ算術の下では決定不能だが、より大きな二階算術の体系では証明できることを証明した。
Franzén, Torkel (2008年). “Torkel Franzén”. Luleå University of Technology (Department of Computer Science and Electrical Engineering). 2008年10月18日時点のオリジナルよりアーカイブ。2021年1月11日閲覧。