Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Goodsteins theorem

en.wikipedia.org

Post reply on HN
Print view View original

41–50 of 54 posts

Re: Goodsteins theorem

#41

Post by lanstin »

Tazerenix wrote: post #5

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…

Is there a cite for that? (About true in all models implies provable?). This post is the first I have heard that but it seems very significant.

Re: Goodsteins theorem

#42

Post by lanstin »

Karellen wrote: post #20
p-e-w wrote: post #9

Earlier quoted context omitted.

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, unattainabl…

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 unattainab…

Ones reach should exceed one’s grasp, else what’s a heaven for.

Re: Goodsteins theorem

#43

Post by klyrs »

p-e-w wrote: post #9
DeathArrow wrote: post #4

Earlier quoted context omitted.

>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, unattainabl…

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.

Re: Goodsteins theorem

#44

Post by symple »

hfhdjdks wrote: post #40
Tazerenix wrote: post #5

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…

>Since this theorem is true for the standard model of the natural numbers but not provable 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 stateme…

The provability of a statement depends upon which system you are in. For instance, within PA one can’t prove that PA is consistent but within ZFC one can prove that PA is consistent. We can say of a statement: Statement A can’t be proven in a given axiomatic system but it can be proven in a different system.

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.

Re: Goodsteins theorem

#45

Post by symple »

lanstin wrote: post #41
Tazerenix wrote: post #5

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…

Is there a cite for that? (About true in all models implies provable?). This post is the first I have heard that but it seems very significant.

It’s the Completeness Theorem.

Re: Goodsteins theorem

#46

Post by magneticnorth »

lanstin wrote: post #41
Tazerenix wrote: post #5

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…

Is there a cite for that? (About true in all models implies provable?). This post is the first I have heard that but it seems very significant.

Godel's completeness theorem https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_th...

(Not to be confused with Godel's incompleteness theorems)

Re: Goodsteins theorem

#47

Post by cubefox »

throwaway81523 wrote: post #39
cubefox wrote: post #30

Earlier quoted context omitted.

Yeah, but this terminology is fairly idiosyncratic. Probably a convention the main author likes to follow.

No it's pretty standard. Peano's axioms from the 19th century had an induction axiom in second order logic, since it quantified over predicates. Peano arithmetic (PA), also called first order arithmetic, came later. It is a first order theory whose induction axioms are an infinite schema. To confuse things further, second-order arithmetic (SOA) is also a first order theory, whose objects are naturals and sets of natu…

It's pretty standard also to talk about "first-order Peano arithmetic" and "second-order Peano arithmetic". This is much more clear but inconsistent with the other usage which you describe.

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.

Re: Goodsteins theorem

#48

Post by wruza »

tromp wrote: post #26
wruza wrote: post #23

Earlier quoted context omitted.

Last 4 terms are trivial. But I have trouble following even the first step. The SE answer is also pretty comprehensible, but as if there was some default assumption I’m not aware of. Do we make one-time substitution, or recursive? Stopping rules feel arbitrary in all enumeration combinatorics I try. https://codegolf.stackexchange.com/a/219466

The first step proceeds as follow. We want the predecessor of [s,t] with s=[0,0] and t=0. 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).

Ah, now I see, thanks!

Re: Goodsteins theorem

#49

Post by throwaway81523 »

cubefox wrote: post #47
throwaway81523 wrote: post #39

Earlier quoted context omitted.

No it's pretty standard. Peano's axioms from the 19th century had an induction axiom in second order logic, since it quantified over predicates. Peano arithmetic (PA), also called first order arithmetic, came later. It is a first order theory whose induction axioms are an infinite schema. To confuse things further, second-order arithmetic (SOA) is also a first order theory, whose objects are naturals and sets of natu…

It's pretty standard also to talk about "first-order Peano arithmetic" and "second-order Peano arithmetic". This is much more clear but inconsistent with the other usage which you describe. 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…

Yes. I don't remember who called second-order logic "set theory in sheep's clothing". ;)

Re: Goodsteins theorem

#50

Post by theteapot »

Kranar wrote: post #35
theteapot wrote: post #7

Earlier quoted context omitted.

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…

Not at all. There is no largest natural number to begin with even in the standard model. 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. The main issue is that first order logic can't defin…

I think I'm philosophically a finitist / constructivist, which seems to be very 19th century and out of vogue with modern Mathematicians AFAICT.

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

Post reply on HN