証明論
数学で日常的に行われている「非形式的」証明は、証明論で言う「形式的」証明とは異なる。しかしながら、それは形式的証明の高度に抽象化されたスケッチのようなもので、専門家が十分な時間と忍耐を持っていれば、非形式的証明から形式的証明を適切に再構築できるようなものである場合が多い。比喩的に言えば、そのような場合に完全な形式的証明を書くことは、機械語でプログラミングをするようなものである。
現代では、形式的証明は一般に計算機支援証明を補助としてコンピュータを使って構築される。また、その証明がコンピュータで自動的に検証される点も重要である。形式的証明の検証は簡単だが、証明そのものをコンピュータが構築すること(自動定理証明)は一般には非常に困難である。一方、数学における非形式的証明は査読による検証に何週間も要し、それでもまだ誤りが含まれていることが多い。
主な証明計算は以下の3つである。
ヒルベルト計算
自然演繹計算
シークエント計算
これらはいずれも、命題論理や述語論理(古典論理または直観論理)、任意の様相論理、多くの部分構造論理(適切さの論理や線型論理)の完全かつ公理的な定式化を可能とする。実際、これらで表せない論理体系は稀である。
先に述べたように、ヒルベルト・プログラムは証明の形式理論の研究に拍車をかけた。このプログラムの中心となる考え方は、数学者が必要とするあらゆる洗練された形式理論の一貫性を有限項で証明できたとき、それらの理論を超数学的論証を使って基礎付けることができ、それらの純粋に汎用の表明(より技術的に言えば、それらの証明可能な算術的階層 Π 1 0 {\displaystyle \Pi _{1}^{0}} )が有限項的に真であることを示す。そのように基礎付けられたとき、有限項的でない定理群は観念的実体の擬似的規定であるとみなすことができ、無視することができる。
このプログラムの誤りはクルト・ゲーデルの不完全性定理で明らかとなった。不完全性定理は、何らかの数学的真理を表現できる程度に強力な任意のω無矛盾な理論は、ゲーデルの定式化では Π 1 0 {\displaystyle \Pi _{1}^{0}} となるそれ自体の一貫性(無矛盾性)を証明できないことを示した。
その後、さらに研究は進み、以下のような成果が得られている。
ゲーデルの結果の洗練が行われ、特にジョン・バークリー・ロッサーは、ω無矛盾性ではなく単純な無矛盾性で済むようにした。
ゲーデルの業績の核心部分を様相言語で公理化した証明可能性論理 (provability logic)
アラン・チューリングとソロモン・フェファーマンによる理論の超限的反復
比較的新しい 自己検証理論 の発見(自身を語ることができるほど強力な体系だが、ゲーデルの証明不可能性の論証の鍵となった対角線論法を適用できるほど強力でない理論体系)
証明論(しょうめいろん、英語: proof theory)は、数理論理学の一分野であり、証明を数学的対象として形式的に表し、それに数学的解析を施す。