Logic Seminar

The Rules of Analysis for Quantified Formulae


限量式の分析に関する注意

『真理・証明・計算』37節で、分析の規則は限量式にまで拡張されるが、これのポイントはどこにあり、なにに特に注意すべきか?これについても、毎年理解不足の人たちが半数以上にのぼる。命題論理の場合は、分析の規則は「与えられた式がトートロジーかどうか、定理かどうか」を判定するための決定手続きにもなっていた。述語論理でも同じようなことが言えるのだろうか?まず、この問題意識をしっかり持ってもらいたい。答えは、何度も予告したように「ノー」なのである。これは、後にわかるように(わかる人にはわかるが、アホにはなかなかわからん)、有名なゲーデルの不完全性定理やチューリングの「停止問題」に関わりのある重要な結果である。

次に、分析手続きのもっと具体的な適用において、勝手な飛躍を導入しないよう注意してもらいたい。限量式については、自由変項をつかって、具体的な式になおして分析を続ける。このとき、式の形によって、使ってよい変項にかかる制限が異なってくる。極言すれば、まさにここが限量式の分析のエッセンスである。なんでこんな制限が要るのや?それを立ち止まって考えてもらいたい。

また、「いっときに一つの分析しかやらない」という鉄則もここでまた想起してもらいたい。自由変項一つにつき分析は一回と数える。一気に二つも三つも自由変項を導入して平気な人は、「分析」の精神がまったくわかってないので、デカルトに戻って復習してもらいたい(というか、出直してきてつかーさい)。

この拡張された分析をマスターすれば、与えられた式を反証するモデル作りは、ほぼ機械的にできるようになる。この「ほぼ」が曲者!

では、次の式は妥当か妥当でないのか?B(y) のなかにx は自由変項として現れないものとする。(A(x) やB(y) はシェマであって一項述語とは限らないことに注意。)

(1) (∃xA(x) ⊃∀yB(y))⊃∃x(A(x)⊃∀yB(y))

(2) ∃x(A(x)⊃∀yB(y))⊃(∃xA(x) ⊃∀yB(y))


Uchii, S. (1989) 『真理・証明・計算』ミネルヴァ書房、1989。


Last modified Sept. 30, 2003. (c) Soshichi Uchii