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

最終更新

量化子のネストとは、∀\forall（すべて）と∃\exists（ある）が二つ以上重なった命題のことです。本記事でもっとも重要な点は、∀\forallと∃\existsの順序を入れ替えると、命題の意味が変わることです。大学の数学、とくにε\varepsilon-δ\delta論法の読み書きでは、この順序の区別が中心になります。ここでは、順序を機械的に読み分けることができるようにします。

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が条件文全体に及んでおり、後者ではP(x)P(x)にしか及んでいないため、Q(x)Q(x)のxxは量化されていません。括弧を省いて二通りに読むことができる式を書かず、どこまでが量化子の範囲であるかを明示します。

量化子が二つ以上並ぶときは、左から順に読みます。∀x ∃y P(x,y)\forall x\, \exists y\, P(x,y)は、「まず任意の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 一方向の含意だけは常に成り立つ

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

定理 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)は偽です。▨

すべてのxxに共通して使うことができるyyが一つあるのなら、xxごとにyyを選ぶことも当然することができます。逆に、xxごとにyyを選ぶことができるからといって、すべてのxxに共通するyyが取れるとはかぎりません。

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

例題

条件と何を求めるかを確認してから、式と答えの対応を見比べてください。

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

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

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

  1. 例題 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}

  2. 例題 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}

  3. 例題 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}

  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}

  5. 例題 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}

  6. 例題 6

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

演習

問題を解いてから「解答・解説」を開けます。

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

演習を読み込み中…

前提記事