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

$\sigma$ を $\mathcal{D}$ の自己同型とする。$\sigma$ は整除関係を保つので、各元 $m$ の下集合（$m$ の約数全体）$\{d\in D:d\mid m\}$ を $\sigma (m)$ の下集合に順序同型に写す。

(1) 素数と素数べきの保存。 最小元 $1$ は $1$ に写る。$1$ 以外の約数が自分自身だけである元（原子）は素数なので、$\sigma$ は素数全体を置換する。この置換を $\pi$ とする。また、下集合が鎖（全順序）になる元は $1$ と素数べき $p^k$ に限られる（相異なる素数 $p,q$ がともに $m$ を割り切れば、$p$ と $q$ は比較不能である）。$p^k$ の下集合は長さ $k+1$ の鎖 $1\mid p\mid \cdots \mid p^k$ で、その原子は $p$ である。したがって $\sigma (p^k)=\pi (p{)}^k$ となり、とくに $p$ の $100$ 以下のべきの個数は $\pi$ で保たれる。

(2) $\sigma$ は $\pi$ で決まる。 $m=\prod p^{a_p}$ を素因数分解すると、$m$ を割り切る素数べきは $p^j(j\le a_p)$ である。$\sigma (m)$ を割り切る素数べきはそれらの像 $\pi (p{)}^j$ に限られるので、$\sigma (m)=\prod \pi (p{)}^{a_p}$ である。逆に、素数の置換 $\pi$ からこの式で定めた写像が $D$ を $D$ に写すならば、それは単射であり（素因数分解の一意性）、$D$ が有限なので全単射である。さらに $a\mid b$ は各素数の指数の大小で決まるので、整除関係は両方向に保たれ、自己同型になる。よって、
$$\text{すべての }m\in D\text{ について }\prod \pi (p{)}^{a_p}\le 100(\ast )$$
を満たす素数の置換 $\pi$ の個数を数えればよい。

(3) 小さい素数は固定される。 $100$ 以下のべきの個数は、$2$ が $6$ 個（$2,4,\dots ,64$）、$3$ が $4$ 個（$3,9,27,81$）、$5$ と $7$ が $2$ 個（$5,25$ と $7,49$）、$11$ 以上の素数は $1$ 個である。(1) より $\pi (2)=2$、$\pi (3)=3$ であり、$\pi$ は $\{5,7\}$ と $11$ 以上の素数の集合をそれぞれ保つ。もし $\pi (5)=7$ とすると $80=2^4\cdot 5$ が $2^4\cdot 7=112>100$ に写り $(\ast )$ に反する。よって $\pi (5)=5$、$\pi (7)=7$ である。

(4) 大きい素数の条件。 $p\ge 11$ ならば $p^2>100$ である。また $p,q\ge 11$ ならば $pq\ge 121>100$ である。よって $p$ を含む $m\in D$ は $m=pr$（$r\le \lfloor 100/p\rfloor \le 9$、$r$ の素因数は $2,3,5,7$ のみ）の形をしている。$\pi$ は $2,3,5,7$ を固定するので $\sigma (pr)=\pi (p)r$ となる。したがって $(\ast )$ は「$r\le \lfloor 100/p\rfloor \Rightarrow \pi (p)r\le 100$」、すなわち $\lfloor 100/p\rfloor \le \lfloor 100/\pi (p)\rfloor$ と同値である。${\sigma }^{-1}$ も自己同型なので逆向きの不等式も成り立ち、
$$\lfloor \frac{100}{\pi (p)}\rfloor =\lfloor \frac{100}{p}\rfloor$$
が必要十分条件となる。

(5) 数え上げ。 $11$ 以上の素数を $\lfloor 100/p\rfloor$ の値で分類すると次のようになる。
- $9$: $\{11\}$
- $7$: $\{13\}$
- $5$: $\{17,19\}$
- $4$: $\{23\}$
- $3$: $\{29,31\}$
- $2$: $\{37,41,43,47\}$
- $1$: $\{53,59,61,67,71,73,79,83,89,97\}$（$10$ 個）

$\pi$ は各クラスの中で自由に置換できるので、自己同型の個数は
$$1!\cdot 1!\cdot 2!\cdot 1!\cdot 2!\cdot 4!\cdot 10!=2\cdot 2\cdot 24\cdot 3628800=348364800$$
である。

$\mathcal{D}$ は $\{1,\dots ,100\}$ 上の割り切り順序である。$\mathrm{Aut}(\mathcal{D})$ は順序同型全体であり、次の手順で数える。

1. 自己同型は素数の置換で決まる。
- $1$ は最小元なので固定される。
- 極小元以外の最小の元（素数）は素数に移る。自己同型は階数 $\Omega (n)$（素因数の個数）を保つ。$n$ の被覆関係は $n/p$（$p$ は素因数）である。
- 素数をすべて固定する自己同型は恒等写像である。帰納法で示す。階数が $r$ より小さい元がすべて固定されているとする。$n$ が 2 種類以上の素因数をもつなら、$n$ はその下側被覆 $\{n/p\}$ で一意に決まる。$n$ が素数べき $p^k$ なら、$p$ の上の鎖で決まる。よって $n$ も固定される。
- 以上より、自己同型は素数の置換 $\sigma$ が $\prod p^e\mapsto \prod \sigma (p{)}^e$ と全体に拡張されたものに限る。これが $D$ の全単射になるような $\sigma$ を数えればよい。

2. 入れ替えられる素数を調べる。 各素数 $p$ について、$p$ の倍数（$\le 100$）全体の構造を比べる。
- $2,3,5,7$ は、$p\cdot q\le 100$ となる $q$ の個数がそれぞれ $14,10,7,5$ で異なる。よって固定される。
- $11$ の倍数は 9 個、$13$ の倍数は 7 個で異なる。よって $11,13$ は固定される。
- $23$ は倍数に $92=4\cdot 23$ をもつが、$29,31$ はもたない。よって $23$ は固定される。
- $17,19$ の倍数は、$17a$ と $19a$（$a=1,\dots ,5$）で同じ構造をもつ。入れ替え可能で、$2!$ 通り。
- $29,31$ の倍数は、$29a$ と $31a$（$a=1,2,3$）で同じ構造をもつ。入れ替え可能で、$2!$ 通り。
- $37,41,43,47$ の倍数は、$p$ と $2p$ だけである。互いに入れ替え可能で、$4!$ 通り。
- $53,59,61,67,71,73,79,83,89,97$（10 個）は、倍数が自分自身だけである。自由に置換でき、$10!$ 通り。
- 上の各グループの間では入れ替えられない。倍数の個数や構造が異なるからである。

3. 積を計算する。 個数は $10!\cdot 4!\cdot 2!\cdot 2!=3628800\cdot 24\cdot 4=348364800$。

4. 確認。 各グループの入れ替えで、$\le 100$ の元が $\le 100$ の元に移ることを確認した（例: $17\cdot 5=85$, $19\cdot 5=95$, $29\cdot 3=87$, $31\cdot 3=93$）。いずれも全単射になる。