全称記号
概要
全称記号と存在記号（universal and existential quantifiers）とは、命題 $P(x)$ に対し「任意の $x\in X$ で $P(x)$」を表す $\forall x\in X,\ P(x)$ と「$P(x)$ が真の $x\in X$ が存在する」を表す $\exists x\in X,\ P(x)$ の記号（および一意存在の $\exists!$）をいう。$X$ が空でなければ全称命題は存在命題を含意し、$\exists x\,\forall y$ は $\forall y\,\exists x$ を含意するが逆は成り立たない。量化された命題の否定は、記号を入れ替えて内側の命題を否定したものである。空集合上では全称命題は常に真、存在命題は常に偽である。
定義
$X$ を集合とし、$X$ の元 $x$ ごとに真偽が定まる命題を $P(x)$ とする（$x$ を変数とする命題関数（propositional function）という）。
- 「任意の $x\in X$ に対して $P(x)$ が真である」ことを $\forall x\in X,\ P(x)$ と書く。$\forall$ を全称記号（universal quantifier）という。
- 「$P(x)$ が真であるような $x\in X$ が存在する」ことを $\exists x\in X,\ P(x)$ と書く。$\exists$ を存在記号（existential quantifier）という。
- 「$P(x)$ が真であるような $x\in X$ がただ一つ存在する」こと、すなわち $\exists x\in X,\ \bigl(P(x)\ \text{かつ}\ \forall y\in X,\ (P(y)\Rightarrow y=x)\bigr)$ を $\exists!\,x\in X,\ P(x)$ と書く。$\exists!$ を一意存在記号（unique existence quantifier）という（記法は Matsusaka68 第 1 章に従う）。
$\exists x\in X,\ P(x)$ は「ある $x\in X$ が存在して $P(x)$」とも読む。日本語としては不自然だが数学の慣用として定着している。記号 $\forall$、$\exists$ は文字 A、E を反転した形であり、All、Exist を連想すると覚えやすい（記号の歴史的な由来は本記事では扱わない）。$X$ が文脈から明らかなときは $\forall x,\ P(x)$、$\exists x,\ P(x)$ と略す。
直感
$\forall$ は「例外なくすべてで成り立つ」という強い主張、$\exists$ は「一つでも見つかればよい」という弱い主張である。二つの記号が並ぶときは、外側の記号ほど先に読む。「どの $y$ についても、それに応じて $x$ をうまく選べる」（$\forall y\,\exists x$）と、「一つの $x$ を先に固定して、それがどの $y$ に対しても通用する」（$\exists x\,\forall y$）とでは主張の強さが違い、後者の方が強い。この違いは解析学の各点連続と一様連続、各点収束と一様収束の違いそのものである。
例と反例
以下 $X=\{1,2,3,4,5\}$ とする。
$\forall x\in X,\ x<6$ は真である。実際 $1,2,3,4,5$ はいずれも $6$ より小さい。一方 $\forall x\in X,\ x<4$ は偽である。$x=4$ が $4<4$ を満たさないからである。
$\exists x\in X,\ x<4$ は真である。実際 $x=1$ が $1<4$ を満たす（$x=2,3$ でもよい）。一方 $\exists x\in X,\ x<1$ は偽である。$X$ のどの元も $1$ 以上だからである。
$\exists!\,x\in X,\ x<2$ は真である。$x=1$ が $1<2$ を満たし、$x<2$ を満たす $X$ の元は $1$ だけだからである。一方 $\exists x\in X,\ x<4$ は真だが $\exists!\,x\in X,\ x<4$ は偽である。$x=1,2,3$ の三つが条件を満たすからである。
次の例は「$\forall y\,\exists x,\ P(x,y)$ ならば $\exists x\,\forall y,\ P(x,y)$」が成り立たないことを示す。自然数全体 $\mathbb{N}$ 上で $P(x,y)$ を「$x>y$」とする。
- $\forall y\in\mathbb{N},\ \exists x\in\mathbb{N},\ x>y$ は真である。$y$ が与えられるごとに $x=y+1$ を選べばよい（$x$ は $y$ に応じて変えてよい）。
- $\exists x\in\mathbb{N},\ \forall y\in\mathbb{N},\ x>y$ は偽である。どんな $x$ をとっても $y=x$ に対して $x>x$ は成り立たないからである。
前者では $y$ ごとに別々の $x$ を選べるのに対し、後者では一つの $x$ がすべての $y$ に対して働かなければならない。逆向きの含意は常に成り立つ（prop-universal-existential-quantifiers-order）。
性質
$X\neq\emptyset$ とする。$\forall x\in X,\ P(x)$ が真ならば $\exists x\in X,\ P(x)$ も真である。また $\exists!\,x\in X,\ P(x)$ が真ならば $\exists x\in X,\ P(x)$ も真である。
$X\neq\emptyset$ なので元 $x_0\in X$ がとれる。$\forall x\in X,\ P(x)$ より特に $P(x_0)$ が真であり、$x_0$ は「$P(x)$ が真であるような $X$ の元」の一つである。よって $\exists x\in X,\ P(x)$ は真である。後半は、$\exists!$ の定義が $\exists x\in X,\ (P(x)\ \text{かつ}\ \cdots)$ の形をしており、$P(x)$ かつ何かが真なら $P(x)$ が真であることから従う。$\square$
$X=\emptyset$ のとき、$\forall x\in X,\ P(x)$ は（確かめるべき $x$ が一つもないので）常に真であり、$\exists x\in X,\ P(x)$ は（該当する $x$ が一つもないので）常に偽である。前者を空虚な真（vacuous truth）という。したがって prop-universal-existential-quantifiers-forall-exists の仮定 $X\neq\emptyset$ は落とせない。
$X,Y$ を集合、$P(x,y)$ を $x\in X$、$y\in Y$ ごとに真偽が定まる命題とする。$\exists x\in X,\ \forall y\in Y,\ P(x,y)$ が真ならば $\forall y\in Y,\ \exists x\in X,\ P(x,y)$ も真である。逆は一般に成り立たない（rem-universal-existential-quantifiers-counterexample）。
仮定より、ある $x_0\in X$ が存在して、任意の $y\in Y$ について $P(x_0,y)$ が真である。$y_0\in Y$ を任意にとると $P(x_0,y_0)$ は真なので、この $y_0$ に対して「$P(x,y_0)$ が真になる $x\in X$」として $x_0$ がとれる。$y_0$ は任意だったから $\forall y\in Y,\ \exists x\in X,\ P(x,y)$ が真である。$\square$
命題 $Q$ の否定を $\lnot Q$ と書く。次が成り立つ。
$$
\lnot\bigl(\forall x\in X,\ P(x)\bigr)\iff\exists x\in X,\ \lnot P(x),\qquad
\lnot\bigl(\exists x\in X,\ P(x)\bigr)\iff\forall x\in X,\ \lnot P(x).
$$
第一式：$\forall x\in X,\ P(x)$ が偽であるとは、「すべての $x\in X$ で $P(x)$ が真」ではないこと、すなわち $P(x)$ が真でない（$\lnot P(x)$ が真である）$x\in X$ が少なくとも一つあることである。これは $\exists x\in X,\ \lnot P(x)$ の定義そのものである。逆も同じ言い換えを逆にたどればよい。第二式：$\exists x\in X,\ P(x)$ が偽であるとは、$P(x)$ が真である $x\in X$ が一つもないこと、すなわちすべての $x\in X$ で $P(x)$ が偽（$\lnot P(x)$ が真）であることで、これは $\forall x\in X,\ \lnot P(x)$ である。$\square$
記号が複数並ぶ場合は外側から順に適用する。例えば
$$
\lnot\bigl(\forall y\in Y,\ \exists x\in X,\ P(x,y)\bigr)\iff\exists y\in Y,\ \lnot\bigl(\exists x\in X,\ P(x,y)\bigr)\iff\exists y\in Y,\ \forall x\in X,\ \lnot P(x,y)
$$
となる。$\forall$ と $\exists$ が入れ替わり、最後に内側の命題が否定される。
補足：空集合の場合を含めた真偽の一覧
| 命題 | $X\neq\emptyset$ のとき | $X=\emptyset$ のとき |
|---|---|---|
| $\forall x\in X,\ P(x)$ | $P$ が全元で真のとき真 | 常に真（空虚な真） |
| $\exists x\in X,\ P(x)$ | $P$ が真の元があれば真 | 常に偽 |
| $\exists!\,x\in X,\ P(x)$ | $P$ が真の元がちょうど一つのとき真 | 常に偽 |
| $\forall\Rightarrow\exists$ | 成り立つ（prop-universal-existential-quantifiers-forall-exists） | 成り立たない |
否定の規則（prop-universal-existential-quantifiers-negation）は $X=\emptyset$ でも成り立つ。実際 $\forall x\in\emptyset,\ P(x)$ は真、$\exists x\in\emptyset,\ \lnot P(x)$ は偽で、両辺の否定どうしが一致する。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
