量化子の順序
$ \forall x\;\exist y\; Aと$ \exist y\;\forall x\; Aの捉え方のイメージ
$ \mathbb{N}から、$ xを選択するマンと、$ yを選択するマン(自分)がいるとする
両者が順番に何かを選択して、最終的に$ Aを成立させたい
どちらのケースでも$ y目線に立ってみるmrsekut.icon
$ \forall x\;\exist y\; Aの場合
相手$ xは何を出してもいい
自分はそこから適合する$ yを出せばいい
$ \exist y\;\forall x\; Aの場合
先に自分が出すが、相手が何を出しても良くなるような$ yを選択して出さないといけない
$ y目線だと、こちらのほうが難しい条件になる
命題の例
任意の実数$ xに対して、$ xy=1となる実数$ yが存在する
$ (\forall x\in\mathbb{R})(\exist y\in\mathbb{R})(xy=1)
e.g. $ (x,y)=(1,1),(2,\frac{1}{2})
実数内の全ての要素一つ一つの$ xに対し、何かしらの実数$ yが存在することを言っている
整数の中に、全ての整数$ nについて$ n+a=nとなるような整数$ aが存在する
$ (\exist a\in\mathbb{Z})(\forall n\in\mathbb{Z})(n+a=n)
e.g. $ a =0
ある$ aがあったとき、$ aに関係なく全ての整数$ nに対し成り立つ
$ (\forall a)(\forall n)でないのは、全ての$ aに対しては成り立たないからmrsekut.icon
論理式の結合
以下の2つがあるとする
$ A(x)=(\exist y_1)(\forall y_2)(B(x,y_1,y_2))
$ A'(x)=(\exist z_1)(\forall z_2)(B'(x,z_1,z_2))
このとき$ A(x)\land A'(x)は以下のいずれも同じである
①$ (\exist y_1)(\forall y_2)(\exist z_1)(\forall z_2)(B(x,y_1,y_2)\land B'(x,z_1,z_2))
②$ (\exist z_1)(\forall z_2)(\exist y_1)(\forall y_2)(B(x,y_1,y_2)\land B'(x,z_1,z_2))
③$ (\exist y_1)(\exist z_1)(\forall y_2)(\forall z_2)(B(x,y_1,y_2)\land B'(x,z_1,z_2))
①②は$ \Sigma_4述語
③は$ \Sigma_2述語
∀∃ に慣れるための練習として、
P(x, y) = 「x は y を愛する」
とおいて、
(1) ∀x ∀y P(x, y)
(2) ∀x ∃y P(x, y)
(3) ∃y ∀x P(x, y)
(4) ∃x ∀y P(x, y)
(5) ∀y ∃x P(x, y)
(6) ∃x ∃y P(x, y)
のそれぞれを「日本語訳」して見るといいと思います。全部違った意味になります。
(1) ∀x ∀y P(x, y)
すべての人は互いを愛している
(2) ∀x ∃y P(x, y)
すべての人には愛する人がいる
(3) ∃y ∀x P(x, y)
誰にでも愛される人がいる
(4) ∃x ∀y P(x, y)
全ての人のことを愛している人がいる
(5) ∀y ∃x P(x, y)
全ての人は誰かから愛されている
(6) ∃x ∃y P(x, y)
(誰か一組でも)愛している人がいる