量化子の順序
$ \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述語