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

方針. 量化子の深さ $k$ の型（Hintikka 型）を使う。${\mathrm{tp}}_k(\bar{a})$ を、$\mathrm{qr}\le k$ の論理式のうち $\bar{a}$ が満たすものの全体とする。言語は有限なので、$\mathrm{qr}\le k$ の論理式は同値なものを除けば有限個しかない。このため次が成り立つ。

• ${\mathrm{tp}}_{k+1}(\bar{a})$ は、$\bar{a}$ の量化子なしの型と、集合 $\{{\mathrm{tp}}_k(\bar{a},b)\mid b\in A\}$ とで決まる。
• $\mathcal{A}{\equiv }_3\mathcal{B}$ となるのは、実現される ${\mathrm{tp}}_2(a)$（$a$ は 1 元）の集合が両者で一致するときに限る。

記号. 同値類の大きさを、1、2、3 以上の 3 種類に分けて考える。大きさ 1 の類の個数を $n_1$、大きさ 2 の類の個数を $n_2$、大きさ 3 以上の類の個数を $n_3$ とおき、$q=n_2+n_3$、$m=n_1+q$（類の総数）とする。

深さ 1 の型 ${\mathrm{tp}}_1(a,b)$. これは $(a,b)$ の量化子なしの型と、3 つ組 $(a,b,c)$ の量化子なしの型として何が実現されるかで決まる。
- $a=b$ のとき：$c$ について実現される可能性があるのは「$c=a$」「$c\ne a$ かつ $Eca$」「$\neg Eca$」である。得られる情報は $|[a]|\ge 2$ かどうかと、$m\ge 2$ かどうか。
- $a\ne b$ かつ $Eab$ のとき：得られる情報は $|[a]|\ge 3$ かどうか（$c\notin \{a,b\}$ かつ $Eca$ となる $c$ があるか）と、$m\ge 2$ かどうか。
- $\neg Eab$ のとき：得られる情報は $|[a]|\ge 2$ かどうか、$|[b]|\ge 2$ かどうか、そして $m\ge 3$ かどうか（$a$ とも $b$ とも同値でない $c$ があるか）。

深さ 2 の型 ${\mathrm{tp}}_2(a)$. 上の結果を $b$ について集めると、${\mathrm{tp}}_2(a)$ は次の 3 つで決まる。
- $t(a)$：$[a]$ の大きさを $1,2,3^{+}$ に切り詰めたもの
- $S(a)\subseteq \{1,2^{+}\}$：$[a]$ 以外の類の大きさを $1,2^{+}$ に切り詰めたものとして現れる値の集合
- $N=[m\ge 3]$：$S(a)\ne \varnothing$ のときだけ読み取れる

この 3 つを $(n_1,n_2,n_3)$ で書くと次のようになる。
- $t=1$ の型（$n_1>0$ のとき現れる）：$1\in S⟺n_1\ge 2$、$2^{+}\in S⟺q\ge 1$
- $t=2$ の型（$n_2>0$ のとき現れる）と $t=3^{+}$ の型（$n_3>0$ のとき現れる）：$1\in S⟺n_1\ge 1$、$2^{+}\in S⟺q\ge 2$

不変量. 実現される型の集合からは、次の量が過不足なく読み取れる。
- どの $t$ が現れるか。つまり $[n_1>0],[n_2>0],[n_3>0]$
- $[n_1\ge 2]$（$t=1$ の型から）
- $[q\ge 2]$（$t=2$ または $3^{+}$ の型から）
- $N=[m\ge 3]$

逆に、これらの量から型の集合が決まる。よって ${\equiv }_3$ の類は、次の組と 1 対 1 に対応する。
$$(\min (n_1,2),[n_2>0],[n_3>0],\min (q,2),[m\ge 3])$$

数え上げ. $n_1^{\prime }=\min (n_1,2)\in \{0,1,2\}$ とする。$([n_2>0],[n_3>0],\min (q,2))$ の可能性は、$q=0$ のとき 1 通り、$q=1$ のとき 2 通り、$q\ge 2$ のとき 3 通りで、合わせて 6 通りある。

$[m\ge 3]$ がこれらから決まらないのは、次の 2 つの場合だけである。
- $n_1^{\prime }=2,q=0$：$n_1=2$ と $n_1\ge 3$ が区別される。
- $n_1^{\prime }=0,\min (q,2)=2$：$q=2$ と $q\ge 3$ が区別される。これが 3 通りある。

空構造（$n_1^{\prime }=0,q=0$）は除く。よって類の個数は
$$3\cdot 6+1+3-1=21$$
である。

代表元による確認. 類の大きさの多重集合で代表元を書く。
- $n_1^{\prime }=0$：$\{2\},\{3\}$；$\{2,2\},\{2,2,2\},\{3,3\},\{3,3,3\},\{2,3\},\{2,2,3\}$ の 8 個
- $n_1^{\prime }=1$：$\{1\},\{1,2\},\{1,3\},\{1,2,2\},\{1,3,3\},\{1,2,3\}$ の 6 個
- $n_1^{\prime }=2$：$\{1,1\},\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,1,2,2\},\{1,1,3,3\},\{1,1,2,3\}$ の 7 個

合計 21 個で、上の計算と一致する。

答え：$21$

有限同値構造は同値類の大きさの多重集合 $M$ で決まる。ゲーム（Ehrenfeucht–Fraïssé ゲーム）の残りラウンド数を $r$ として、$r$ ラウンドでの $M$ の型 $U_r(M)$ を再帰的に数える。

【型の定義】すでに選んだ元が属さない類（未選択類）の多重集合 $M$ について、次のように定める。
- $U_r(M)$ は、$M$ の各類 $s$ を選んだときの組 $(\min (s-1,r-1),U_{r-1}(M\setminus \{s\}))$ の集合である。
- 選択済みの類の残りの元の個数は $r$ で打ち切って考える。

【$U_1$】$M$ が空かどうかだけで決まる。

【$U_2$】類の大きさを「小」（大きさ1）と「大」（大きさ2以上）に分ける。$M$ は次の6つの型のどれかになる。
- 空
- 類が1つで小
- 類が1つで大
- 類が2つ以上ですべて小
- 類が2つ以上ですべて大
- 類が2つ以上で小と大が混在

これは (小の個数, 大の個数) を 2 で打ち切った値で決まる。

【$U_3$】類を大きさ 1 (a)、2 (b)、3以上 (c) に分け、それぞれの個数を $n_a,n_b,n_c$、$n_{big}=n_b+n_c$ とする。$f(x,y)$ を「小 $x$ 個・大 $y$ 個の多重集合の $U_2$ 型」とすると、$U_3(M)$ は次の組の集合である。
- $n_a\ge 1$ なら $(a,f(n_a-1,n_{big}))$
- $n_b\ge 1$ なら $(b,f(n_a,n_{big}-1))$
- $n_c\ge 1$ なら $(c,f(n_a,n_{big}-1))$

$f$ の6つの値は次の通り。
- $(0,0)$
- $(1,0)$
- $(0,1)$
- $(\ge 2,0)$
- $(0,\ge 2)$
- $(\ge 1,\ge 1)$

【数え上げ】$n_a$ の有無と、b・c の有無 $(p_b,p_c)$ で分ける。

(i) $n_a=0$ のとき
- $(p_b,p_c)=(1,0)$：$n_{big}=1,2,3+$ で 3 通り
- $(0,1)$：3 通り
- $(1,1)$：$n_{big}=2$ と $3+$ で 2 通り
- 計 8 通り

(ii) $n_a\ge 1$ のとき
- b・c なし：$n_a=1,2,3+$ で 3 通り
- $(1,0)$ と $(0,1)$：それぞれ 4 通り（$n_a=1$ で $n_{big}=1$ と $\ge 2$ の 2 通り、$n_a\ge 2$ で $n_{big}=1$ と $\ge 2$ の 2 通り。$n_a=2$ と $3+$ は同じ型になる）
- $(1,1)$：2 通り
- 計 $3+4+4+2=13$ 通り

合計は $8+13=21$ である。

【確認】大きさ 3 と 4 の類は 3 ラウンドでは区別できない（4 つの異なる元を選ぶには 4 ラウンド必要）ため、c を「3以上」にまとめたのは妥当である。また $a$ の有無で型が異なるので、(i) と (ii) の型は重ならない。