量化子の深さとエーレンフォイヒト・フレッセゲーム

論理式の量化子の深さ $qr$ を計算できる。 $k$ 手のエーレンフォイヒト・フレッセゲームで複製者が勝つことと、深さ $k$ 以下の文で区別できないこと（ $A \equiv_{k} B$ ）が同値であることを使い、有限線形順序について「 $L_{m} \equiv_{k} L_{n} ⟺ m = n$ または $m, n \geq 2^{k} - 1$ 」から、 $L_{m}$ と $L_{n}$ を区別する文の量化子の深さの最小値を求められる（例: $L_{6}$ と $L_{7}$ は $3$ 、 $L_{7}$ と $L_{8}$ は $4$ ）

前提

一階述語論理の構造と文の真偽（大学院数学数理論理学・集合論）

この技能までの道筋（5 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
真理値表と充足割り当ての個数（大学院数学数理論理学・集合論）
一階述語論理の構造と文の真偽（大学院数学数理論理学・集合論）

説明

論理式に含まれる量化子の「入れ子の深さ」 $qr$ を数え、2 つの構造が深さ $k$ 以下の文では見分けられないか（ $A \equiv_{k} B$ ）を、エーレンフォイヒト・フレッセゲーム（EF ゲーム）という 2 人のゲームで判定できるようになります。特に、言語 ${<}$ の有限線形順序 $L_{n} = ({1, 2, \dots, n}, <)$ について、 $L_{m}$ と $L_{n}$ を区別するのに最低どれだけ深い文が必要かを、公式 $L_{m} \equiv_{k} L_{n} ⟺ m = n$ または $m, n \geq 2^{k} - 1$ から求められます。「この性質は一階の文で、どれくらいの複雑さで表せるか」を調べる場面で使います。

なぜそうしてよいのか

量化子の深さは次のように帰納的に定めます。原子式（ $x < y$ , $x = y$ など）は $qr = 0$ 、 $qr (\neg φ) = qr (φ)$ 、 $qr (φ \land ψ) = qr (φ \lor ψ) = qr (φ \to ψ) = max (qr (φ), qr (ψ))$ 、 $qr (\exists x φ) = qr (\forall x φ) = qr (φ) + 1$ 。つまり量化子の「個数」ではなく「何重に入れ子になっているか」です。 $A \equiv_{k} B$ は、 $qr \leq k$ のすべての文 $σ$ について「 $A ⊨ σ ⟺ B ⊨ σ$ 」が成り立つことをいいます。

$k$ 手の EF ゲームでは、攪乱者（スポイラー）と複製者（デュプリケーター）が交互に動きます。各手で攪乱者は $A$ か $B$ の一方を選んでその元を 1 つ取り、複製者はもう一方の構造の元を 1 つ取ります。 $k$ 手後に取られた元を $a_{1}, \dots, a_{k}$ と $b_{1}, \dots, b_{k}$ とし、対応 $a_{i} \mapsto b_{i}$ が原子式をすべて保つ（ $a_{i} < a_{j} ⟺ b_{i} < b_{j}$ , $a_{i} = a_{j} ⟺ b_{i} = b_{j}$ ）なら複製者の勝ち、そうでなければ攪乱者の勝ちです。文の真偽を判定するとき、 $\exists x$ は「ある元を 1 つ選ぶ」ことでした。攪乱者が $A$ で $\exists x φ (x)$ の証拠 $a$ を選ぶと、複製者は $B$ でそれに見合う $b$ を返さねばならない、という具合に、1 手が 1 重の量化子に対応します。このことから（有限個の関係記号・定数記号だけの言語で）「 $k$ 手のゲームで複製者に必勝法がある $⟺ A \equiv_{k} B$ 」が成り立ちます（エーレンフォイヒト・フレッセの定理）。

線形順序では、両端の外側に番兵 $0$ と $n + 1$ を置いて考えます。複製者は「残り $r$ 手のとき、取られた点（番兵を含む）の隣り合う 2 点の間隔が、両側で等しいか、両側とも $2^{r}$ 以上」を保つように応じれば負けません。間隔 $2^{r}$ 以上の区間に打たれても、うまく応じれば分かれた両側の間隔をそれぞれ等しいか $2^{r - 1}$ 以上にできるからです。逆に攪乱者は短い側の区間の中点を打って二分探索のように間隔を半減させ、 $k$ 手で差を暴けます。最初の間隔は番兵の間の $n + 1$ と $m + 1$ なので、条件は「 $m + 1 = n + 1$ または $m + 1, n + 1 \geq 2^{k}$ 」、すなわち $m = n$ または $m, n \geq 2^{k} - 1$ となります。 $- 1$ は番兵に由来します。

手順

量化子の深さを求めるときは、論理式を外側から分解し、原子式は $0$ 、否定はそのまま、 $\land, \lor, \to$ は $max$ 、量化子 1 つで $+ 1$ として計算する（個数ではなく入れ子の深さを数える）。
2 つの構造を区別する文の深さの最小値は「 $A \neq \equiv_{k} B$ となる最小の $k$ 」であることを確認する。 $qr \leq j$ の文は $qr \leq k$ （ $j \leq k$ ）の文でもあるので、 $\equiv_{k}$ なら $\equiv_{j}$ であり、深さ $k$ で区別できなければそれより浅くても区別できない。
有限線形順序 $L_{m}, L_{n}$ （ $m \neq = n$ ）では、 $s = min (m, n)$ とおき、公式 $L_{m} \equiv_{k} L_{n} ⟺ m, n \geq 2^{k} - 1$ を使う。大きい方は小さい方以上なので、条件は $s \geq 2^{k} - 1$ と同じになる。
$s \geq 2^{k} - 1$ （すなわち $s + 1 \geq 2^{k}$ ）が成り立たなくなる最小の $k$ を求める。 $2^{k} > s + 1$ となる最小の $k$ が答えである。
境目の $k - 1$ では $s \geq 2^{k - 1} - 1$ で $\equiv_{k - 1}$ 、 $k$ では $s < 2^{k} - 1$ で $\neq \equiv_{k}$ となっていることを両方確かめる。

例題

言語 ${<}$ の構造 $L_{n} = ({1, 2, \dots, n}, <)$ （ $<$ は通常の大小）を考える。 $L_{10}$ では成り立ち $L_{20}$ では成り立たない一階の文のうち、量化子の深さ $qr$ の最小値を求めよ。

例題の解答

（手順 2）区別する文の深さの最小値は、 $L_{10} \neq \equiv_{k} L_{20}$ となる最小の $k$ である。なお、 $σ$ が $L_{20}$ で成り立ち $L_{10}$ で成り立たないなら $\neg σ$ は逆向きに区別し、 $qr (\neg σ) = qr (σ)$ なので、どちら向きに区別するかで最小値は変わらない。

（手順 3） $10 \neq = 20$ なので、 $s = min (10, 20) = 10$ とおくと、 $L_{10} \equiv_{k} L_{20} ⟺ 10 \geq 2^{k} - 1$ 。

（手順 4） $2^{k} - 1$ を順に計算すると $k = 1$ : $1$ 、 $k = 2$ : $3$ 、 $k = 3$ : $7$ 、 $k = 4$ : $15$ 。 $10 \geq 2^{k} - 1$ が成り立たなくなる最小の $k$ は $4$ である（ $2^{4} = 16 > 11$ ）。

（手順 5） $k = 3$ では $10 \geq 7$ , $20 \geq 7$ なので $L_{10} \equiv_{3} L_{20}$ となり、深さ $3$ 以下の文では区別できない。 $k = 4$ では $10 < 15$ なので $L_{10} \neq \equiv_{4} L_{20}$ となり、深さ $4$ 以下のある文が両者で真偽が異なる。必要なら否定をとって $L_{10}$ で真、 $L_{20}$ で偽となる文にできる。

よって最小値は $4$ である。

答え: $4$

よくある誤り

量化子の個数を深さとしてしまう誤り。例えば $\exists x \exists y (x < y) \land \exists z (z = z)$ は量化子が 3 個だが、正しくは $qr = max (2, 1) = 2$ である。
境目を $2^{k}$ としてしまう誤り（「 $m, n \geq 2^{k}$ なら $\equiv_{k}$ 」）。正しくは番兵の分だけずれて $m, n \geq 2^{k} - 1$ である。例えば $L_{7}$ と $L_{8}$ は $7 \geq 2^{3} - 1$ なので $L_{7} \equiv_{3} L_{8}$ であり、区別に必要な深さは $3$ ではなく $4$ 。
大きい方 $max (m, n)$ や差 $∣ m - n ∣$ で判定してしまう誤り。例えば $L_{6}$ と $L_{100}$ で、大きい方 $100$ について $100 < 2^{7} - 1$ から「深さ $7$ が必要」としたり、差が $94$ と大きいから深い文が要ると考えたりするのは誤りである。条件は両方が $2^{k} - 1$ 以上であることなので、効くのは小さい方 $min (m, n) = 6$ で、 $6 \geq 2^{2} - 1 = 3$ かつ $6 < 2^{3} - 1 = 7$ より正しい深さは $3$ 。逆に $L_{14}$ と $L_{15}$ は差が $1$ しかないが、 $14 \geq 7$ かつ $14 < 15 = 2^{4} - 1$ より深さ $4$ が必要である。
「元が $n$ 個以上ある」を書いた文 $\exists x_{1} \dots \exists x_{n} ⋀_{i < j} x_{i} < x_{j}$ （ $qr = n$ ）で区別できるから最小の深さも $n$ だとしてしまう誤り。これは上界にすぎず、例えば $L_{6}$ と $L_{7}$ は深さ $7$ の文で区別できるが、正しい最小値は $6 < 2^{3} - 1$ , $6 \geq 2^{2} - 1$ より $3$ である。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
関係記号 $<$ を 1 つだけもつ一階述語論理の言語を考える（等号 $=$ は使ってよいとする）。正の整数 $n$ に対し、 $L_{n} = ({1, 2, \dots, n}, <)$ を、 $<$ を通常の大小関係と解釈した有限線形順序とする。論理式 $φ$ の量化子の深さ（量化子の入れ子の最大の深さ）を $qr (φ)$ と書き、構造 $A, B$ が量化子の深さ $k$ 以下のすべての文で同じ真偽をとることを $A \equiv_{k} B$ と書く。
有限線形順序について、正の整数 $k$ に対して
$L_{m} \equiv_{k} L_{n} ⟺ m = n または m, n \geq 2^{k} - 1$
が成り立つことを用いてよい。
$L_{12} ⊨ σ$ かつ $L_{20} \neq ⊨ σ$ となる文 $σ$ （ $L_{12}$ と $L_{20}$ を区別する文）の量化子の深さ $qr (σ)$ の最小値を求めよ。

量化子の深さとエーレンフォイヒト・フレッセゲーム

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題