述語論理 ②

Prop & Proof

含意の同値変形
$$ A\Rightarrow B\ \equiv\ \neg A\lor B $$
より、
$$ P(x)\Rightarrow \neg Q(x)\ \equiv\ \neg P(x)\lor \neg Q(x) $$
である。また、命題論理のド・モルガンの法則
$$ \neg(A\land B)\ \equiv\ \neg A\lor \neg B $$
より、
$$ \neg P(x)\lor \neg Q(x)\ \equiv\ \neg\bigl(P(x)\land Q(x)\bigr) $$
が成り立つ。さらに、量化記号の否定の規則
$$ \forall x\,\neg A(x)\ \equiv\ \neg\exists x\,A(x) $$
を用いると、次の同値変形を得る。
$$ \begin{align} \forall x \bigl(P(x)\Rightarrow \neg Q(x)\bigr) &\equiv \forall x \bigl(\neg P(x)\lor \neg Q(x)\bigr)\\ &\equiv \forall x \neg\bigl(P(x)\land Q(x)\bigr)\\ &\equiv \neg\exists x \bigl(P(x)\land Q(x)\bigr) \end{align} $$
従って
$$ \forall x \bigl(P(x)\Rightarrow \neg Q(x)\bigr)\ \equiv\ \neg\Bigl(\exists x \bigl(P(x)\land Q(x)\bigr)\Bigr) $$
が成り立つ。
$$ \Box$$

$\forall x\in S,\ P(x)$ が真であると仮定する。
全称命題の定義より、この仮定は、任意の $x\in S$ に対して $P(x)$ が真であることを意味する。
ここで $a\in S$ は $S$ の元であるから、上の「任意の $x\in S$」の中に $x=a$ を含む。従って $P(a)$ は真である。
$ $
よって
$$ \forall x\in S,\ P(x)\ \Rightarrow\ P(a) $$
が成り立つ。
$$ \Box$$

$P(a)$ が真であると仮定する。また $a\in S$ である。
ここで $x:=a$ とおくと $x\in S$ であり、仮定より $P(x)=P(a)$ は真である。
$ $
従って「ある $x\in S$ が存在して $P(x)$ が真である」が成り立つ。すなわち
$$ \exists x\in S\ \text{s.t.}\ P(x) $$
は真である。
$ $
以上より
$$ P(a)\ \Rightarrow\ \exists x\in S\ \text{s.t.}\ P(x) $$
が成り立つ。
$$ \Box$$

$S$ は空集合でないので、ある元 $a\in S$ を$1$つとることができる。$\forall x\in S,\ P(x)$ が真であると仮定する。
全称命題の定義より、任意の $x\in S$ について $P(x)$ が真である。特に $a\in S$ であるから $P(a)$ は真である。
$ $
ここで $x:=a$ とおけば $x\in S$ かつ $P(x)$ は真である。
従って、ある $x\in S$ が存在して $P(x)$ が成り立つ。すなわち $\exists x\in S\ \text{s.t.}\ P(x)$ は真である。
$ $
以上より
$$ \bigl(\forall x\in S,\ P(x)\bigr)\ \Rightarrow\ \exists x\in S\ \text{s.t.}\ P(x) $$
が成り立つ。
$$ \Box$$