量化子の順序は可換ではない

順方向。 $\mathcal{M} \models_s \exists y\, \forall x\, R(x,y)$ を仮定する。$\exists$ に対する意味論的節により、$\mathcal{M} \models_s \exists y\, \varphi \iff \text{there is } d \in M \text{ with } \mathcal{M} \models_{s[y \mapsto d]} \varphi$。これをここに適用すると、ある $d_0 \in M$ が存在して $\mathcal{M} \models_{s[y \mapsto d_0]} \forall x\, R(x,y)$。

これに $\forall$ に対する節を適用すると、$\mathcal{M} \models_{s[y \mapsto d_0][x \mapsto a]} R(x,y)$ がすべての $a \in M$ について成り立つ。なぜなら $\forall x$ は後でどの $a$ を選ぼうと $M$ 全体にわたるからである。

ここで $\forall x\, \exists y\, R(x,y)$ を確認するため任意の $a \in M$ を固定する。前段落から $x \mapsto a$ を取ると $\mathcal{M} \models_{s[y \mapsto d_0][x \mapsto a]} R(x,y)$ が得られ、これは $x \mapsto a$ のもとで $\exists y\, R(x,y)$ に対する証拠として $d_0$ 自身を示している。したがって $\mathcal{M} \models_{s[x \mapsto a]} \exists y\, R(x,y)$。

$a \in M$ は任意だったので、$\mathcal{M} \models_{s[x \mapsto a]} \exists y\, R(x,y)$ はすべての $a$ について成り立ち、これはまさに $\mathcal{M} \models_s \forall x\, \exists y\, R(x,y)$ の意味論的節である。これで $\exists y\, \forall x\, R(x,y) \Rightarrow \forall x\, \exists y\, R(x,y)$ が証明された。

逆は成り立たない:反例。 $\mathcal{M}$ の領域を $M = \mathbb{Z}$(整数)とし、$R(x,y)$ を「$x < y$」と解釈する。このとき $\forall x\, \exists y\, R(x,y)$ は真である:任意の整数 $x$ に対して $y = x+1$ を取れば $x < y$。しかし $\exists y\, \forall x\, R(x,y)$ は偽である:これはすべての整数 $x$ より大きい単一の整数 $y$ を要求するが、そのような最大の整数は存在しない(どの候補 $y$ についても、整数 $y+1$ は $y+1 < y$ に違反する)。よって $\forall x\, \exists y\, R(x,y)$ は成り立つが $\exists y\, \forall x\, R(x,y)$ は成り立たず、逆の含意が一般には偽であることが示された。