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

21–30 of 54 posts

Re: Goodsteins theorem

#21

Post by daxfohl »

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

> 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

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.

Re: Goodsteins theorem

#22

Post by thaumasiotes »

daxfohl wrote: post #21
tromp wrote: post #12

Earlier quoted context omitted.

> 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

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

Re: Goodsteins theorem

#23

Post by wruza »

tromp wrote: post #6

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…

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

Re: Goodsteins theorem

#24

Post by dandanua »

wruza wrote: post #23
tromp wrote: post #6

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…

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

Just look at the expanded js code, I also had troubles with the more informal description. It's a one-time substitution but for all matches.

Re: Goodsteins theorem

#25

Post by ShamelessC »

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…

That’s clarified almost immediately in the article.

Also, Wikipedia articles can have multiple authors.

Re: Goodsteins theorem

#26

Post by tromp »

wruza wrote: post #23
tromp wrote: post #6

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…

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

Re: Goodsteins theorem

#27

Post by naasking »

H8crilA wrote: post #17
anvuong wrote: post #8

Earlier quoted context omitted.

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.

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?

Re: Goodsteins theorem

#28

Post by cubefox »

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

> 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

Logicians and set theorists use this terminology. But everyone else just uses the second-order induction axiom when talking about arithmetic, without explicitly talking about first or second-order logic. Steven Shapiro made this point in his book "Thinking About Mathematics".

Re: Goodsteins theorem

#29

Post by cubefox »

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

I think the article mentions this clearly in the introduction: “it is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second-order arithmetic).”

Yeah, but this terminological distinction is not really justified. It should be simply between first and second order Peano arithmetic.

Re: Goodsteins theorem

#30

Post by cubefox »

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

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.
Post reply on HN