Goodsteins theorem
en.wikipedia.org
Goodsteins theorem
1–10 of 54 posts
Re: Goodsteins theorem
#2>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.
Re: Goodsteins theorem
#3>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 ari…
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.
Re: Goodsteins theorem
#4>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 ari…
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.
>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.
Re: Goodsteins theorem
#5A 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...
Re: Goodsteins theorem
#6Another 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]
[[0,0],0]
[[0,0],[0,0]]
[0,[0,[0,0]]]
[0,[0,0]]
[0,0]
0
[1] https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE_...
Re: Goodsteins theorem
#7A 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…
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.
Re: Goodsteins theorem
#8A 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…
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…
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.
Re: Goodsteins theorem
#9Earlier quoted context omitted.
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.
>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.
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.
Re: Goodsteins theorem
#10The 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.