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

$\mathcal{M}=(A,g,S)$ で $\phi$ の 3 つの連言肢がそれぞれ何を意味するかを読み取る。

第 1 の連言肢 $\forall x(f(f(x))=x)$ は、すべての $a\in A$ で $g(g(a))=a$、すなわち $g$ が対合であることを意味する。対合は全単射であり、$A$ は $g$ の不動点（$g(a)=a$）と互換 $\{a,b\}$（$a\ne b$, $g(a)=b$, $g(b)=a$）に分かれる。

第 2 の連言肢 $\forall x(f(x)=x\to P(x))$ は、$g$ の不動点はすべて $S$ に属することを意味する。

第 3 の連言肢 $\forall x(P(x)\wedge P(f(x))\to f(x)=x)$ を場合分けして読む。
- $a$ が不動点のとき：結論 $g(a)=a$ が成り立つので、条件は自動的に満たされる。
- $a$ が互換 $\{a,b\}$ に属するとき：$g(a)=b\ne a$ なので、$a\in S$ かつ $b\in S$ となってはいけない。

したがって $\mathcal{M}\models \phi$ となるのは、次の条件がすべて成り立つときであり、そのときに限る。
- $g$ は対合である。
- $g$ の不動点はすべて $S$ に属する。
- $g$ の各互換 $\{a,b\}$ について、$a,b$ の両方が $S$ に属することはない。

数え上げ

対合 $g$ を 1 つ固定し、互換の個数を $m$ とする。不動点が $S$ に属するかどうかは決まっている。各互換 $\{a,b\}$ については、$S$ との共通部分が $\varnothing ,\{a\},\{b\}$ の 3 通りが許される。よって $S$ の選び方は $3^m$ 通りある。

$A$（6 元）上の対合を互換の個数 $m$ で分類すると、次のようになる。
- $m=0$（恒等写像）：$1$ 個
- $m=1$：$\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ 個
- $m=2$：互換に使う 4 元の選び方が $\left(\genfrac{}{}{0ex}{}{6}{4}\right)=15$ 通り、その 4 元を 2 組に分ける方法が $3$ 通りなので、$15\cdot 3=45$ 個
- $m=3$：6 元を 3 組に分ける方法で、$5\cdot 3\cdot 1=15$ 個

（検算：$1+15+45+15=76$ は 6 元集合上の対合の総数と一致する。）

したがって求める個数は
$$1\cdot 3^0+15\cdot 3^1+45\cdot 3^2+15\cdot 3^3=1+45+405+405=856.$$

第1の文より $g$ は $g\circ g=\mathrm{id}$ をみたす写像、すなわち恒等写像または互換の積で表される対合である。第2の文より、$g$ の不動点はすべて $S$ に属する。第3の文は、$g(x)\ne x$ となる $x$ については $x\in S$ かつ $g(x)\in S$ とはならないことを意味する（$g(x)=x$ のときは結論が成り立つので制約にならない）。

したがって、$g$ が $k$ 個の 2-サイクルをもつとき、次のように $S$ の選び方が決まる。
- 不動点は $S$ に入るので、選択の余地は 1 通り。
- 各 2-サイクル $\{x,y\}$ では、「どちらも $S$ に入らない」「$x$ だけ入る」「$y$ だけ入る」の 3 通り。

よって $S$ の選び方は $3^k$ 通りである。

$A$ の要素数 6 の上で $k$ 個の 2-サイクルをもつ対合の個数は $\frac{6!}{2^{k}k!(6-2k)!}$ である。
- $k=0$: 1
- $k=1$: 15
- $k=2$: 45
- $k=3$: 15

求める個数は
$$1\cdot 1+15\cdot 3+45\cdot 9+15\cdot 27=1+45+405+405=856.$$

検算として、対合の総数 $1+15+45+15=76$ は 6 点上の対合の個数として正しい。