§A3.11量化子のネストと順序

最終更新

「すべての実数に対して、それより大きい実数が存在する」と「すべての実数より大きい実数が存在する」では、用いている大小の条件は同じでも、真偽が異なります。この違いを読むには、量化子の順序だけでなく、それぞれが式のどこまで及ぶかも確かめる必要があります。量化されていない変数が残る式は、その変数の値を指定して読む条件として扱います。

本記事では、量化子の順序による意味の違いと基本的な含意を、具体例とともに解説します。

1 量化子が及ぶ範囲

∀x\forall xや∃x\exists xは、その後ろに続く部分に対して働きます。この働く範囲を、その量化子のスコープと呼びます。スコープは括弧で示します。

∀x (P(x)⇒Q(x))と(∀x P(x))⇒Q(x)\forall x\, \bigl(P(x) \Rightarrow Q(x)\bigr) \qquad \text{と} \qquad \bigl(\forall x\, P(x)\bigr) \Rightarrow Q(x)

の二つは、量化子の及ぶ範囲が異なる式です。前者では∀x\forall xが条件文全体に及んでいます。後者では∀x\forall xがP(x)P(x)にしか及ばず、Q(x)Q(x)のxxは量化されていません。後者は一般にxxの値によって真偽が変わる条件であり、xxの値を定めるか、さらに量化するまでは閉じた命題になりません。括弧を省いて二通りに読むことができる式を書かず、どこまでが量化子の範囲であるかを明示します。

量化子が二つ以上並ぶときは、左から順に読みます。∀x ∃y P(x,y)\forall x\, \exists y\, P(x,y)は、「まず任意のxxが与えられ、その後で、与えられたxxに応じてyyを選ぶ」という順序を表します。

2 量化子の順序と意味

例 2.1. 次の二つを見比べる。xx、yyは実数の範囲を動く。

  • ∀x ∃y (y>x)\forall x\, \exists y\ (y > x)：「どのようなxxに対しても、xxに応じて選んでよいあるyyが存在してy>xy > xとなる」——真である。y=x+1y = x + 1とすればよい。
  • ∃y ∀x (y>x)\exists y\, \forall x\ (y > x)：「あるyyが存在して、すべてのxxに対してy>xy > xとなる」—— 偽である。すべての実数より大きい実数は存在しないからである。

内側の条件はどちらもy>xy > xで同じですが、量化子の順序だけで真偽が逆転しました。二つの命題の違いは、yyをxxに応じて選ぶことができるのか、それともxxより先にyyを一つ固定するのかという点にあります。∀x ∃y\forall x\, \exists yでは、yyはxxに依存してかまいません。すなわち、xxごとに別のyyを取ることができます。∃y ∀x\exists y\, \forall xでは、yyを先に一つ決めた後ですべてのxxを見るので、yyはxxに依存することができません。

3 共通の対象から個別の対象への含意

∀\forallと∃\existsの順序を自由に交換することはできませんが、一方向の含意は常に成り立ちます。

定理 3.1. 任意の述語PPに対し∃y ∀x P(x,y)⇒∀x ∃y P(x,y)\exists y\,\forall x\, P(x, y) \Rightarrow \forall x\,\exists y\, P(x, y)が成り立つ。逆向きの含意は一般には成り立たない。

証明. 前提より、すべてのxxについてP(x,y0)P(x, y_0)を満たすy0y_0が一つ存在する。各xxに対してy=y0y = y_0が∃y P(x,y)\exists y\, P(x, y)を満たすので、∀x ∃y P(x,y)\forall x\,\exists y\, P(x, y)が成り立つ。逆向きの含意が成り立たないことは、例 2.1により示されている。そこでは∀x ∃y (y>x)\forall x\,\exists y\,(y > x)が真であるのに∃y ∀x (y>x)\exists y\,\forall x\,(y > x)は偽である。▨

なお、∀\forallどうし、∃\existsどうしを入れ替えても、命題の意味は変わりません。∀x ∀y\forall x\,\forall yと∀y ∀x\forall y\,\forall xは同じ命題であり、∃\existsについても同様です。注意が必要なのは、∀\forallと∃\existsが隣り合っている場合だけです。

4 例題

レベル2 — 量化子の順序（∀∃ と ∃∀）

次の2つの命題は、量化子の順序だけが違う。それぞれの真偽を判定せよ。

解法の型左から順に決めていく。∀x\forall x∃y\exists yは y を x ごとに選べる、∃y\exists y∀x\forall xは y が全 x 共通の1つ。∀\forallと∃\existsが隣り合う入れ替えは意味を変える

量化子の順序だけが違う次の2つの命題について、それぞれの真偽を判定せよ。

例 4.1.

（m,n は自然数）(1) ∀m ∃n (n>m)(2) ∃n ∀m (n>m)\begin{array}{l} \text{（}m, n \text{ は自然数）} \\ (1)\ \forall m\, \exists n\ (n > m) \\ (2)\ \exists n\, \forall m\ (n > m) \end{array}

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) は各 m に対し n==m + 1 と取れるので真。(2) は「最大の自然数より大きい n が1つある」に相当し、n を固定したとき m==n が反例（n > n は偽）。よって偽。

例 4.2.

（数列 an=1/n, n≥1）(1) ∀ε>0 ∃N ∀n≥N (∣an∣<ε)(2) ∃N ∀ε>0 ∀n≥N (∣an∣<ε)\begin{array}{l} \text{（数列 } a_n = 1/n,\ n \ge 1 \text{）} \\ (1)\ \forall \varepsilon > 0\, \exists N\, \forall n \ge N\ (|a_n| < \varepsilon) \\ (2)\ \exists N\, \forall \varepsilon > 0\, \forall n \ge N\ (|a_n| < \varepsilon) \end{array}

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) は収束の定義そのもので、N をε\varepsilonごとに選んでよいから真（1/N <ε\varepsilonとなる N を取る）。(2) は N を先に固定し、その後どんなに小さいε\varepsilonでも成り立つことを要求する。N を固定したとき n==N としてε=\varepsilon =1/(2N) と取れば |a_N|==1/N >ε\varepsilonなので反例。(2) は実質「n≥\geN ですべて 0」を意味してしまう。

例 4.3.

（x は実数、n は自然数）(1) ∀x ∃n (n>x)(2) ∃n ∀x (n>x)\begin{array}{l} \text{（}x \text{ は実数、} n \text{ は自然数）} \\ (1)\ \forall x\, \exists n\ (n > x) \\ (2)\ \exists n\, \forall x\ (n > x) \end{array}

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) はアルキメデスの原理で真（どんな実数より大きい自然数が取れる）。(2) は n を先に固定するので、x==n と取れば n > x は成り立たず反例。すべての実数より大きい自然数は存在しないので偽。

例 4.4.

（x,y は実数）(1) ∀x ∃y (y>x)(2) ∃y ∀x (y>x)\begin{array}{l} \text{（}x, y \text{ は実数）} \\ (1)\ \forall x\, \exists y\ (y > x) \\ (2)\ \exists y\, \forall x\ (y > x) \end{array}

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) は「x を見てから y を選んでよい」ので y==x + 1 と取れば真。(2) は「y を先に1つ固定し、その後すべての x で y > x」を要求する。どんな y を固定しても x==y と取れば y > x は成り立たない（これが反例）ので偽。順序を入れ替えると y が x に依存できるかどうかが変わる。

例 4.5.

（x,y は実数）(1) ∀x ∃y (x+y=0)(2) ∃y ∀x (x+y=0)\begin{array}{l} \text{（}x, y \text{ は実数）} \\ (1)\ \forall x\, \exists y\ (x + y = 0) \\ (2)\ \exists y\, \forall x\ (x + y = 0) \end{array}

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) は各 x に対し y==-x と取れるので真。(2) は y を先に1つ固定するので、x==1 - y と取れば x + y==1≠\ne0 となり反例。ひとつの y がすべての x の逆元になることはできないので偽。

例 4.6.

（人全体を考える）(1) すべての人には、ある母親がいる(2) ある人が存在して、その人はすべての人の母親である\begin{array}{l} \text{（人全体を考える）} \\ (1)\ \text{すべての人には、ある母親がいる} \\ (2)\ \text{ある人が存在して、その人はすべての人の母親である} \end{array}

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) は「人ごとに母親を選んでよい」ので真。(2) は「たった1人がすべての人の母親」を主張する。どの人 m を選んでも、m 自身の母親は m ではない（あるいは m は自分自身の母親ではない）ので反例になり、偽。∀∃\forall\existsと∃∀\exists\forallは同じ述語でもまったく違う主張になる。

5 演習

レベル2 — 量化子の順序（∀∃ と ∃∀）

次の2つの命題は、量化子の順序だけが違う。それぞれの真偽を判定せよ。

解法の型左から順に決めていく。∀x\forall x∃y\exists yは y を x ごとに選べる、∃y\exists y∀x\forall xは y が全 x 共通の1つ。∀\forallと∃\existsが隣り合う入れ替えは意味を変える

量化子の順序だけが違う次の2つの命題について、それぞれの真偽を判定せよ。

問題 5.1.

（数列 an=1/n, n≥1）(1) ∀ε>0 ∃N ∀n≥N (∣an∣<ε)(2) ∃N ∀ε>0 ∀n≥N (∣an∣<ε)\begin{array}{l} \text{（数列 } a_n = 1/n,\ n \ge 1 \text{）} \\ (1)\ \forall \varepsilon > 0\, \exists N\, \forall n \ge N\ (|a_n| < \varepsilon) \\ (2)\ \exists N\, \forall \varepsilon > 0\, \forall n \ge N\ (|a_n| < \varepsilon) \end{array}
解答.

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) は収束の定義そのもので、N をε\varepsilonごとに選んでよいから真（1/N <ε\varepsilonとなる N を取る）。(2) は N を先に固定し、その後どんなに小さいε\varepsilonでも成り立つことを要求する。N を固定したとき n==N としてε=\varepsilon =1/(2N) と取れば |a_N|==1/N >ε\varepsilonなので反例。(2) は実質「n≥\geN ですべて 0」を意味してしまう。▨

問題 5.2.

（人全体を考える）(1) すべての人には、ある母親がいる(2) ある人が存在して、その人はすべての人の母親である\begin{array}{l} \text{（人全体を考える）} \\ (1)\ \text{すべての人には、ある母親がいる} \\ (2)\ \text{ある人が存在して、その人はすべての人の母親である} \end{array}
解答.

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) は「人ごとに母親を選んでよい」ので真。(2) は「たった1人がすべての人の母親」を主張する。どの人 m を選んでも、m 自身の母親は m ではない（あるいは m は自分自身の母親ではない）ので反例になり、偽。∀∃\forall\existsと∃∀\exists\forallは同じ述語でもまったく違う主張になる。▨

問題 5.3.

（x,y は実数）(1) ∀x ∃y (x+y=0)(2) ∃y ∀x (x+y=0)\begin{array}{l} \text{（}x, y \text{ は実数）} \\ (1)\ \forall x\, \exists y\ (x + y = 0) \\ (2)\ \exists y\, \forall x\ (x + y = 0) \end{array}
解答.

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) は各 x に対し y==-x と取れるので真。(2) は y を先に1つ固定するので、x==1 - y と取れば x + y==1≠\ne0 となり反例。ひとつの y がすべての x の逆元になることはできないので偽。▨

問題 5.4.

（m,n は自然数）(1) ∀m ∃n (n>m)(2) ∃n ∀m (n>m)\begin{array}{l} \text{（}m, n \text{ は自然数）} \\ (1)\ \forall m\, \exists n\ (n > m) \\ (2)\ \exists n\, \forall m\ (n > m) \end{array}
解答.

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) は各 m に対し n==m + 1 と取れるので真。(2) は「最大の自然数より大きい n が1つある」に相当し、n を固定したとき m==n が反例（n > n は偽）。よって偽。▨

問題 5.5.

（x は実数、n は自然数）(1) ∀x ∃n (n>x)(2) ∃n ∀x (n>x)\begin{array}{l} \text{（}x \text{ は実数、} n \text{ は自然数）} \\ (1)\ \forall x\, \exists n\ (n > x) \\ (2)\ \exists n\, \forall x\ (n > x) \end{array}
解答.

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) はアルキメデスの原理で真（どんな実数より大きい自然数が取れる）。(2) は n を先に固定するので、x==n と取れば n > x は成り立たず反例。すべての実数より大きい自然数は存在しないので偽。▨

問題 5.6.

（x,y は実数）(1) ∀x ∃y (y>x)(2) ∃y ∀x (y>x)\begin{array}{l} \text{（}x, y \text{ は実数）} \\ (1)\ \forall x\, \exists y\ (y > x) \\ (2)\ \exists y\, \forall x\ (y > x) \end{array}
解答.

答

(1)真(2)偽\begin{array}{ll} (1) & \text{真} \\ (2) & \text{偽} \end{array}

注意 (1) は「x を見てから y を選んでよい」ので y==x + 1 と取れば真。(2) は「y を先に1つ固定し、その後すべての x で y > x」を要求する。どんな y を固定しても x==y と取れば y > x は成り立たない（これが反例）ので偽。順序を入れ替えると y が x に依存できるかどうかが変わる。▨

前提記事