述語論理 ➃
はじめに
こちら ① に、これまでに作成した数学ノートをシリーズとしてまとめています(※)。
※ 読み進める順番は、ページ下部（古い記事）から上部（新しい記事）へです。
$ $
こちら ➁ に、証明を進めるうえでのポイントを随時まとめています。必要に応じて参照してください。
こちら ③ に、数学における基本用語を随時まとめています。必要に応じて参照してください。
$ $
Prop & Proof
集合 $S$ を定義域とし、$R(x,y)$ を $S$ を定義域とする命題関数とする。このとき次が成り立つ。
$$
\forall x\in S,\ \forall y\in S,\ R(x,y)\ \Leftrightarrow\ \forall y\in S,\ \forall x\in S,\ R(x,y)
$$
- まず
$$ \forall x\in S,\ \forall y\in S,\ R(x,y)\ \Rightarrow\ \forall y\in S,\ \forall x\in S,\ R(x,y) $$
を示す。
$ $
$\forall x\in S,\ \forall y\in S,\ R(x,y)$ が真であるとする。すると、任意の $a\in S$ に対して、$\forall y\in S,\ R(a,y)$ が真である。
従って、任意の $a\in S$ と任意の $b\in S$ に対して $R(a,b)$ は真である。
$ $
そこで、任意の $b\in S$ を$1$つとる。
(上より)任意の $a\in S$ について $R(a,b)$ は真であるから、$\forall x\in S,\ R(x,b)$ は真である。
$b\in S$ は任意であったから，$\forall y\in S,\ \forall x\in S,\ R(x,y)$ は真である。
$ $ - 次に
$$ \forall y\in S,\ \forall x\in S,\ R(x,y)\ \Rightarrow\ \forall x\in S,\ \forall y\in S,\ R(x,y) $$
を示す。
$ $
$\forall y\in S,\ \forall x\in S,\ R(x,y)$ が真であるとする。すると、任意の $b\in S$ に対して、$\forall x\in S,\ R(x,b)$ が真である。
従って、任意の $b\in S$ と任意の $a\in S$ に対して $R(a,b)$ は真である。
$ $
そこで、任意の $a\in S$ を$1$つとる。
(上より)任意の $b\in S$ について $R(a,b)$ は真であるから、$\forall y\in S,\ R(a,y)$ は真である。
$a\in S$ は任意であったから、$\forall x\in S,\ \forall y\in S,\ R(x,y)$ は真である。
$ $
-1.と2.より両方向の含意が成り立つので主張が成立する。
$$ \Box$$
集合 $S$ を定義域とし、$R(x,y)$ を $S$ を定義域とする命題関数とする。このとき次が成り立つ。
$$
\exists x\in S,\ \exists y\in S\ \text{s.t.}\ R(x,y)\ \Leftrightarrow\ \exists y\in S,\ \exists x\in S\ \text{s.t.}\ R(x,y)
$$
- まず
$$ \exists x\in S, \ \exists y\in S\ \text{s.t.}\ R(x,y)\ \Rightarrow\ \exists y\in S, \ \exists x\in S\ \text{s.t.}\ R(x,y) $$
を示す。
$ $
$\exists x\in S, \ \exists y\in S\ \text{s.t.}\ R(x,y)$ が真であるとする。
すると、ある $a\in S$ が存在して、$\exists y\in S\ \text{s.t.}\ R(a,y)$ が真である。
従って、ある $b\in S$ が存在して、$R(a,b)$ が真である。
ここで $b\in S$ が存在して $R(a,b)$ が真であるから$\exists x\in S\ \text{s.t.}\ R(x,b)$ は真である。よって、
$$ \exists y\in S,\ \exists x\in S\ \text{s.t.}\ R(x,y) $$
は真である。
$ $ - 次に
$$ \exists y\in S, \ \exists x\in S\ \text{s.t.}\ R(x,y)\ \Rightarrow\ \exists x\in S, \ \exists y\in S\ \text{s.t.}\ R(x,y) $$
を示す。
$ $
$\exists y\in S, \ \exists x\in S\ \text{s.t.}\ R(x,y)$ が真であるとする。
すると、ある $b\in S$ が存在して、$\exists x\in S\ \text{s.t.}\ R(x,b)$ が真である。
従って、ある $a\in S$ が存在して、$R(a,b)$ が真である。
ここで $a\in S$ が存在して $R(a,b)$ が真であるから、$\exists y\in S\ \text{s.t.}\ R(a,y)$ は真である。よって、
$$ \exists x\in S,\ \exists y\in S\ \text{s.t.}\ R(x,y) $$
は真である。
$ $
-1.と2.より、両方向の含意が成り立つので主張が成立する。
$$ \Box$$
$\forall$ と $\exists$ を入れ替えると一般には同値でない。すなわち、
$$
\forall x\in S,\ \exists y\in S\ \text{s.t.}\ R(x,y)
$$
と
$$
\exists y\in S\ \text{s.t.}\ \forall x\in S,\ R(x,y)
$$
は一般に同値ではない。
$ $
例えば、$S=\mathbb{N}$ とし、$R(x,y)$ を
$$
R(x,y):\ x< y
$$
で定める。このとき
$$
\forall x\in\mathbb{N},\ \exists y\in\mathbb{N}\ \text{s.t.}\ R(x,y)
$$
は真である。実際、任意の $x\in\mathbb{N}$ に対して、例えば $y=x+1$ と取れば $x< y$ が成り立つ。
$ $
一方で
$$
\exists y\in\mathbb{N}\ \text{s.t.}\ \forall x\in\mathbb{N},\ R(x,y)
$$
は偽である。実際、命題
$$
\exists y\in\mathbb{N}\ \text{s.t.}\ \forall x\in\mathbb{N},\ x< y
$$
が真であると仮定する。すると、ある $y_0\in\mathbb{N}$ が存在して
$$
\forall x\in\mathbb{N},\ x< y_0
$$
が成り立つ。ここで $x:=y_0$ とおくと、$x\in\mathbb{N}$ であるから上の全称命題より
$$
y_0< y_0
$$
が従うが、これは成り立たない。従って元の存在命題は偽である。
$ $
従って、この例では
$$
\forall x\in S,\ \exists y\in S\ \text{s.t.}\ R(x,y)
$$
は真であるが
$$
\exists y\in S\ \text{s.t.}\ \forall x\in S,\ R(x,y)
$$
は偽であり、両者は同値ではない。
この記事を高評価した人
この記事に送られたバッジ
投稿者
