論理学の練習問題 述語論理

量化子の∀(全ての)と∃(存在する)に関し、∀x∃yf(x,y) と ∃y∀xf(x,y) の違いについて。


∀x∃yf(x,y) は、日本語の文で表すと、全てのxについてf(x,y)であるyが存在する、
となり、
∃y∀xf(x,y) は、同様に、あるyが存在し全てのxに対してf(x,y)である、
となる。
具体例で表すと、f(x,y)を、xとyは友達である(x,yとも定義域は人間とする)、という関係を表すものとしてもっと日常的な文にしてみると、
∀x∃yf(x,y) は、誰にでも友達がいる、
となり、
∃y∀xf(x,y) は、誰とでも友達である人がいる、
となる。
図示すると下図のようになる。

ここで、∃y∀xf(x,y)→∀x∃yf(x,y) であることも分るだろう。各xと対になるyが同一のものであっても構わないからである。xとyが友達である、という例でいえば、誰とでとも友達である人が一人いれば、誰でも友達を持つことになるからである。
直感的にはそれでいいのだが、詳しい証明はあとで書く予定。