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

1. $\alpha$ のカントール標準形を求める。 $\mu ={\omega }^2+\omega \cdot 2+3$ とおく。左分配法則 $\mu \cdot (\xi +\eta )=\mu \cdot \xi +\mu \cdot \eta$ より
$$\alpha =\mu \cdot {\omega }^2+\mu \cdot 4.$$

- $\mu \cdot 4$ について：$3+{\omega }^2={\omega }^2$ なので
$$\mu +\mu ={\omega }^2+\omega \cdot 2+(3+{\omega }^2)+\omega \cdot 2+3={\omega }^2\cdot 2+\omega \cdot 2+3.$$
同様にくり返して、$\mu \cdot n={\omega }^2\cdot n+\omega \cdot 2+3$（$n\ge 1$）。特に $\mu \cdot 4={\omega }^2\cdot 4+\omega \cdot 2+3$ である。
- $\mu \cdot \omega$ について：$\omega$ は極限順序数なので $\mu \cdot \omega ={\sup }_n\mu \cdot n={\sup }_n({\omega }^2\cdot n+\omega \cdot 2+3)={\omega }^3$ である。よって $\mu \cdot {\omega }^2=(\mu \cdot \omega )\cdot \omega ={\omega }^3\cdot \omega ={\omega }^4$ となる。

したがって
$$\alpha ={\omega }^4+{\omega }^2\cdot 4+\omega \cdot 2+3.$$

2. $\beta +\gamma =\alpha$ となる $\gamma$ を決定する。 $\gamma \ne 0$ とし、そのカントール標準形を $\gamma ={\omega }^e\cdot c+\delta$（$c\ge 1$, $\delta <{\omega }^e$）と書く。$\beta$ も
$$\beta ={\beta }^{\prime }+{\omega }^e\cdot b+{\beta }^{\prime \prime }$$
と分ける。ここで ${\beta }^{\prime }$ は指数が $e$ より大きい項の和、$b\ge 0$、${\beta }^{\prime \prime }<{\omega }^e$ である。${\beta }^{\prime \prime }+{\omega }^e={\omega }^e$ なので
$$\beta +\gamma ={\beta }^{\prime }+{\omega }^e\cdot (b+c)+\delta .$$
右辺はカントール標準形になっている。標準形の一意性から、次の 3 つが必要である。
- $e$ は $\alpha$ に現れる指数である。
- $\alpha$ の ${\omega }^e$ の係数を $a$ とすると $b+c=a$、よって $1\le c\le a$ である。
- $\delta$ は $\alpha$ の指数 $e$ 未満の部分に一致する。

逆に、このような $e,c$ に対しては、$\beta =(\alpha \text{ の指数が }e\text{ より大きい部分})+{\omega }^e\cdot (a-c)$ とおけば $\beta +\gamma =\alpha$ が成り立つ。

よって $0$ でない $\gamma$ は、$\alpha$ の各項 ${\omega }^e\cdot a$ について $c=1,\dots ,a$ の $a$ 通りずつあり、それらはすべて相異なる。これに $\gamma =0$（$\beta =\alpha$）を加える。

3. 数える。 係数は $1,4,2,3$ なので、個数は $1+(1+4+2+3)=11$ である。

具体的には次の 11 個である。
- $0$
- $1,2,3$
- $\omega +3,\omega \cdot 2+3$
- ${\omega }^2\cdot k+\omega \cdot 2+3(k=1,2,3,4)$
- $\alpha$

答えは $11$ である。

まず $\alpha$ をカントール標準形に直す。$A={\omega }^2+\omega \cdot 2+3$ とおく。$A$ の最高次は ${\omega }^2$ なので、$A\cdot \omega ={\omega }^3$、$A\cdot {\omega }^2={\omega }^4$ である。また自然数 $n$ について $A\cdot n={\omega }^2\cdot n+\omega \cdot 2+3$ となる。右分配律より $A\cdot ({\omega }^2+4)=A\cdot {\omega }^2+A\cdot 4$ なので、
$$\alpha ={\omega }^4+{\omega }^2\cdot 4+\omega \cdot 2+3.$$

次に、$\beta +\gamma =\alpha$ となる $\beta$ が存在する $\gamma$ を調べる。これは $\alpha$ の「終切片」にあたる。標準形 $\alpha ={\omega }^{a_1}{c}_1+\cdots +{\omega }^{a_n}{c}_n$ に対し、$\gamma$ は $\gamma =0$ か、
$$\gamma ={\omega }^{a_k}\cdot d+{\omega }^{a_{k+1}}{c}_{k+1}+\cdots +{\omega }^{a_n}{c}_n(1\le d\le c_k)$$
の形のものに限る。理由は、$\beta$ の側で ${\omega }^{a_k}$ の項が吸収されるからである。たとえば $\omega \cdot 2+3$ に対し $\gamma =\omega +3$ は $\beta ={\omega }^4+{\omega }^2\cdot 4+\omega$ で実現できる。一方 $\gamma =\omega$ は $1+\omega =\omega$ だが、$\beta +\omega =\alpha$ は末尾の $3$ のために成り立たない。

個数を数える。
- $\gamma =0$：1 個
- 末尾が $3$ の部分（$\gamma =1,2,3$）：3 個
- $\omega \cdot d+3$（$d=1,2$）：2 個
- ${\omega }^2\cdot d+\omega \cdot 2+3$（$d=1,\dots ,4$）：4 個
- ${\omega }^4+{\omega }^2\cdot 4+\omega \cdot 2+3=\alpha$：1 個

合計は $1+3+2+4+1=11$ 個である。これは $1+\sum c_i=1+(1+4+2+3)=11$ とも一致する。