完全な理論の作り方

無矛盾な一階の理論が以下の二条件をみたすとする。

1. 任意の閉原子論理式に対して、 または が成り立つ。
2. の形の任意の閉論理式に対して、ある閉項が存在して、 が成り立つ。

このとき、は完全な理論である。なぜならば、任意の閉論理式に対して、条件2を繰り返し適用することで、 をみたし量化子を含まない を得る。 に出現する各原子論理式に対し、 ならば真を、 ならば偽を割り当てる。その下での の付値が真ならば が成り立ち、偽ならば が成り立つことが、命題論理の完全性定理から導かれる。

ところで、任意の無矛盾な一階の理論に対して、そのHenkin拡大は条件1,2をみたす無矛盾な理論である。すなわち、任意の無矛盾な一階の理論に対して、の拡大が存在して、は完全かつ無矛盾である。ただし、理論の拡大において定数記号の追加は許す。

PAも一階の理論なので、以上の議論が適用できる。すなわち、PAが無矛盾ならば、PAの完全かつ無矛盾な拡大が存在する。

命題論理は一階述語論理のサブセットであることから、以上の議論は命題論理の理論にも適用できる。命題論理において、条件2は自明に成り立っている。命題論理の原子論理式は の形のものだけなので、条件1は次のように書き換えられる。

1. 任意の命題変数に対して、 または が成り立つ。

つまり、この辺の議論はPAと命題論理でパラレルに展開できるものであって、PAと命題論理の違いをことさらに際立たせるものではないということ。

蛇足： id:wd0:20111214:a のつづきでもあるが、独立した記事として読めるように書いたつもり。