論理学とは何か：鹿島亮「数理論理学」②ー不完全性定理、シークエント計算、直観主義論理ー

前の記事

第６章　不完全性定理

いよいよ不完全性定理です。

この説では証明の説明及びその意味について書いてあります。

不完全性定理の意味

第一不完全性定理

ざっくり詳細は省いて説明します。

自然演繹体系に自然数論の公理を追加した体系Basicにおいて、以下の２つは同時に成り立たない

• Basicは無矛盾である

• どんな論理式φについても、φと¬φのどちらかは証明できる

つまり、
Basicが無矛盾ならば、φと¬φがどちらも証明できない命題がある

第二不完全性定理

自然演繹上のペアノ算術の体系PAについて以下の条件は同時に成り立たない

• PAは無矛盾である

• 自分自身（PA)の無矛盾性を証明できる 

つまり、
PAが無矛盾ならば、PA上でその無矛盾性を証明できない。

第７章　命題論理

• 命題論理におけるトートロジーの扱い

• 選言標準形への書き換え

第８章　さまざまな証明体系

自然演繹と同じ証明能力を持つ以下２つを紹介する。

• ヒルベルト流体系

• シークエント計算

第９章　シークエント計算のカット除去定理

第１０章　直観主義論理

直観主義論理の説明
直観主義論理は背中律 (A or ¬A)が成り立たない論理体系
それについての特徴を解説

第１１章　クリプキ・モデルと中間論理

直観主義のセマンティクスとしてのｸﾘﾌﾟｷ・モデルの説明

以上