述語論理 ③

Prop & Proof

1. $S=\varnothing$の場合を示す。
   定義より、全称命題$\forall x\in S,\ R(x)$は「任意の$x$について、もし$x$が$S$に属するならば$R(x)$が成り立つ」という意味である。
   したがって形式的には
   $$ \forall x\ \bigl(x\in S\Rightarrow R(x)\bigr) $$
   と書ける。ここで$S=\varnothing$のとき、任意の$x$に対して$x\in S$は偽である。
   一般に含意$A\Rightarrow B$は前件$A$が偽であるとき常に真である(空虚な真)。よって、全称命題$\forall x\ \bigl(x\in S\Rightarrow R(x)\bigr)$は真である。
   $ $
   今回の場合、左辺は
   $$ \forall x\in\varnothing,\ \bigl(P(x)\land Q(x)\bigr) $$
   である。ここで$S=\varnothing$かつ$R(x):=P(x)\land Q(x)$とおくと、
   $$ \forall x\in\varnothing,\ \bigl(P(x)\land Q(x)\bigr) \ \equiv\ \forall x\ \bigl(x\in\varnothing\Rightarrow (P(x)\land Q(x))\bigr) $$
   となる。$S=\varnothing$であるから任意の$x$に対して$x\in\varnothing$は偽である。よって任意の$x$について
   $$ x\in\varnothing\Rightarrow (P(x)\land Q(x)) $$
   は真である。従って
   $$ \forall x\ \bigl(x\in\varnothing\Rightarrow (P(x)\land Q(x))\bigr) $$
   は真であり、よって左辺
   $$ \forall x\in\varnothing,\ \bigl(P(x)\land Q(x)\bigr) $$
   は真である。
   $ $
   右辺は
   $$ \bigl(\forall x\in\varnothing,\ P(x)\bigr)\land\bigl(\forall x\in\varnothing,\ Q(x)\bigr) $$
   である。各項はそれぞれ
   $$ \forall x\in\varnothing,\ P(x)\ \equiv\ \forall x\ \bigl(x\in\varnothing\Rightarrow P(x)\bigr) $$
   $$ \forall x\in\varnothing,\ Q(x)\ \equiv\ \forall x\ \bigl(x\in\varnothing\Rightarrow Q(x)\bigr) $$
   と書ける。いずれも任意の$x$に対して前件$x\in\varnothing$が偽であるから、任意の$x$について含意は真となる。従って
   $$ \forall x\in\varnothing,\ P(x)\ \text{は真},\qquad \forall x\in\varnothing,\ Q(x)\ \text{も真} $$
   である。よって真なる命題の連言もまた真であるので、右辺も真である。
   $ $
   以上より、$S=\varnothing$のとき左辺も右辺も真であるから、同値は真である。
   $$ $$
2. $S\neq\varnothing$の場合を示す。
   (i) まず
   $$ \forall x\in S,\ \bigl(P(x)\land Q(x)\bigr)\ \Rightarrow\ \bigl(\forall x\in S,\ P(x)\bigr)\land\bigl(\forall x\in S,\ Q(x)\bigr) $$
   を示す。
   $ $
   $\forall x\in S,\ (P(x)\land Q(x))$ が真であるとする。すると、任意の $a\in S$ について $P(a)\land Q(a)$ が真である。
   よって連言より、任意の $a\in S$ について $P(a)$ が真であり、かつ任意の $a\in S$ について $Q(a)$ が真である。
   従って $\forall x\in S,\ P(x)$ は真であり，$\forall x\in S,\ Q(x)$ も真であるから、
   その両方の連言
   $$ \bigl(\forall x\in S,\ P(x)\bigr)\land\bigl(\forall x\in S,\ Q(x)\bigr) $$
   は真である。
   $ $
   (ii) 次に
   $$ \bigl(\forall x\in S,\ P(x)\bigr)\land\bigl(\forall x\in S,\ Q(x)\bigr)\ \Rightarrow\ \forall x\in S,\ \bigl(P(x)\land Q(x)\bigr) $$
   を示す。
   $ $
   $\bigl(\forall x\in S,\ P(x)\bigr)\land\bigl(\forall x\in S,\ Q(x)\bigr)$ が真であるとする。
   すると、任意の $a\in S$ について $P(a)$ は真であり、任意の $a\in S$ について $Q(a)$ も真である。
   従って任意の $a\in S$ について $P(a)\land Q(a)$ は真であるから、$\forall x\in S,\ (P(x)\land Q(x))$ は真である。
   $ $
   (i)と(ii)より両方向の含意が成り立つので主張が成立する。
   $$ \Box$$

1. $S=\varnothing$の場合を示す。
   まず左辺
   $$ \exists x\in\varnothing\ \text{s.t.}\ \bigl(P(x)\lor Q(x)\bigr) $$
   を考える。これは「ある $x\in\varnothing$ が存在して $P(x)\lor Q(x)$ が真である」という主張である。
   しかし $\varnothing$ には元が存在しないから、そのような $x$ は存在しない。
   従って
   $$ \exists x\in\varnothing\ \text{s.t.}\ \bigl(P(x)\lor Q(x)\bigr) $$
   は偽である。
   $ $
   次に右辺
   $$ \bigl(\exists x\in\varnothing\ \text{s.t.}\ P(x)\bigr)\lor\bigl(\exists x\in\varnothing\ \text{s.t.}\ Q(x)\bigr) $$
   を考える。ここで
   $$ \exists x\in\varnothing\ \text{s.t.}\ P(x) $$
   は「ある $x\in\varnothing$ が存在して $P(x)$ が真である」という主張であるが、$\varnothing$ には元が存在しないので偽である。
   同様に
   $$ \exists x\in\varnothing\ \text{s.t.}\ Q(x) $$
   も偽である。従って右辺は偽 $\lor$ 偽であり、偽となる。
   $ $
   以上より、$S=\varnothing$のとき左辺も右辺も偽であるから、同値
   $$ \exists x\in\varnothing\ \text{s.t.}\ \bigl(P(x)\lor Q(x)\bigr)\ \Leftrightarrow\ \bigl(\exists x\in\varnothing\ \text{s.t.}\ P(x)\bigr)\lor\bigl(\exists x\in\varnothing\ \text{s.t.}\ Q(x)\bigr) $$
   は真である。
   $$ $$
2. $S\neq\varnothing$の場合を示す。
   (i) まずは、
   $$ \exists x\in S\ \text{s.t.}\ \bigl(P(x)\lor Q(x)\bigr)\ \Rightarrow\ \bigl(\exists x\in S\ \text{s.t.}\ P(x)\bigr)\lor\bigl(\exists x\in S\ \text{s.t.}\ Q(x)\bigr) $$
   を示す。$\exists x\in S\ \text{s.t.}\ (P(x)\lor Q(x))$ が真であるとする。するとある $a\in S$ が存在して $P(a)\lor Q(a)$ が真である。
   $ $
   従って $P(a)$ が真であるか、または $Q(a)$ が真である。$P(a)$ が真である場合、ある $x\in S$ が存在して $P(x)$ が真であるから，
   $\exists x\in S\ \text{s.t.}\ P(x)$ は真である。$Q(a)$ が真である場合も同様に、$\exists x\in S\ \text{s.t.}\ Q(x)$ は真である。
   $ $
   よって
   $$ \bigl(\exists x\in S\ \text{s.t.}\ P(x)\bigr)\lor\bigl(\exists x\in S\ \text{s.t.}\ Q(x)\bigr) $$
   は真である。
   $ $
   (ii) 次に
   $$ \bigl(\exists x\in S\ \text{s.t.}\ P(x)\bigr)\lor\bigl(\exists x\in S\ \text{s.t.}\ Q(x)\bigr)\ \Rightarrow\ \exists x\in S\ \text{s.t.}\ \bigl(P(x)\lor Q(x)\bigr) $$
   を示す。$\bigl(\exists x\in S\ \text{s.t.}\ P(x)\bigr)\lor\bigl(\exists x\in S\ \text{s.t.}\ Q(x)\bigr)$ が真であるとする。
   このとき$\exists x\in S\ \text{s.t.}\ P(x)$ が真であるか、または $\exists x\in S\ \text{s.t.}\ Q(x)$ が真である。
   $ $
   まず $\exists x\in S\ \text{s.t.}\ P(x)$ が真である場合を考える。このとき、ある $a\in S$ が存在して $P(a)$ が真である。
   従って $P(a)\lor Q(a)$ も真であるから、ある $x\in S$ が存在して $P(x)\lor Q(x)$ が真である。
   よって $\exists x\in S\ \text{s.t.}\ (P(x)\lor Q(x))$ は真である。
   $ $
   次に $\exists x\in S\ \text{s.t.}\ Q(x)$ が真である場合を考える。このとき、ある $b\in S$ が存在して $Q(b)$ が真である。
   従って $P(b)\lor Q(b)$ も真であるから、ある $x\in S$ が存在して $P(x)\lor Q(x)$ が真である。
   よって $\exists x\in S\ \text{s.t.}\ (P(x)\lor Q(x))$ は真である。
   $ $
   以上より
   $$ \exists x\in S\ \text{s.t.}\ \bigl(P(x)\lor Q(x)\bigr) $$
   が成り立つ。
   $ $
   (i)と(ii)より両方向の含意が成り立つので主張が成立する。
   $$ \Box$$