2つの束縛記号を含む論理式について

質問

数学の考え方『数学と論理』のp.57に、
∃x∀yA(x,y) ⇒ ∀x∃yA(x,y)
が証明可能である、とありますが、どうしてもわかりません。
証明は、
A(a,b) ⇒ A(a,b)
A(a,b) ⇒ ∃yA(a,y)
∀yA(a,y) ⇒ ∃yA(a,y)
∃x∀yA(x,y) ⇒ ∃yA(a,y)
∃x∀yA(x,y) ⇒ ∀x∃yA(x,y)
となっていますが、なぜ3段めから4段めが導けるのかがわかりません。
ご教授お願いします。

回答No.1

noname#52504 · ベストアンサー

なかなかショッキングな内容のご質問でしたので、つい現物を取り寄せてしまいました。
確かにそのように書いてありますねぇ…。

結論から言いますと、おそらくマチガイであろうと思います。

以下、既にご賢察のことと思いますが、
　３つ目の推論（３段目から４段目への推論）で、左辺に特称記号を導入していますが、
　p.49では、左辺に特称記号を導入する際、変数は固有変数であって下式にあってはならないとあります。
　一方、３つめの推論は下式右辺にaが残るので、この条件を満たしません。

問題の式、
　●∃x∀yＡ(x,y) ⇒ ∀x∃yＡ(x,y)
について、

例えば、対象が｛1,2,3,4,…｝で、Ａ(x,y)≡x×y＝y　の場合、
つまり対象が(0を含まない)自然数であり、xとyの積がyであるという意味に解釈します。
∃x∀yＡ(x,y) は真ですが、∀x∃yＡ(x,y)は偽です。

『すべての人を憎んでいる人がいるとしても、全ての人が誰かを憎んでいるとは限らない。』
というようなことです。少なくとも私は（自分も含め）誰も憎んではいません。

また、反対の方向、
　■∀x∃yＡ(x,y) ⇒ ∃x∀yＡ(x,y)
について挙げられている反例ですが、
∀x∃yＡ(x,y)　を　「すべての人には父親がいる」　と読むのであれば、
Ａ(x,y)は「xはyを父親に持つ」ということですから、
∃x∀yＡ(x,y)　は　「すべての人を父親に持つ人がいる」　とすべきであって、
「すべての人の父親がいる」と読むのは無茶です。

おそらく、問題の式は、
　○∃x∀yＡ(x,y) ⇒ ∀y∃xＡ(x,y)　
と間違えたものと思われます。

こちらは本当に証明可能であり、有用であり、交換律の直後に記述するにふさわしい式です。

また、この場合、反対の方向
　□∀y∃xＡ(x,y) ⇒ ∃x∀yＡ(x,y)
はやはり証明不可能であって、挙げられている反例についても、
　・Ａ(x,y)≡x≠y　としている部分についてはxとyは交換可能なのでそのまま使える。
　・Ａ(x,y)≡「xはyの父親である」と解釈すれば、むしろこの式にこそふさわしい。
ので、式と証明の部分だけ入れ替えれば、p.57全体の文脈が通ります。

学生・一般向けの書物では、全体の構成はともかく細かい記述については、
「著者」として名前が出ているセンセイが直接自分で書くとは限らないようですから、こういうこともままあります。

立場上「自信なし」としておきますが、１週間回答がつかなかったことと併せてご参考ください。

お礼

> 結論から言いますと、おそらくマチガイであろうと思います。
わざわざ書籍を参照して、懇切丁寧なご回答ありがとうございます。
該当の記述は、間違いだったのですね。

> おそらく、問題の式は、
> 　○∃x∀yＡ(x,y) ⇒ ∀y∃xＡ(x,y)　
> と間違えたものと思われます。
これは、「万能な戦術があれば、相手のどんな戦術にも対抗できる」みたいな感じですね。
max_x min_y f(x,y) ≦ min_y max_x f(x,y) とanalogousな形で馴染みやすいです。

> 学生・一般向けの書物では、全体の構成はともかく細かい記述については、
> 「著者」として名前が出ているセンセイが直接自分で書くとは限らないようですから、こういうこともままあります。
書いてあることを鵜呑みにせず、注意して読むようにしたいと思います。
お忙しい中、ありがとうございました。