量化子(全称命題・存在命題)の順序変更

by nomura · 2024年6月14日

量化子(全称命題・存在命題)の順序変更
量化子(全称命題・存在命題)は次のように順序変更できる。

(1)

\[ \forall x\forall y,P\left(x,y\right)\Leftrightarrow\forall y\forall x,P\left(x,y\right) \]

(2)

\[ \exists x\exists y,P\left(x,y\right)\Leftrightarrow\exists y\exists x,P\left(x,y\right) \]

(3)

\[ \exists x\forall y,P\left(x,y\right)\Rightarrow\forall y\exists x,P\left(x,y\right) \] 逆は一般的に成り立たない。

(3)の補足
\(\exists x\forall y,P\left(x,y\right)\)はある\(x\)が存在し、(\(x\)に依らない)任意の\(y\)について\(P\left(x,y\right)\)が成り立つということである。
\(\forall y\exists x,P\left(x,y\right)\)は任意の\(y\)に対し、(\(y\)に依って変えてもよい)ある\(x_{y}\)が存在して\(P\left(x,y\right)\)が成り立つということである。
これより、\(\exists x\forall y,P\left(x,y\right)\)が成り立てば条件の緩い\(\forall y\exists x,P\left(x,y\right)\)は成り立つということである。

(1)

\begin{align*} \forall x\forall y,P\left(x,y\right) & \Leftrightarrow\bigwedge_{x\in X}\bigwedge_{y\in Y}P\left(x,y\right)\\ & \Leftrightarrow\bigwedge_{y\in Y}\bigwedge_{x\in X}P\left(x,y\right)\\ & \Leftrightarrow\forall y\forall x,P\left(x,y\right) \end{align*}

(2)

\begin{align*} \exists x\exists y,P\left(x,y\right) & \Leftrightarrow\bigvee_{x\in X}\bigvee_{y\in Y}P\left(x,y\right)\\ & \Leftrightarrow\bigvee_{y\in Y}\bigvee_{x\in X}P\left(x,y\right)\\ & \Leftrightarrow\exists y\exists x,P\left(x,y\right) \end{align*}

(3)

\(\Rightarrow\)

\begin{align*} \exists x\in X,\forall y\in Y,P\left(x,y\right) & \Leftrightarrow\exists x\in X,\bigwedge_{y\in Y}P\left(x,y\right)\\ & \Leftrightarrow\bigvee_{x\in X}\bigwedge_{y\in Y}P\left(x,y\right)\\ & \Rightarrow\bigwedge_{y\in Y}\bigvee_{x\in X}P\left(x,y\right)\\ & \Leftrightarrow\forall y\in Y,\exists x\in X,P\left(x,y\right) \end{align*}

逆は一般的に成り立たない

反例で示す。
\[ \exists x\in\left\{ 0,1\right\} ,\forall y\in\left\{ 0,-1\right\} ,x+y=0\nLeftarrow\forall y\in\left\{ 0,-1\right\} ,\exists x\in\left\{ 0,1\right\} ,x+y=0 \] 左辺は偽、右辺は真となる。
故に逆は一般的に成り立たない。