Goodsteins theorem
en.wikipedia.org
en.wikipedia.org
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_...
[1] https://codegolf.stackexchange.com/questions/6430/shortest-t...
I'm wondering if there is some deeper sense in this Patcail's predecessor function? Are there some follow up research on that?
We first compute s' = P(s) = P([0,0]) = 0. Then in [s',t] = [0,0] we must replace all occurrences of 0 with [0,0], which results in [[0,0],[0,0]]. This is a one-time substitution (else it would never end).
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...
> 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.
The main issue is that first order logic can't define the concept of finite. There is no way for a first order system to express a statement like "There are only finitely many x such that P(x) holds." Introducing such a finite quantifier or finite predicate will also introduce inconsistencies.
If it were possible then one could introduce an axiom along the lines of "For all x, x has a finite number of predecessors." and then we could eliminate all non-standard natural numbers.
> There is no largest natural number to begin with even in the standard model.
I'm aware of that. I get Peano Arithmetic more of less.
> One way to conceptualize non-standard natural numbers would be to consider natural numbers with an infinite number of digits. Any such number would be greater than any natural number, and no first order model of arithmetic can exclude every possible way to express such numbers.
I'm not sure you can argue such a number is "greater" than any natural number? They seem incomparable.
I've always found the provable vs true comparison confusing. How can we say the statement is true under the standard model if we cannot prove it? I understand that it could be true, but how do we know it? If it's proven with second order arithmetic, then this implies it is true under the standard model too?
Or are there statements true independently of the axiomatic system you use to prove them? (Apologies if this is too off-topic)
Let’s assume the Natural Numbers are consistent system. Let’s collect all true statements in this system and use that collection as our axioms. It is now the case that every true statement about the Natural Numbers can be proven in this system. The problem with this system of axioms is that there is no effective procedure for determining if a statement is an axiom or not. It is not a useful system.
Every true statement can be proven in some system. The incompleteness theorems show that we can’t have a relatively simple set of axioms that are powerful enough to prove all true statements about the Natural Numbers. Every simple enough set of axioms for the Natural Numbers will have nonstandard implementations (models) in which some statements are false in these nonstandard models but true in the Natural Numbers.
(Not to be confused with Godel's incompleteness theorems)
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.
I think that is the difference between science and engineering. Science strives for the ultimate truth while engineering cares about useful stuff.
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.
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.
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.
When they have the latter in mind, they call it second order arithmetic (or Z2), rather than Peano arithmetic (or PA) [1].
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.
But there is such a page. It redirects to https://en.wikipedia.org/wiki/Peano_axioms#Peano_arithmetic_... .
Anyway, updated the link on the Goodstein's Theorem page to point to that section specifically.
> The ninth, final axiom is a second-order statement of the principle of mathematical induction over the natural numbers, which makes this formulation close to second-order arithmetic. A weaker first-order system called Peano arithmetic is obtained by explicitly adding the addition and multiplication operation symbols and replacing the second-order induction axiom with a first-order axiom schema.
Moreover, non-logicians don't talk about "first-order" or "second-order" logic at all. They just express the induction axiom in plain English, and in this case it is (as Stewart Shapiro argued) equivalent to the second-order axiom.
Also, Wikipedia articles can have multiple authors.