Proving the Weak Goodstein Theorem within $\mathsf{PA}$

Question

In

Cichon, E. A., A short proof of two recently discovered independence results using recursion theoretic methods, Proc. Am. Math. Soc. 87, 704-706 (1983). ZBL0512.03028.

the following process is defined (Weak Goodstein process)

Given a natural number $N$, write it in base $x$ in the traditional way, i.e. as sums of powers of $x$. Increase the base of the representation by $1$, then subtract $1$ from the new number thus obtained. Repeat the procedure of increasing the base by $1$ and subtracting $1$

The Weak Goodstein Theorem states that for any $N$ and $x$ the Weak Goodstein process terminates after finitely many steps. Cichon used the Hardy Hierarchy to prove this, showing in the process that the Weak Goodstein Theorem is in fact a theorem of $\mathsf{PA}$ (which is not the case for either Goodstein's Theorem nor Extended Goodsten's Theorem, although the former can be expressed in $\mathsf{PA}$ but not the latter)

Now, consider the following example: $N=8$ and $x=2$. The first few terms of the weak Goodstein sequence $\{g_{p}(8)\}$ are

(1) $g_{1}(8) = 2^{3}$

(2) $g_{2}(8) = 3^{3}-1 = 2\cdot 3^{2}+2\cdot 3+2 = 26$

(3) $g_{3}(8) = (2\cdot 4^{2}+2\cdot 4+2)-1 = 2\cdot 4^{2}+2\cdot 4+1 = 41$

(4) $g_{4}(8) = (2\cdot 5^{2}+2\cdot 5+1)-1=2\cdot 5^{2}+2\cdot 5 = 60$

$\hspace{1cm}$$\vdots$

(22) $g_{22}(8) = (2\cdot 23^{2}+1)-1=2\cdot 23^{2} = 1058$

It soon becomes apparent that for $p\ge 2$ the general form is $$g_{p}(8) = a_{p}(p+1)^{2}+b_{p}(p+1)+c_{p},$$ where $0\le a_{p}\le 2$, and $0\le b_{p},c_{p}\le p$. It is straightforward to prove this by induction on $p$, as it is preserved when going from $g_{p}(8)$ to $g_{p+1}(8)$ by considering the three different cases ($c_{p}>0$, $c_{p}=0$ & $b_{p}>0$, $c_{p}=b_{0}=0$ & $a_{p}>0$).

Hence, each $p\ge 2$ corresponds uniquely with the triple $(a_{p},b_{p},c_{p})$. The sequence can thus be described using triples and counting becomes easier to visualize: $$\begin{array}{c|c} p & (a_{p},b_{p},c_{p})\\ \hline 2 & (2,2,2)\\ 3 & (2,2,1)\\ 4 & (2,2,0)\\ 5 & (2,1,5)\\ 6 & (2,1,4)\\ \vdots & \vdots\\ 10 & (2,1,0)\\ \vdots & \vdots\\ 22 & (2,0,0)\\ \vdots & \vdots\\ 3\cdot 2^{26}-2 & (1,1,0)\\ \vdots & \vdots\\ 3\cdot 2^{27}-2 & (1,1,0)\\ \vdots & \vdots\\ 3\cdot 2^{26+3\cdot 2^{27}}-2 & (0,1,0)\\ \vdots & \vdots\\ 3\cdot 2^{27+3\cdot 2^{27}}-2 & (0,0,0)\\ \end{array}$$

The counting argument illustrated above is simply a proof in $\mathsf{PA}$ that the sequence $\{g_{p}(8)\}$ terminates: we have shown that to each step $p$ one can assign exactly one triple of the coefficients of the decomposition in base $(p+1)$, and then demonstrated that the triples are well-ordered in a decreasing lexicographic way.

Can this argument be carried out in general to give a proof within $\mathsf{PA}$ of the Weak Goodstein Theorem? That is, assigning to each term $g_{p}(n)$ of a weak Goodstein sequence exactly one $m$-tuple of the coefficients of the decomposition in base $(p+1)$ and then show that the $m$-tuplets satisfy a strictly decreasing lexicographic well-ordering.

More generally, consider Goodstein's Theorem, i.e. involving hereditary base notation and starting at base $2$ (not to be confused with the extended result proven by R.L. Goodstein, which is not even expressible in the language of $\mathsf{PA}$ - see the Wikipedia link above). Why does the tuple argument described above cannot be carried out within $\mathsf{PA}$?

This question is somewhat related.

Answer 1

I spent some time learning about the standard proof of Goodstein theorem using ordinals, and its strength. In order to remove the question from the unanswered list I will give an answer. I would appreciate feedback if my understanding of the concepts is erroneous.

The answer to the first questions is yes, it can be carried out within $\mathsf{PA}$. The process of assigning to each term $g_{p}(n)$ of a weak Goodstein sequence exactly one $m$-tuple of the coefficients of the decomposition in base $(p+1)$ and then showing that the $m$-tuples satisfy a strictly decreasing lexicographic well-ordering is accomplished when we construct a parallel sequence of ordinal numbers in Cantor Normal Form which is strictly decreasing and terminates. This is nothing but the usual proof of Goodstein's Theorem using ordinals applied to weak Goodstein sequences (see for example p.126 in 3.). However, when applied to weak Goodstein sequences this proof is within $\mathsf{PA}$ because all the ordinals produced are strictly bounded by $\omega^{\omega}$. I.e. the process amounts to induction of length $\omega^{\omega}$, which we know to be formalizable in $\mathsf{PA}$. Indeed, Gerhard Gentzen (see 1. and 2.) showed that for any $\alpha<\varepsilon_{0}$, transfinite induction of length $\alpha$ is formalizable in $\mathsf{PA}$ (recall that regular induction is just induction of length $\omega$).

As for the second question, the tuple argument cannot be carried out within in $\mathsf{PA}$ because the process of ordering the tuples produces ordinals which are only strictly bounded by $\varepsilon_{0}$. I.e. the process amounts to induction of length $\varepsilon_{0}$, which Gentzen showed not to be formalizable in $\mathsf{PA}$ (see 1. and 2.)

1. Gentzen, Gerhard, The consistency of arithmetics, Math. Ann. 112, 493-565 (1936). ZBL62.0044.01.

2. Gentzen, Gerhard, Beweisbarkeit und Unbeweisbarkeit von Anfangsfällen der transfiniten Induktion in der reinen Zahlentheorie, Math. Ann. 119, 140-161 (1943). ZBL0028.10201.

3. Hrbacek, Karel; Jech, Thomas, Introduction to set theory, Pure and Applied Mathematics, Marcel Dekker 220. New York, NY: Marcel Dekker (ISBN 0-8247-7915-0/hbk). ix, 291 p. (1999). ZBL1045.03521.