「自然数論は無矛盾であるならば不完全である」、これがゲーデルの第一不完全性定理である。さらにゲーデルはもっと驚くべき定理を証明した。今自然数論の無矛盾性が証明されたと仮定しよう。このとき「この命題は証明可能でない」という命題が論理的に真であることが証明されたことになる。なぜなら他に選択の余地はないからである。しかしながら「この命題は証明可能でない」という命題が証明されたことは、「この命題は証明可能でない」という命題が証明可能であることに他ならない。証明可能でない命題が証明可能である。これは矛盾である。したがって自然数論の無矛盾性は証明できない。「自然数論の無矛盾性は証明可能でない」、これがゲーデルの第二不完全性定理である*1。
大筋は合ってるように思うのだが、にしても「なぜなら他に選択の余地はないからである」というフレーズは凄い。さも自明であるかのようだが、実のところ、これの証明が第二不完全性定理の肝なのではないか。
たしかに、ごく大雑把にいえば、第二不完全性定理の証明の流れは以下のようだ。まず、自然数論をT、ゲーデル文をg、証明可能性述語(可証性述語)をPrvとして
- T |- Con(T) → ¬Prv(g)
を何とか証明する。ここで
- T |- Con(T)
を仮定すると
- T |- ¬Prv(g)
が出てくる。ゲーデル文の特性から
- T |- g iff ¬Prv(g)
なので、
- T |- g
となるが、これは(Tが無矛盾なら)不整合なので、「無矛盾性を証明できる」という仮定がおかしい。よって自分の無矛盾性は証明できない(q.e.d)。
この構図は割とシンプルである。問題は、最初の条件文を証明するのが大変だということ。厳密な証明は、証明可能性述語に関する三つの有名な可導性条件を利用する。事典の項目なのでスペースが限られているのは理解できるが、せめて、この条件文が第一不完全性定理の形式化であることを明示すべきだったと思う。
*1:落合仁司「合理性」『事典哲学の木』p.371