この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

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

難易度 2大学院の講義の演習問題レベル大学院数学数理論理学・集合論

1 項関数記号 $f$ だけからなる一階の言語を考える。台集合 $A = {1, 2, \dots, 10}$ 上の構造 $M = (A, f^{M})$ を、関数 $f^{M} : A \to A$ の値が次の表で与えられるものとする。

$x$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$f^{M} (x)$	$2$	$1$	$1$	$2$	$6$	$5$	$5$	$6$	$9$	$9$

$M$ の自己同型、すなわち全単射 $σ : A \to A$ であって、すべての $x \in A$ について $σ (f^{M} (x)) = f^{M} (σ (x))$ を満たすものは何個あるか。

この問題で使うもの

有限構造の自己同型の個数（説明と入口の問題）

この問題を解けるようになるまで（25 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$f$ を有向辺 $x \to f (x)$ とみたグラフ（関数グラフ）を描き、連結成分に分けよう。自己同型は周期点を同じ周期の周期点に写す。

ヒント 2

不動点は $9$ だけなので $9$ と $10$ は動かせない。周期 2 の点 ${1, 2, 5, 6}$ の上では、 $σ$ は置換 $(12) (56)$ と可換でなければならない。

ヒント 3

$(12) (56)$ と可換な ${1, 2, 5, 6}$ の置換を数えよう。そのそれぞれに対し、 $3, 4, 7, 8$ の行き先は $σ (ℓ (y)) = ℓ (σ (y))$ で一意に決まるかを確かめる。

答えと解説

答えを見る

8

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

$f = f^{M}$ と書く。 $f$ を有向辺 $x \to f (x)$ とみると、次の 3 つの連結成分に分かれる。
- 成分 $C_{1}$ ： $2$ 周期 $1 \leftrightarrow 2$ に、 $3 \to 1$ 、 $4 \to 2$ がついたもの
- 成分 $C_{2}$ ： $2$ 周期 $5 \leftrightarrow 6$ に、 $7 \to 5$ 、 $8 \to 6$ がついたもの
- 成分 $C_{3}$ ：不動点 $9$ に、 $10 \to 9$ がついたもの

自己同型 $σ$ は $f$ と可換なので、 $f^{k} (x) = x$ ならば $f^{k} (σ (x)) = σ (f^{k} (x)) = σ (x)$ となり、周期点を同じ周期の周期点に写す（逆写像 $σ^{- 1}$ も自己同型なので、周期もちょうど保たれる）。

$9, 10$ の行き先　不動点（ $f (x) = x$ となる $x$ ）は $9$ だけなので $σ (9) = 9$ 。また $f (10) = 9$ より $f (σ (10)) = σ (9) = 9$ なので $σ (10) \in f^{- 1} (9) = {9, 10}$ 、 $σ$ は単射だから $σ (10) = 10$ 。

周期 $2$ の点　周期 $2$ の点は ${1, 2, 5, 6}$ で、 $σ$ はこの集合の置換を引き起こし、その上で $f$ は置換 $τ = (12) (56)$ として働く。 $σ$ の制限 $π$ は $π τ = τ π$ を満たす必要がある。これは「 $τ$ の 2 つの互換 ${1, 2}, {5, 6}$ を互換ごとに写す」ことと同じで、そのような $π$ は
- 2 つの互換を入れ替えるか否か： $2$ 通り
- 各互換をどちらの向きに写すか： $2 \times 2 = 4$ 通り

の計 $2 \times 4 = 8$ 個ある（ $S_{4}$ における $τ$ の中心化群の位数 $= 4! /3 = 8$ とも一致する。 $τ$ の共役類は $(2, 2)$ 型の 3 個）。

残りの点 $3, 4, 7, 8$ 　各周期 2 の点 $y$ に対し、 $f (x) = y$ となる周期点でない $x$ はちょうど 1 個ある（ $1$ には $3$ 、 $2$ には $4$ 、 $5$ には $7$ 、 $6$ には $8$ ）。これを $ℓ (y)$ とおくと、 $σ$ は周期点でない点を周期点でない点に写すので、 $f (σ (ℓ (y))) = σ (y)$ より $σ (ℓ (y)) = ℓ (σ (y))$ と一意に決まる。逆に $π$ を上の 8 個のどれにとっても、このように定めた $σ$ は全単射で $f$ と可換になる（ $9, 10$ は固定、周期点上では $π τ = τ π$ 、 $ℓ (y)$ では $σ (f (ℓ (y))) = π (y) = f (ℓ (π (y))) = f (σ (ℓ (y)))$ ）。

よって自己同型の個数は $8$ 。

別解

関数グラフ（ $x \to f (x)$ ）の連結成分に分けて調べる。

成分 $P$ : 2 点の閉路 $1 \leftrightarrow 2$ （ $f (1) = 2, f (2) = 1$ ）と、 $3 \to 1$ 、 $4 \to 2$ 。計 4 点。
成分 $Q$ : 2 点の閉路 $5 \leftrightarrow 6$ と、 $7 \to 5$ 、 $8 \to 6$ 。計 4 点。 $P$ と同型（ $1, 2, 3, 4 \mapsto 5, 6, 7, 8$ ）。
成分 $R$ : 不動点 $9$ （ $f (9) = 9$ ）と、 $10 \to 9$ 。計 2 点。

自己同型は関数グラフの自己同型で、連結成分を同型な成分へ写す。 $R$ は $P, Q$ と同型でないので $R$ 自身へ写る。

$R$ の自己同型: 不動点 9 は不動点に写るので $σ (9) = 9$ 、 $σ (10) \in f^{- 1} (9) ∖ {9} = {10}$ 。恒等写像のみで 1 個。
$P$ の自己同型: 閉路の点 $1, 2$ は閉路の点に写る。 $σ (1) = 1$ なら $σ (2) = f (σ (1)) = 2$ 、 $f^{- 1} (1) ∖ {2} = {3}$ より $σ (3) = 3$ 、同様に $σ (4) = 4$ （恒等）。 $σ (1) = 2$ なら $σ (2) = 1$ , $σ (3) = 4, σ (4) = 3$ 。よって 2 個。 $Q$ も同様に 2 個。
$P$ と $Q$ を入れ替える同型は、 $P \to Q$ の同型 2 通りと $Q \to P$ の同型 2 通りの組で $2 \cdot 2 = 4$ 個。

合計: $P, Q$ を保つもの $2 \cdot 2 = 4$ 個、入れ替えるもの $4$ 個、 $R$ 側は 1 通り。よって $4 + 4 = 8$ 個。

検算: 自己同型群は $(Z /2) ≀ S_{2}$ （位数 $2^{2} \cdot 2 = 8$ ）で、一致する。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題