from Hacker News

Goodsteins theorem

by dedalus on 12/23/23, 8:20 PM with 51 comments

by tromp on 12/26/23, 8:48 AM
Another sequence that's about as simple to define as Goodstein's is the following: Start with any binary tree, which is either 0, or a pair [s,t] of binary trees. Then while it's not 0, repeatedly apply the following predecessor operation P on binary trees:
```
    P([0,t]) = t
    P([s,t]) = [P(s),t] but with all instances of t replaced by [P(s),t]
```
For example, starting from [[0,0],0], we have the sequence of predecessor trees
```
    [[0,0],0]
    [[0,0],[0,0]]
    [0,[0,[0,0]]]
    [0,[0,0]]
    [0,0]
    0
```
This sequence grows unbelievably faster than Goodstein's, and even faster than the infamous TREE() function [1], while having an almost trivial definition. The number of predecessors to reach 0 is sequence A367433 in the Online Encyclopedia of Integer Sequences [2].
[1] https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE_...
[2] https://oeis.org/A367433
by Tazerenix on 12/26/23, 8:42 AM
A theorem which is true in every model is provable by Godel's completeness theorem. Since this theorem is true for the standard model of the natural numbers but not provable, it follows there are nonstandard models of the natural numbers for which it is false.
That is, there are models of Peano arithmetic which contain all of the natural numbers we know and love, and some other ones on top of that and there are some Goodstein sequences using those extra "non-standard" natural numbers which do not terminate at zero.
https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet...
by DeathArrow on 12/26/23, 8:08 AM
>Laurence Kirby and Jeff Paris[1] showed that it is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second-order arithmetic). This was the third example of a true statement about natural numbers that is unprovable in Peano arithmetic, after the examples provided by Gödel's incompleteness theorem and Gerhard Gentzen's 1943 direct proof of the unprovability of ε0-induction in Peano arithmetic.
It seems math is never perfect but always perfectible. A perfect system wouldn't have paradoxes. One common example is Russel paradox.
We arrive at different conclusions by choosing a different set of axioms and constructing everything else based on that set. We can have parallels that intersect and parallels that don't.
by ConnorMooneyhan on 12/26/23, 4:40 PM
I remember this being shown on PBS Infinite Series. God I miss that show.
by cubefox on 12/26/23, 10:15 AM
The author of this article writes that the theorem cannot be proven in "Peano arithmetic". But that's only true if by that he means "first-order Peano arithmetic", a system which allows for absurd "non-standard numbers". When ordinary mathematicians talk about "Peano arithmetic", they arguably have the second-order induction axiom in mind, not the first-order infinite induction axiom scheme. And they most certainly have the natural numbers in mind, not some possibly absurd "numbers" with infinitely many predecessors. And in this normal version of Peano arithmetic, the theorem can be proven.