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

$\mathcal{A}{\equiv }_k\mathcal{B}$ を「量化子の深さ $k$ 以下のすべての文で真偽が一致する」と定める。文 $\sigma$ が $L_n$ で真・$L_{n+1}$ で偽なら $\neg \sigma$ は逆になり、深さは同じなので、
$$f(n)=\min \{k:L_n/{\equiv }_k{L}_{n+1}\}$$
である。エーレンフォイヒト・フレッセのゲームの定理（有限関係言語では、$\mathcal{A}{\equiv }_k\mathcal{B}$ と、$k$ ラウンドのゲームで Duplicator が必勝であることは同値）を使う。

補題. $k\ge 0$ と $m,n\ge 0$（$L_0$ は空の順序。補題の中だけで使う）に対し、$k$ ラウンドのゲーム $G_k(L_m,L_n)$ で Duplicator が必勝であることと、
$$m=n\text{または}m,n\ge 2^k-1$$
は同値である。

証明（$k$ についての帰納法）. $k=0$ では $2^0-1=0$ なので主張は自明。$k$ で成り立つとして $k+1$ を示す。$t=2^k-1$ とおくと $2^{k+1}-1=2t+1$ である。順序に元 $a$ を選ぶと、残りは「$a$ より小さい部分」と「$a$ より大きい部分」に分かれ、以後のラウンドで選ばれる元がどちら側にあるかと、各側の中での順序関係で原子論理式の真偽がすべて決まる。したがって、1 ラウンド目で $L_m$ の $a$（左側 $p$ 個・右側 $q$ 個）と $L_n$ の $b$（左側 $p^{\prime }$ 個・右側 $q^{\prime }$ 個）が対応したあと、Duplicator が残り $k$ ラウンドで必勝であることは、$G_k(L_p,L_{p^{\prime }})$ と $G_k(L_q,L_{q^{\prime }})$ の両方で必勝であることと同値になる（左右それぞれの必勝戦略を組み合わせればよく、逆にどちらかで負けるなら Spoiler はその側だけで指せばよい）。

(Duplicator 側) $m,n\ge 2t+1$ とする。Spoiler が $L_m$ で左側 $p$、右側 $q$（$p+q=m-1$）の元を選んだとする（$L_n$ 側を選んだ場合も対称）。
- $p<t$ なら、$L_n$ で左側も $p$ 個の元を選ぶ。右側は $m-1-p\ge 2t-p>t$ 個、$n-1-p>t$ 個で、ともに $t$ 以上。
- $q<t$ なら同様に右側の個数をそろえる。
- $p,q\ge t$ なら、$n-1\ge 2t$ より左右とも $t$ 個以上ある元を $L_n$ で選べる。
いずれの場合も左右それぞれが「個数が等しい」か「ともに $t$ 以上」になり、帰納法の仮定から Duplicator が必勝。

(Spoiler 側) $m<n$ かつ $m<2t+1$ とする。Spoiler は $L_n$ で左側の個数が $p=\min (n-1,t)$ である元を選ぶ（右側は $q=n-1-p$）。Duplicator が $L_m$ で左側 $p^{\prime }$、右側 $q^{\prime }$（$p^{\prime }+q^{\prime }=m-1$）の元を選んだとする。
- $p^{\prime }<p$ のとき: $p^{\prime }<p\le t$ なので左側は「個数が異なり、一方が $t$ 未満」。
- $p^{\prime }>p$ のとき: $p=n-1$ だと $p^{\prime }\le m-1<n-1$ に反するので $p=t$。すると $q^{\prime }=m-1-p^{\prime }<m-1-t\le 2t-1-t<t$ で、$q^{\prime }<m-1-t<n-1-t=q$。右側が「個数が異なり、一方が $t$ 未満」。
- $p^{\prime }=p$ のとき: $p=n-1$ は $p^{\prime }\le m-1$ に反するので $p=t$。$q^{\prime }=m-1-t<t$ かつ $q^{\prime }<n-1-t=q$。
いずれも帰納法の仮定から、その側の $k$ ラウンドのゲームで Spoiler が勝つ。よって $G_{k+1}(L_m,L_n)$ は Spoiler の勝ち。$■$

$f(n)$ の決定. 補題を $L_n$ と $L_{n+1}$（$n\ne n+1$）に使うと、$L_n{\equiv }_k{L}_{n+1}⟺n\ge 2^k-1$。したがって $L_n/{\equiv }_k{L}_{n+1}⟺2^k\ge n+2$ で、
$$f(n)=\min \{k:2^k\ge n+2\}=\lceil {\log }_2(n+2)\rceil$$
となる。（例: $f(1)=2$。$\forall x\forall y(x=y)$ が $L_1$ と $L_2$ を区別する。$f(3)=3$。$\exists x(\exists y(y<x)\wedge \exists z(x<z))$ の形の文の深さ 2 では $L_3$ と $L_4$ を区別できない。）

和の計算. $j=n+2$ は $3$ から $102$ まで動く。$\lceil {\log }_{2}j\rceil =r$ となるのは $2^{r-1}<j\le 2^r$ のとき。

個数の合計は $2+4+8+16+32+38=100$ で、和は
$$4+12+32+80+192+266=586$$
である。

$f(n)$ は、$L_n$ と $L_{n+1}$ を量化子の深さ $k$ 以下の文で区別できる最小の $k$ である。これはエーレンフォイヒト・フレッセの定理により、$k$ ラウンドのゲームで複製者が勝てなくなる最小の $k$ に等しい。

有限線形順序についての既知の事実: $m\ne n$ のとき $L_m{\equiv }_k{L}_n$（深さ $k$ 以下の文がすべて一致する）$⟺m,n\ge 2^k-1$。

（根拠: $\min (m,n)<2^k-1$ なら、深さ $k$ の文で長さ $<2^k-1$ の順序の大きさを数えて区別できる。両方 $\ge 2^k-1$ なら、ゲームの各ラウンドで残りの区間を二分する戦略により複製者が勝つ。）

$L_n$ と $L_{n+1}$ は $n\ne n+1$ なので、$L_n{\equiv }_k{L}_{n+1}⟺n\ge 2^k-1$。したがって $f(n)$ は $n<2^k-1$、すなわち $2^k>n+1$ を満たす最小の整数 $k$ で、$f(n)=\lfloor {\log }_2(n+1)\rfloor +1$。

小さい場合の確認: $n=1$ では $k=1$ で $\exists x(x=x)$ は両方で真なので区別できず、$k=2$ の $\exists x\exists y(x<y)$ で区別できるので $f(1)=2$。$n=2$ も $f(2)=2$（$\exists x\exists y\exists z$ は深さ 3 だが、$L_2$ と $L_3$ は深さ 2 の文 $\exists x\forall y(\dots )$ などで区別される。$2^2-1=3>2$ より）。$n=3$ は $f(3)=3$。

和: ${\sum }_{n=1}^{100}f(n)={\sum }_{m=2}^{101}(\lfloor {\log }_{2}m\rfloor +1)$。
- $m=2,3$（2 個）: 1
- $m=4$〜$7$（4 個）: 2
- $m=8$〜$15$（8 個）: 3
- $m=16$〜$31$（16 個）: 4
- $m=32$〜$63$（32 個）: 5
- $m=64$〜$101$（38 個）: 6

個数の合計は $2+4+8+16+32+38=100$。$\lfloor {\log }_{2}m\rfloor$ の和は $2+8+24+64+160+228=486$。$+100$ して $586$。