# Question on proof of Goodstein's Theorem

I recently read the ordinal-based proof of Goodstein's Theorem, saying that all Goodstein sequences do terminate. However, I did not see why the crucial part worked.

To my knowledge, the proof involves the construction of a parallel ordinal sequence to each Goodstein sequence $G(m)(n)$, $P(m)(n)$, so that $\exists G(m)(n)\Longleftrightarrow\exists P(m)(n)$. Each $P(m)(n+1)$ is constructed by replacing each occurrence of $n+1$ in $G(m)(n)$ with $\omega$, so $2^2+2\rightarrow \omega^\omega+\omega$, for example.

The proof then says that since the base-changing aspect of the process going from $G(m)(n)$ doesn't affect the omegas in the corresponding $P(m)(n)$ and then we subtract one from both, the $P(m)(n)$ must become strictly smaller each step. But why is this the case?

If I have some $G(m)(n)$ which is equivalent to $2^2$, with a $P(m)(n)$ thus equal to $\omega^2$, although it is true that $3^3-1<3^3$, is it true that $\omega^2-1<\omega^2$? Is the expression "$\omega^2-1$" even well defined?

Without this strictly decreasing aspect of the $P(m)(n)$ sequence, it is not clear to me how the proof works...

• You reduce the natural number by $1$ not the ordinal: from $2^2$ you go to $2^1+1$, and then $3^1+1$. This is paralleled in the ordinals in going from $\omega^\omega$ to $\omega+1$. – Lord Shark the Unknown Dec 25 '17 at 18:00
• Ah! That makes a lot of sense! – Isky Mathews Dec 25 '17 at 18:04
• @LordSharktheUnknown would you like to post the answer to this question officially and close it? – Isky Mathews Dec 25 '17 at 18:12

Starting with $4=2^2,$ with base $2,$ the next number is obtained by changing the $2$'s to $3$'s and subtracting $1,$ giving $3^3-1,$ with base $3$. But the rules require this to be re-written in base $3$ as $3^2\cdot 2+3^1\cdot 2+2$ before going further. The next number is $4^2\cdot 2+4^1\cdot 2 +1,$ with base $4.$ The corresponding ordinals are $\omega^{\omega},\; \omega^2\cdot 2+\omega\cdot 2+2,\;\omega^2\cdot 2+\omega\cdot 2+1.$
As Lord Shark the Unknown points out, one first reduces the natural number by one and then changes the base, so the example above is resolved by saying $2^2\rightarrow 3^1+1$ and so $\omega^2 \rightarrow \omega+1$. Thus, since the base doesn't affect the ordinal but the subtraction of one leads to the reduction of a non-base integer, then the resulting $P(m)(n+1)<P(m)(n)$ and then the rest of the proof follows...