量化子の順序
量化子の順序
\forall x\;\exist y\; Aと\exist y\;\forall x\; Aの捉え方のイメージ
\mathbb{N}から、xを選択するマンと、yを選択するマン(自分)がいるとする
両者が順番に何かを選択して、最終的にAを成立させたい
どちらのケースでもy目線に立ってみる
\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に対しては成り立たないから
論理式の結合
以下の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述語
となるので、一番狭い③を採用することで、Σn述語#5fac08e11982700000a66a26らへんの定理が成り立つ
>∀∃ に慣れるための練習として、
>
>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)
(誰か一組でも)愛している人がいる