8 ms·

Goodsteins theorem

83 points by dedalus 3y ago

DeathArrow 3y ago
>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.
- p-e-w 3y ago
  We don't want perfect systems but useful ones. A perfect axiom system wouldn't have true but unprovable statements either, yet, as we learned a while ago, any such "perfect" system would be unable to express even basic arithmetic.
  - DeathArrow 3y ago
    >We don't want perfect systems but useful ones. I think that is the difference between science and engineering. Science strives for the ultimate truth while engineering cares about useful stuff.
    - p-e-w 3y ago
      During the past century, it has been demonstrated again and again that the "ultimate truth" either doesn't exist or cannot be attained (Incompleteness Theorem, Uncertainty Principle, Observable Universe, not to mention a million philosophical and psychological problems). If that is what science strives for, it's a lost cause. Fortunately, lots of valuable things can be achieved without chasing such lofty, unattainable goals.
      - baq 3y ago
        Actually… reaching the very limits of knowability is the crown achievement of science and your first two examples have very important engineering implications. Given these economies, perhaps it makes sense to say wherever in science we aren’t at the boundary of knowable, there’s still something worth discovering.
      - Karellen 3y ago
        If "ultimate truth" cannot be attained, but can be asymptotically approached, is striving for it still a lost cause if the knowledge gained in the approach might be useful? I'll never be able to run a marathon as fast as Eliud Kipchoge. That doesn't mean it's a lost cause for me to try to get my marathon time as close to his as possible - I can still achieve valuable things despite the goal being lofty and unattainable. Further, I might achieve more through chasing an unattainable goal, than I would if I'd set my sights lower. It's also worth remembering the aphorism that people saying: “It can’t be done,” are always being interrupted by somebody doing it.
        lanstin 3y ago
        Ones reach should exceed one’s grasp, else what’s a heaven for.
      - klyrs 3y ago
        I disagree strongly with your reading of those results. Each says that the "ultimate truth" is complicated -- that not every question has an easy answer. That doesn't say there isn't an ultimate truth, just "that question cannot be answered" is the ultimate truth. Exploring the bounds of knowability is incredibly important to the dual side of science; exploring the bounds of knowledge. In my lofty opinion, the very purpose of humanity is to bring these bounds together.
Tazerenix 3y ago
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_arithmetic https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet...
- theteapot 3y ago
  Quote from linked page: > The existence of non-standard models of arithmetic can be demonstrated by an application of the compactness theorem. To do this, a set of axioms P* is defined in a language including the language of Peano arithmetic together with a new constant symbol x. The axioms consist of the axioms of Peano arithmetic P together with another infinite set of axioms: for each numeral n, the axiom x > n is included. Any finite subset of these axioms is satisfied by a model that is the standard model of arithmetic plus the constant x interpreted as some number larger than any numeral mentioned in the finite subset of P. Thus by the compactness theorem there is a model satisfying all the axioms P. Since any model of P* is a model of P (since a model of a set of axioms is obviously also a model of any subset of that set of axioms), we have that our extended model is also a model of the Peano axioms. The element of this model corresponding to x cannot be a standard number, because as indicated it is larger than any standard number. So basically take Peano arithmetic and say "Hey Peano Arithmetic, what's the largest number you have? Oh n you say? well exists x > n. Haha". Seems like childish game.
  - anvuong 3y ago
    It's philosophical. It's either turtle all the way down or the axiomatic systems. With axiomatic systems you'll always get things like this, and this is what keeps mathematician awake at night.
    - 3y ago
tromp 3y ago
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_function https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE_... [2] https://oeis.org/A367433 https://oeis.org/A367433
- Sharlin 3y ago
  Worth noting that this sequence was introduced, of all places, as an answer to a codegolf.stackexchange question in 2021! https://codegolf.stackexchange.com/a/219466 https://codegolf.stackexchange.com/a/219466
  - tromp 3y ago
    Indeed; a lot of gems are to be found there. Like this 49 bit program to exceed Graham's Number [1]. [1] https://codegolf.stackexchange.com/questions/6430/shortest-terminating-program-whose-output-size-exceeds-grahams-number/263884#263884 https://codegolf.stackexchange.com/questions/6430/shortest-t...
- dandanua 3y ago
  This function is almost like in the definition of middle-growing hierarchy https://googology.fandom.com/wiki/Middle-growing_hierarchy https://googology.fandom.com/wiki/Middle-growing_hierarchy But this hierarchy can be defined for any ordinal with a system of notations. I'm wondering if there is some deeper sense in this Patcail's predecessor function? Are there some follow up research on that?
- wruza 3y ago
cubefox 3y ago
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.
- tromp 3y ago
  > When ordinary mathematicians talk about "Peano arithmetic", they arguably have the second-order induction axiom in mind When they have the latter in mind, they call it second order arithmetic (or Z2), rather than Peano arithmetic (or PA) [1]. [1] https://en.wikipedia.org/wiki/Second-order_arithmetic https://en.wikipedia.org/wiki/Second-order_arithmetic
  - daxfohl 3y ago
    The link to "Peano arithmetic" at the top of the Goodstein page takes you to Peano axioms page. That page says Peano axioms are "close to" second-order arithmetic, and it also provides an informal distinction between Peano axioms and Peano arithmetic. But there's no wikipedia page for Peano arithmetic. So I'm curious if this theorem is unprovable in Peano axioms, or just Peano arithmetic. If the latter, then the link at the top of the Goodstein page is rather misleading, unless you're paying close enough attention to notice the blurb about the distinction between Peano axioms and Peano arithmetic.
    - thaumasiotes 3y ago
      > But there's no wikipedia page for Peano arithmetic. But there is such a page. It redirects to https://en.wikipedia.org/wiki/Peano_axioms#Peano_arithmetic_as_first-order_theory https://en.wikipedia.org/wiki/Peano_axioms#Peano_arithmetic_... .
ConnorMooneyhan 3y ago
I remember this being shown on PBS Infinite Series. God I miss that show.
- ykonstant 3y ago
  Kelsey has a new channel on YouTube called Chalk Talk. It got some traction with a few lovely videos, but it's been some time since she maade one. I suspect there is a funding issue. https://www.youtube.com/@chalktalkmath https://www.youtube.com/@chalktalkmath

83 points by dedalus 3y ago

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

p-e-w 3y ago
We don't want perfect systems but useful ones. A perfect axiom system wouldn't have true but unprovable statements either, yet, as we learned a while ago, any such "perfect" system would be unable to express even basic arithmetic.
- DeathArrow 3y ago
  >We don't want perfect systems but useful ones. I think that is the difference between science and engineering. Science strives for the ultimate truth while engineering cares about useful stuff.
  - p-e-w 3y ago
    During the past century, it has been demonstrated again and again that the "ultimate truth" either doesn't exist or cannot be attained (Incompleteness Theorem, Uncertainty Principle, Observable Universe, not to mention a million philosophical and psychological problems). If that is what science strives for, it's a lost cause. Fortunately, lots of valuable things can be achieved without chasing such lofty, unattainable goals.
    - baq 3y ago
      Actually… reaching the very limits of knowability is the crown achievement of science and your first two examples have very important engineering implications. Given these economies, perhaps it makes sense to say wherever in science we aren’t at the boundary of knowable, there’s still something worth discovering.
    - Karellen 3y ago
      If "ultimate truth" cannot be attained, but can be asymptotically approached, is striving for it still a lost cause if the knowledge gained in the approach might be useful? I'll never be able to run a marathon as fast as Eliud Kipchoge. That doesn't mean it's a lost cause for me to try to get my marathon time as close to his as possible - I can still achieve valuable things despite the goal being lofty and unattainable. Further, I might achieve more through chasing an unattainable goal, than I would if I'd set my sights lower. It's also worth remembering the aphorism that people saying: “It can’t be done,” are always being interrupted by somebody doing it.
      - lanstin 3y ago
        Ones reach should exceed one’s grasp, else what’s a heaven for.
    - klyrs 3y ago
      I disagree strongly with your reading of those results. Each says that the "ultimate truth" is complicated -- that not every question has an easy answer. That doesn't say there isn't an ultimate truth, just "that question cannot be answered" is the ultimate truth. Exploring the bounds of knowability is incredibly important to the dual side of science; exploring the bounds of knowledge. In my lofty opinion, the very purpose of humanity is to bring these bounds together.

Tazerenix 3y ago

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_arithmetic https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet...

theteapot 3y ago
Quote from linked page: > The existence of non-standard models of arithmetic can be demonstrated by an application of the compactness theorem. To do this, a set of axioms P* is defined in a language including the language of Peano arithmetic together with a new constant symbol x. The axioms consist of the axioms of Peano arithmetic P together with another infinite set of axioms: for each numeral n, the axiom x > n is included. Any finite subset of these axioms is satisfied by a model that is the standard model of arithmetic plus the constant x interpreted as some number larger than any numeral mentioned in the finite subset of P. Thus by the compactness theorem there is a model satisfying all the axioms P. Since any model of P* is a model of P (since a model of a set of axioms is obviously also a model of any subset of that set of axioms), we have that our extended model is also a model of the Peano axioms. The element of this model corresponding to x cannot be a standard number, because as indicated it is larger than any standard number. So basically take Peano arithmetic and say "Hey Peano Arithmetic, what's the largest number you have? Oh n you say? well exists x > n. Haha". Seems like childish game.
- anvuong 3y ago
  It's philosophical. It's either turtle all the way down or the axiomatic systems. With axiomatic systems you'll always get things like this, and this is what keeps mathematician awake at night.
  - 3y ago

tromp 3y ago

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_function https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE_... [2] https://oeis.org/A367433 https://oeis.org/A367433

Sharlin 3y ago
Worth noting that this sequence was introduced, of all places, as an answer to a codegolf.stackexchange question in 2021! https://codegolf.stackexchange.com/a/219466 https://codegolf.stackexchange.com/a/219466
- tromp 3y ago
  Indeed; a lot of gems are to be found there. Like this 49 bit program to exceed Graham's Number [1]. [1] https://codegolf.stackexchange.com/questions/6430/shortest-terminating-program-whose-output-size-exceeds-grahams-number/263884#263884 https://codegolf.stackexchange.com/questions/6430/shortest-t...
dandanua 3y ago
This function is almost like in the definition of middle-growing hierarchy https://googology.fandom.com/wiki/Middle-growing_hierarchy https://googology.fandom.com/wiki/Middle-growing_hierarchy But this hierarchy can be defined for any ordinal with a system of notations. I'm wondering if there is some deeper sense in this Patcail's predecessor function? Are there some follow up research on that?
wruza 3y ago

cubefox 3y ago

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.

tromp 3y ago
> When ordinary mathematicians talk about "Peano arithmetic", they arguably have the second-order induction axiom in mind When they have the latter in mind, they call it second order arithmetic (or Z2), rather than Peano arithmetic (or PA) [1]. [1] https://en.wikipedia.org/wiki/Second-order_arithmetic https://en.wikipedia.org/wiki/Second-order_arithmetic
- daxfohl 3y ago
  The link to "Peano arithmetic" at the top of the Goodstein page takes you to Peano axioms page. That page says Peano axioms are "close to" second-order arithmetic, and it also provides an informal distinction between Peano axioms and Peano arithmetic. But there's no wikipedia page for Peano arithmetic. So I'm curious if this theorem is unprovable in Peano axioms, or just Peano arithmetic. If the latter, then the link at the top of the Goodstein page is rather misleading, unless you're paying close enough attention to notice the blurb about the distinction between Peano axioms and Peano arithmetic.
  - thaumasiotes 3y ago
    > But there's no wikipedia page for Peano arithmetic. But there is such a page. It redirects to https://en.wikipedia.org/wiki/Peano_axioms#Peano_arithmetic_as_first-order_theory https://en.wikipedia.org/wiki/Peano_axioms#Peano_arithmetic_... .

ConnorMooneyhan 3y ago

I remember this being shown on PBS Infinite Series. God I miss that show.

ykonstant 3y ago
Kelsey has a new channel on YouTube called Chalk Talk. It got some traction with a few lovely videos, but it's been some time since she maade one. I suspect there is a funding issue. https://www.youtube.com/@chalktalkmath https://www.youtube.com/@chalktalkmath