数理論理学・集合論の問題

$L_{12}$ と $L_{20}$ を区別する文で量化子の深さが $k$ 以下のものが存在することは、$L_{12}/{\equiv }_k{L}_{20}$ であることと同じである（${\equiv }_k$ の定義そのもの）。また ${\equiv }_k$ は $k$ が大きいほど強い条件なので（深さ $k-1$ 以下の文は深さ $k$ 以下の文でもある）、求める最小値は「$L_{12}/{\equiv }_k{L}_{20}$ となる最小の $k$」である。これはエーレンフォイヒト・フレッセゲームの言葉では、$k$ 手のゲームで撹乱者が勝つ最小の $k$ に当たる。

与えられた事実で $m=12,n=20$ とすると $m\ne n$ なので、
$$L_{12}{\equiv }_k{L}_{20}⟺12\ge 2^k-1\text{かつ}20\ge 2^k-1⟺2^k-1\le 12.$$
各 $k$ について $2^k-1$ を計算すると
- $k=1$: $2^1-1=1\le 12$ なので $L_{12}{\equiv }_1{L}_{20}$
- $k=2$: $2^2-1=3\le 12$ なので $L_{12}{\equiv }_2{L}_{20}$
- $k=3$: $2^3-1=7\le 12$ なので $L_{12}{\equiv }_3{L}_{20}$
- $k=4$: $2^4-1=15>12$ なので $L_{12}/{\equiv }_4{L}_{20}$

したがって、深さ $3$ 以下の文ではどれも $L_{12}$ と $L_{20}$ で真偽が一致し（3 手のゲームでは複製者が勝つ）、区別できない。一方、$L_{12}/{\equiv }_4{L}_{20}$ より、深さ $4$ 以下の文 $\tau$ で $L_{12}$ と $L_{20}$ で真偽が異なるものがある。$L_{12}\models \tau$ ならば $\sigma =\tau$、$L_{12}/\models \tau$ ならば $\sigma =\neg \tau$ とすれば（否定をつけても量化子の深さは変わらない）、$L_{12}\models \sigma$ かつ $L_{20}/\models \sigma$ となり、$\mathrm{qr}(\sigma )\le 4$ である。深さ $3$ 以下では区別できないので $\mathrm{qr}(\sigma )=4$ である。

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

$L_{12}$ と $L_{20}$ を区別する文の量化子の深さの最小値は、$L_{12}/{\equiv }_k{L}_{20}$ となる最小の $k$ である（深さ $k$ 以下の文で区別できることと $/{\equiv }_k$ は同値）。

与えられた事実より、$m\ne n$ のとき $L_m{\equiv }_k{L}_n⟺m,n\ge 2^k-1$。ここで $m=12,n=20$。

• $k=1$: $2^1-1=1$。$12,20\ge 1$ なので $L_{12}{\equiv }_1{L}_{20}$。
• $k=2$: $2^2-1=3$。$12,20\ge 3$ なので $L_{12}{\equiv }_2{L}_{20}$。
• $k=3$: $2^3-1=7$。$12,20\ge 7$ なので $L_{12}{\equiv }_3{L}_{20}$。
• $k=4$: $2^4-1=15$。$12<15$ なので $m,n\ge 15$ は成り立たず、$12\ne 20$ でもあるから $L_{12}/{\equiv }_4{L}_{20}$。

よって深さ 3 以下の文では区別できず、深さ 4 の文で区別できる。したがって最小値は $4$。

確かめ: $k=4$ の文が存在することは $/{\equiv }_4$ の定義そのもの（深さ 4 以下のある文で真偽が異なる。深さ 3 以下では一致するので、その文の深さはちょうど 4）。また、$12$ は $15$ 未満、$20$ は $15$ 以上なので、閾値 $2^4-1=15$ がちょうど 2 つの順序の間にある。