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

単項式の吸収規則　カントール標準形の単項式について、$a<b$ ならば ${\omega }^{a}c+{\omega }^{b}d={\omega }^{b}d$、$a=b$ ならば ${\omega }^{a}c+{\omega }^{a}d={\omega }^a(c+d)$ が成り立つ（$c,d$ は正の整数）。和の結合法則より、$S_{\sigma }$ は各 ${\alpha }_i$ の標準形の単項式を左から順に並べた和であり、ある単項式 ${\omega }^{a}c$ は、それより右に指数が $a$ より真に大きい単項式があるときに限り消える。残った単項式は指数が単調非増加に並ぶので、同じ指数の係数を足せば $S_{\sigma }$ の標準形が得られる。

以下 $A={\alpha }_1,B={\alpha }_2,C={\alpha }_3,D={\alpha }_4,E={\alpha }_5$ と書く。単項式は
$A:{\omega }^2,1$、$B:\omega \cdot 2,1$、$C:{\omega }^2\cdot 2,\omega$、$D:\omega ,3$、$E:2$
である。$S_{\sigma }={\omega }^{2}p+\omega q+r$ と書く。

${\omega }^2$ の係数 $p$　指数 $2$ が最大なので $A,C$ の ${\omega }^2$ の項は必ず残り、常に $p=1+2=3$。

$\omega$ の係数 $q$　$A,C$ のうち後にあるほうを $M$ とする。指数 $1$ の単項式は $M$ の ${\omega }^2$ の項より後にあるときに限り残る。
- $M=C$（$A$ が $C$ より前）のとき：$C$ 自身の $\omega$ が残り $q=1+2[B\text{ が }C\text{ より後}]+[D\text{ が }C\text{ より後}]$。
- $M=A$（$C$ が $A$ より前）のとき：$C$ の $\omega$ は消え $q=2[B\text{ が }A\text{ より後}]+[D\text{ が }A\text{ より後}]$。
（$[]$ は条件が成り立てば $1$、そうでなければ $0$。）

定数項 $r$　$A,B,C,D$ はどれも指数 $1$ 以上の単項式を含むので、定数項が残るのは「$A,B,C,D$ の中で最後にあるもの $L$」の定数項と、$E$ が全体の最後にあるときの $E$ だけである。$L$ の定数項を $c(L)$ とすると $c(A)=1,c(B)=1,c(C)=0,c(D)=3$ で
$$r=c(L)+2[E\text{ が最後}].$$

$(q,c(L))$ の組の列挙　$A,B,C,D$ の並べ方で場合分けする。
- $M=C$：$B,D$ ともに $C$ より後 → $q=4$、$L\in \{B,D\}$ で $c(L)\in \{1,3\}$。$B$ だけ後 → $q=3$、$L=B$、$c=1$。$D$ だけ後 → $q=2$、$L=D$、$c=3$。どちらも前 → $q=1$、$L=C$、$c=0$。
- $M=A$：$B,D$ ともに $A$ より後 → $q=3$、$c\in \{1,3\}$。$B$ だけ後 → $q=2$、$c=1$。$D$ だけ後 → $q=1$、$c=3$。どちらも前 → $q=0$、$L=A$、$c=1$。

まとめると、各 $q$ に対して現れる $c(L)$ は
$q=4:\{1,3\}$、$q=3:\{1,3\}$、$q=2:\{1,3\}$、$q=1:\{0,3\}$、$q=0:\{1\}$。

$E$ の位置　$E$ を最後に置くかどうかは $A,B,C,D$ の並べ方と独立に選べるので、$r\in \{c,c+2\}$ がともに現れる。ここで $c=1$ に $2$ を足した $3$ が $c=3$ と重なることに注意すると
- $q=4,3,2$：$r\in \{1,3,5\}$ でそれぞれ $3$ 個
- $q=1$：$r\in \{0,2,3,5\}$ で $4$ 個
- $q=0$：$r\in \{1,3\}$ で $2$ 個

$p=3$ は共通なので、相異なる $S_{\sigma }={\omega }^2\cdot 3+\omega q+r$ の個数は $3+3+3+4+2=15$。

（確認例：$A,C,B,D,E$ の順では ${\omega }^2\cdot 3+\omega \cdot 4+5$、$A,B,D,C,E$ の順では ${\omega }^2\cdot 3+\omega +2$ となり、上の規則と一致する。）

よって答えは $15$。

各 ${\alpha }_i$ のカントール標準形は $A={\omega }^2+1$, $B=\omega \cdot 2+1$, $C={\omega }^2\cdot 2+\omega$, $D=\omega +3$, $E=2$ である。和 $x+y$ では、$y$ の最高次の指数より小さい指数の項が $x$ から吸収される。

$A$, $C$ は次数 2、$B$, $D$ は次数 1、$E$ は次数 0 である。並びの中で次数 2 の項のうち最後にくるものを $M\in \{A,C\}$ とする。
- $M$ より前の $B,D,E$ は、$M$ の ${\omega }^2$ に完全に吸収される。
- もう一方の次数 2 の項は ${\omega }^2$ の部分だけが残る。$A$ から ${\omega }^2$、$C$ から ${\omega }^2\cdot 2$ が残り、${\omega }^2$ の係数の合計は常に 3 になる。
- よって $S={\omega }^2\cdot 3+(M\text{ の尾部})+s(T)$ となる。$M=A$ の尾部は $1$、$M=C$ の尾部は $\omega$ である。
- $T$ は $M$ より後ろにある $\{B,D,E\}$ の部分列で、順序つきの選び方が $1+3+6+6=16$ 通りある。$s(T)$ はその和である。

$s(T)$ の値は次のとおり。
- 空列: $0$
- $B$: $\omega 2+1$
- $D$: $\omega +3$
- $E$: $2$
- $BD$: $\omega 3+3$
- $DB$: $\omega 3+1$
- $BE$: $\omega 2+3$
- $EB$: $\omega 2+1$
- $DE$: $\omega +5$
- $ED$: $\omega +3$
- $BDE$: $\omega 3+5$
- $BED$: $\omega 3+3$
- $DBE$: $\omega 3+3$
- $DEB$: $\omega 3+1$
- $EBD$: $\omega 3+3$
- $EDB$: $\omega 3+1$

$M=A$ のとき、尾部 $1+s(T)$ の相異なる値は $\{1,3,\omega +3,\omega +5,\omega 2+1,\omega 2+3,\omega 3+1,\omega 3+3,\omega 3+5\}$ の 9 個。

$M=C$ のとき、尾部 $\omega +s(T)$ の相異なる値は $\{\omega ,\omega +2,\omega 2+3,\omega 2+5,\omega 3+1,\omega 3+3,\omega 4+1,\omega 4+3,\omega 4+5\}$ の 9 個。

両者に共通するのは $\omega 2+3$, $\omega 3+1$, $\omega 3+3$ の 3 個である。

どの $M$, $T$ の組も、$T$ を $M$ の後ろに置き、残りを前に置けば実現できる。また ${\omega }^2\cdot 3$ に尾部を足してもカントール標準形は変わらないので、尾部が異なれば順序数も異なる。

したがって相異なる順序数の個数は $9+9-3=15$ 個である。