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

$f=f^{\mathcal{M}}$ と書く。$a\to f(a)$ に有向辺を引いた有向グラフ（関数グラフ）で考える。自己同型 $\sigma$ は $\sigma \circ f=f\circ \sigma$ を満たすので、この有向グラフのグラフ同型であり、連結成分を連結成分へ、閉路上の点を閉路上の点へ、$a$ の逆像 $f^{-1}(a)$ を $f^{-1}(\sigma (a))$ へ全単射に移す。

連結成分. 表から連結成分は次の 3 つである。
- $X=\{1,\dots ,9\}$：閉路 $1\to 2\to 3\to 1$（長さ $3$）があり、$f^{-1}(1)\setminus \{3\}=\{4,5\}$, $f^{-1}(2)\setminus \{1\}=\{6,7\}$, $f^{-1}(3)\setminus \{2\}=\{8,9\}$。$4,\dots ,9$ の逆像は空。
- $Y_1=\{10,11\}$：$10$ は不動点（長さ $1$ の閉路）、$f(11)=10$、$11$ の逆像は空。
- $Y_2=\{12,13\}$：$12$ は不動点、$f(13)=12$、$13$ の逆像は空。

$X$ は長さ $3$ の閉路を含み、$Y_1,Y_2$ は長さ $1$ の閉路を含むので、$\sigma$ は $X$ を $X$ に移し、$Y_1\cup Y_2$ を $Y_1\cup Y_2$ に移す。したがって
$$|\mathrm{Aut}(\mathcal{M})|=|\mathrm{Aut}(X)|\times |\mathrm{Aut}(Y_1\cup Y_2)|$$
である（$X$ 上と $Y_1\cup Y_2$ 上の自己同型を独立に選んで組み合わせたものがちょうど $\mathrm{Aut}(\mathcal{M})$ になる）。

$\mathrm{Aut}(X)$. $\sigma$ は閉路 $\{1,2,3\}$ をそれ自身に移し、$\sigma (f(a))=f(\sigma (a))$ から閉路上では巡回のずらし $\sigma (1)=k,\sigma (2)=f(k),\sigma (3)=f(f(k))$ の形になる。$k\in \{1,2,3\}$ のどれでもこの条件を満たすので $3$ 通り。

閉路上の値が決まると、各 $v\in \{1,2,3\}$ について閉路外の逆像 $2$ 個（たとえば $\{4,5\}$）を $\sigma (v)$ の閉路外の逆像 $2$ 個へ全単射に移せばよく、それぞれ $2!=2$ 通り。これらの点の逆像は空なので、それ以上の制約はない。よって
$$|\mathrm{Aut}(X)|=3\times 2^3=24.$$

$\mathrm{Aut}(Y_1\cup Y_2)$. $Y_1$ と $Y_2$ はともに「不動点 1 つに逆像 1 点が付いたもの」で互いに同型であり、それぞれの自己同型は恒等写像だけである（不動点は不動点へ、残りの 1 点は残りの 1 点へ移るしかない）。$\sigma$ は $Y_1,Y_2$ をそのままにするか入れ替える（$10\leftrightarrow 12,11\leftrightarrow 13$）かのどちらかで、いずれも条件を満たすので
$$|\mathrm{Aut}(Y_1\cup Y_2)|=1\cdot 1\cdot 2!=2.$$

以上より
$$|\mathrm{Aut}(\mathcal{M})|=24\times 2=48.$$

$f$ を有向グラフ $a\to f(a)$ とみなすと、自己同型は $f$ と可換な全単射である。連結成分に分けて調べる。

成分 I: $1\to 2\to 3\to 1$ の 3-サイクル。$4,5\mapsto 1$、$6,7\mapsto 2$、$8,9\mapsto 3$ なので、サイクルの各点にちょうど 2 個の葉（$f$ の像にならない点）がつく。
成分 II: $10\mapsto 10$（不動点）、$11\mapsto 10$。
成分 III: $12\mapsto 12$（不動点）、$13\mapsto 12$。

自己同型は成分を同型な成分へ写す。成分 II と III は同型で、成分 I はこれらと同型でない（サイクル長が違う）。

• 成分 I の自己同型: サイクルへの制限は $f$ と可換な巡回置換で、サイクルの回転 3 通り。回転を決めると、各サイクル点の 2 個の葉をどう対応させるかは各点で 2 通りなので $2^3=8$。よって $3\times 8=24$。
• 成分 II から II への自己同型: 不動点 $10$ は $10$ に、葉 $11$ は $11$ に写るので 1 通り。III も同様に 1 通り。
• II と III を入れ替えるかどうか: 2 通り。

よって総数は $24\times 2=48$。

検算: 位数の確認として、成分 I の自己同型群は $(\mathbb{Z}/2{)}^3⋊\mathbb{Z}/3$ で位数 24、II と III の入れ替えで位数 2 の積となり、全体は $24\times 2=48$。回転 $1\to 2\to 3\to 1$、$4\to 6\to 8\to 4$、$5\to 7\to 9\to 5$ が実際に $\sigma f=f\sigma$ を満たすことも確認した（例: $\sigma (f(4))=\sigma (1)=2=f(6)=f(\sigma (4))$）。