سوال ۱۱۵ کنکور ارشد علوم کامپیوتر ۱۴۰۱

Both statements are classical facts of ordinal arithmetic.

Statement (a): $\omega^{\alpha}$ is additively indecomposable

We must show that whenever $\beta,\beta' < \omega^{\alpha}$ then $\beta' + \beta < \omega^{\alpha}$. The ordinals with this closure-under-addition property are exactly the additively indecomposable ordinals, and these are precisely the powers $\omega^{\alpha}$.

Use the Cantor normal form: every ordinal $\gamma < \omega^{\alpha}$ can be written as $\gamma = \omega^{\gamma_1}c_1 + \cdots + \omega^{\gamma_k}c_k, \qquad \alpha > \gamma_1 > \cdots > \gamma_k,$ so its leading exponent $\gamma_1$ is strictly less than $\alpha$. Take any $\beta,\beta' < \omega^{\alpha}$ with leading exponents $e,e' < \alpha$ and let $\mu = \max(e,e') < \alpha$. When we add $\beta' + \beta$, ordinal addition absorbs all terms of $\beta'$ whose exponent is below the leading exponent of $\beta$, and the leading exponent of the sum is $\max(e',e)=\mu$. Hence $\beta' + \beta < \omega^{\mu+1} \le \omega^{\alpha},$ because $\mu < \alpha \Rightarrow \mu + 1 \le \alpha$. Therefore $\omega^{\alpha} > \beta' + \beta$.

(The edge case $\alpha = 0$ also works: $\omega^{0}=1$, the only ordinal below it is $0$, and $0+0 = 0 < 1$.)

So (a) is true.

Statement (b): limit ordinals are unbounded

Given any ordinal $\alpha$, the ordinal $\beta = \alpha + \omega$ is a limit ordinal (it has no immediate predecessor: every $\delta < \alpha+\omega$ equals $\alpha+n$ for some finite $n$, and $\alpha+n+1$ is still $< \alpha+\omega$), and clearly $\beta = \alpha+\omega > \alpha$. Thus a strictly larger limit ordinal always exists; the limit ordinals form a proper class cofinal in the ordinals.

So (b) is true.

Both (a) and (b) hold, so the answer is Both.

Exam trick: Memorize that the additively indecomposable ordinals are exactly $\{\omega^{\alpha}\}$ (closed under $+$ below), and that both limit ordinals and powers $\omega^{\alpha}$ are unbounded — so any "does there exist a bigger limit ordinal?" question is automatically yes.