全称記号と存在記号(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)という)。
$\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$ の読み方と、量化された命題の真偽の定め方は Ham §2.7 による。
$\forall$ は「例外なくすべてで成り立つ」という強い主張、$\exists$ は「一つでも見つかればよい」という弱い主張である。二つの記号が並ぶときは、外側の記号ほど先に読む。「どの $y$ についても、それに応じて $x$ をうまく選べる」($\forall y\,\exists x$)と、「一つの $x$ を先に固定して、それがどの $y$ に対しても通用する」($\exists x\,\forall y$)とでは主張の強さが違い、後者の方が強い。この違いは解析学の各点連続と一様連続、各点収束と一様収束の違いそのものである。
$\forall x\in X,\ P(x)$ に現れる $x$ は、記号 $\forall$ によって束縛されている(bound)といい、束縛された変数を束縛変数という。束縛変数は「すべての $x$ について」の $x$ であり、名前を変えても意味は変わらない。$\forall x\in X,\ P(x)$ と $\forall t\in X,\ P(t)$ は同じ命題である。これに対し、どの記号にも束縛されていない変数を自由変数(free variable)という。命題 $\exists y\in\mathbb R,\ y^2=x$ では $y$ が束縛変数、$x$ が自由変数であり、この命題の真偽は $x$ の値によって決まる($x\ge0$ なら真、$x< 0$ なら偽)。すなわちこれは $x$ についての命題関数である。
変数の名前を変えるときは、自由変数と同じ名前を束縛変数に使ってはならない。$\exists y\in\mathbb R,\ y>x$ の束縛変数 $y$ を $x$ に書き換えると $\exists x\in\mathbb R,\ x>x$ となり、偽の命題に変わってしまう。これを避けるため、書き換えには式に現れていない新しい文字を使う。論理式の中の出現ごとの区別と、代入が意味を保つ条件は 自由変数と束縛変数 で扱う。
集合 $\{x\in\mathbb R\mid \exists n\in\mathbb N,\ x=n^2\}$ では、$n$ は $\exists$ に、$x$ は集合の記法 $\{x\in\mathbb R\mid\cdots\}$ に束縛されている。この集合は平方数 $0,1,4,9,\dots$ 全体である。$\sum_{k=1}^n k$ の $k$ や、$\int_0^1 f(t)\,dt$ の $t$ も同じ意味の束縛変数であり、名前を替えても値は変わらない。一方、和 $\sum_{k=1}^n k$ の上端の $n$ はどの記号にも束縛されておらず、和の値を左右する自由変数である(前半の集合の記法の $n$ とは別の変数である)。
以下 $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$」とする。
$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$ が入れ替わり、最後に内側の命題が否定される(量化された命題の否定の作り方は Ham §2.10 も参照)。
量化と「かつ」「または」の組合せには、入れ替えてよいものと、よくないものがある。以下 $P(x),Q(x)$ を $x\in X$ についての命題関数、$R$ を $x$ を含まない命題とする。
次が成り立つ。
(1) $\forall x\in X,\ \bigl(P(x)\ \text{かつ}\ Q(x)\bigr)\iff\bigl(\forall x\in X,\ P(x)\bigr)\ \text{かつ}\ \bigl(\forall x\in X,\ Q(x)\bigr)$。
(2) $\exists x\in X,\ \bigl(P(x)\ \text{または}\ Q(x)\bigr)\iff\bigl(\exists x\in X,\ P(x)\bigr)\ \text{または}\ \bigl(\exists x\in X,\ Q(x)\bigr)$。
(3) $\bigl(\forall x\in X,\ P(x)\bigr)\ \text{または}\ \bigl(\forall x\in X,\ Q(x)\bigr)\Longrightarrow\forall x\in X,\ \bigl(P(x)\ \text{または}\ Q(x)\bigr)$。
(4) $\exists x\in X,\ \bigl(P(x)\ \text{かつ}\ Q(x)\bigr)\Longrightarrow\bigl(\exists x\in X,\ P(x)\bigr)\ \text{かつ}\ \bigl(\exists x\in X,\ Q(x)\bigr)$。
(5) $\forall x\in X,\ \bigl(P(x)\Rightarrow R\bigr)\iff\bigl(\exists x\in X,\ P(x)\bigr)\Rightarrow R$。
(3)(4) の逆は一般に成り立たない(ex-universal-existential-quantifiers-parity)。
$X=\mathbb Z$、$P(x)$ を「$x$ は偶数」、$Q(x)$ を「$x$ は奇数」とする。どの整数も偶数か奇数なので $\forall x\in\mathbb Z,\ (P(x)\ \text{または}\ Q(x))$ は真である。しかし「すべての整数が偶数」も「すべての整数が奇数」も偽なので、$(\forall x,\ P(x))\ \text{または}\ (\forall x,\ Q(x))$ は偽である。よって (3) の逆は成り立たない。同じ $P,Q$ で、$\exists x,\ P(x)$($x=0$)と $\exists x,\ Q(x)$($x=1$)はともに真だが、偶数かつ奇数の整数はないので $\exists x,\ (P(x)\ \text{かつ}\ Q(x))$ は偽である。よって (4) の逆も成り立たない。
量化の順序と否定の規則は、解析学の定義を読むときにそのまま使われる。関数 $f\colon\mathbb R\to\mathbb R$ が点 $a$ で連続であることは
$$
\forall\varepsilon>0,\ \exists\delta>0,\ \forall x\in\mathbb R,\ \bigl(|x-a|< \delta\Rightarrow|f(x)-f(a)|< \varepsilon\bigr)
$$
と書かれる。ここで $\forall\varepsilon>0$ は $\forall\varepsilon\in(0,\infty)$ の略記である。
上の式を否定の規則で外側から順に否定すると、$f$ が $a$ で連続でないことは
$$
\exists\varepsilon>0,\ \forall\delta>0,\ \exists x\in\mathbb R,\ \bigl(|x-a|< \delta\ \text{かつ}\ |f(x)-f(a)|\ge\varepsilon\bigr)
$$
となる。最後の段では「$A\Rightarrow B$ の否定は $A$ かつ $B$ でない」を使った。例えば $f(x)=0$($x\le0$)、$f(x)=1$($x>0$)は $a=0$ で連続でない:$\varepsilon=1/2$ とすると、どの $\delta>0$ に対しても $x=\delta/2$ が $|x|< \delta$ かつ $|f(x)-f(0)|=1\ge1/2$ を満たす。
$f$ が $\mathbb R$ 上で各点で連続であることは $\forall a\,\forall\varepsilon\,\exists\delta\,\forall x$、一様連続であることは $\forall\varepsilon\,\exists\delta\,\forall a\,\forall x$ の形をしている。後者では $\delta$ を $a$ に依存せずに選ぶ必要があり、prop-universal-existential-quantifiers-order の形の含意によって、一様連続なら各点で連続である。逆が成り立たない例として、$f(x)=x^2$ は各点で連続だが一様連続でない(一様連続の例「反例:実数全体上の2乗」)。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $X\ne\emptyset$ | $X=\emptyset$ | $\forall$ から $\exists$ を導くこと |
| 量化の順序を保つ | $\mathbb N$ 上の $x>y$ | $\forall y\,\exists x$ から $\exists x\,\forall y$ を導くこと |
| $\forall$ を「かつ」とだけ組む | $\mathbb Z$ 上の偶数・奇数 | $\forall$ を「または」の各項へ分けること |
| $\exists$ を「または」とだけ組む | $\mathbb Z$ 上の偶数・奇数 | $\exists$ を「かつ」の各項から合わせること |
一行目は rem-universal-existential-quantifiers-empty、二行目は rem-universal-existential-quantifiers-counterexample、三・四行目は ex-universal-existential-quantifiers-parity で確かめた。
| 命題 | $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アソシエイト)の紹介料で運営されています。 支援について / 寄付する