数学基礎論講義をこっそり読む
こっそり読んでいます。まだまだ最初の方の命題論理のコンパクト性のところなのですが、いきなり悩んでました...
こちらのテキストでは、前提のある場合の命題論理の一般化された完全性定理『 』を先に証明して、そこからコンパクト性定理『 が充足可能 ⇔ 任意の有限集合が充足可能』を導いています。
左向き矢印の証明は、背理法により
1) が充足可能でない
2) よって任意の命題、特にについて が成立する
3) 完全性定理により
4) 証明は有限列なので部分集合が存在して
5) 再び完全性定理により これは前提に反する。
というステップを踏むのですが、疑問点は 2)にあります。まず、テキストp.21のの定義においては、『の命題すべてにTを割り当てる任意の真理値関数が命題Aに値Tを割り当てるとき』そのように書くとあり、もともとが充足不可能なときでも、が成立すると規約するのかという点がまず不明確です。しかし、もちろんこれはこれでOKなのですが、一般化された完全性定理の証明の左向き矢印の証明(p.22)において 『と書き直すだけでよい』とある点がすこし問題になります。この場合 が無矛盾でないとその後の構成がうまくいきません。ただ、補題2.5があるのでこの場合は直接 が出て証明が終ります。ちょっと気持ちがわるいのはが充足不可能かつ が無矛盾でないという場合を一応考慮する必要があるところで、この場合は証明での構成が進んで、を充足する真理値関数ができ、結局矛盾するためそういう場合はないということになります。なんかねじれている感じが…
すっきりさせる方法としては、テキストの完全性の証明をまねすると、
『は無矛盾である⇔は充足可能である』
がすなおに証明できるので、その両辺の否定形の
『は矛盾する⇔は充足不可能である』
を に適用すると、一般化された完全性定理が得られ、
『は矛盾する⇔ある有限集合は矛盾する』
と組み合わせると
『は充足不可能 ⇔ある有限集合は充足不可能』が得られ、これの両辺を否定形に直すと、コンパクト性定理が得られます。