数理論理学

授業全体の流れ、この科目で何を学ぶかについて説明する。

言語・項・論理式の定義と例を説明する。

一階述語論理の証明体系の例としてNKを導入し、推論規則や導出図について説明する。

NKにおける定理の証明の導出図をいくつか見る。

構造が論理式を充足することの定義と、論理的妥当性の定義を述べる。

NKで証明できる文は論理的に妥当であるという、一階述語論理の健全性定理を証明する。

論理的に妥当な文はNKで証明できるという、一階述語論理の完全性定理について、証明を行う。

論理的に妥当な文はNKで証明できるという、一階述語論理の完全性定理について、証明を行う。

ゲーデルの不完全性定理の意味するところについて、正確に説明する。特に、ゲーデルの不完全性定理とは「何でないのか」を理解する。

一階ペアノ算術の公理系PAについて、特に数学的帰納法の公理について解説する。

論理式や証明などの記号列をひとつの自然数で表す手法であるゲーデル数について解説する。

計算可能性理論について、概略を述べる。

計算可能関数がPAで表現できるという表現定理と、その帰結としてPAの述語は不動点を持つという対角化補題が得られることを見る。

一定の条件をみたす公理系は不完全であるという第一不完全性定理を証明する。

一定の条件をみたす公理系は自己の無矛盾性を証明できないという第二不完全性定理について、証明の概略を述べる。