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

31–40 of 54 posts

Re: Goodsteins theorem

#31

Post by H8crilA »

naasking wrote: post #27
H8crilA wrote: post #17

Earlier quoted context omitted.

The shocking part is just how much you can't get away from stupid problems like this. Hilbert believed we could settle these kinds of issues once and for all, the Goedel proved that we can't. So in a sense there isn't anything like "the actual natural numbers without shenanigans", there always are shenanigans.

There always are shenanigans if you pass a certain threshold of expressive power. Can we do most or all useful /interesting stuff below that threshold though?

Excessive power has been proven to be just addition and multiplication over the natural numbers. So - no, we can't.

Re: Goodsteins theorem

#32

Post by [deleted] »

cubefox wrote: post #30
YetAnotherNick wrote: post #14

Earlier quoted context omitted.

According to different page in wikipedia, Peano axioms is second order but "Peano arithmetic" is first order. > 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 operatio…

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

[deleted]

Re: Goodsteins theorem

#34

Post by naasking »

H8crilA wrote: post #31
naasking wrote: post #27

Earlier quoted context omitted.

There always are shenanigans if you pass a certain threshold of expressive power. Can we do most or all useful /interesting stuff below that threshold though?

Excessive power has been proven to be just addition and multiplication over the natural numbers. So - no, we can't.

Yes, addition and multiplication over the infinite naturals. I don't think it's obvious that all three of these are needed together for all interesting applications. For instance, various types of finitism eliminate the infinities.

Re: Goodsteins theorem

#35

Post by Kranar »

theteapot wrote: post #7
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…

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

Re: Goodsteins theorem

#36

Post by daxfohl »

thaumasiotes wrote: post #22
daxfohl wrote: post #21

Earlier quoted context omitted.

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…

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

Oh, I missed that! I'd searched google for the term, and it just returned the top-level Peano axioms page.

Anyway, updated the link on the Goodstein's Theorem page to point to that section specifically.

Re: Goodsteins theorem

#37

Post by [deleted] »

cubefox wrote: post #10

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

[deleted]

Re: Goodsteins theorem

#38

Post by ykonstant »

ConnorMooneyhan wrote: post #33

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

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

Re: Goodsteins theorem

#39

Post by throwaway81523 »

cubefox wrote: post #30
YetAnotherNick wrote: post #14

Earlier quoted context omitted.

According to different page in wikipedia, Peano axioms is second order but "Peano arithmetic" is first order. > 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 operatio…

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

Re: Goodsteins theorem

#40

Post by hfhdjdks »

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 statements true independently of the axiomatic system you use to prove them? (Apologies if this is too off-topic)

Post reply on HN