0
$\begingroup$

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...

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Lord Shark the Unknown Dec 25 '17 at 18:00
  • $\begingroup$ Ah! That makes a lot of sense! $\endgroup$ – Isky Mathews Dec 25 '17 at 18:04
  • $\begingroup$ @LordSharktheUnknown would you like to post the answer to this question officially and close it? $\endgroup$ – Isky Mathews Dec 25 '17 at 18:12
0
$\begingroup$

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.$

$\endgroup$
0
$\begingroup$

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...

$\endgroup$
  • 1
    $\begingroup$ It's common courtesy to invite the user who made the comment to post it as an answer... Or at least give them more than a few minutes to decide if they want to do that. $\endgroup$ – Asaf Karagila Dec 25 '17 at 18:10
  • $\begingroup$ Ah, I genuinely apologise. Give me a second. $\endgroup$ – Isky Mathews Dec 25 '17 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.