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

11–20 of 54 posts

Re: Goodsteins theorem

#11

Post by baq »

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…

Actually… reaching the very limits of knowability is the crown achievement of science and your first two examples have very important engineering implications.

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.

Re: Goodsteins theorem

#12

Post by tromp »

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

Re: Goodsteins theorem

#13

Post by theteapot »

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

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.

If we can just make up random axioms like this, I think I'd prefer the turtles :).

Re: Goodsteins theorem

#14

Post by YetAnotherNick »

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 operation symbols and replacing the second-order induction axiom with a first-order axiom schema.

[1]: https://en.wikipedia.org/wiki/Peano_axioms

Re: Goodsteins theorem

#15

Post by Sharlin »

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…

Worth noting that this sequence was introduced, of all places, as an answer to a codegolf.stackexchange question in 2021!

https://codegolf.stackexchange.com/a/219466

Re: Goodsteins theorem

#16

Post by Jaxan »

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

Re: Goodsteins theorem

#17

Post by H8crilA »

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

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.

Re: Goodsteins theorem

#18

Post by dandanua »

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…

This function is almost like in the definition of middle-growing hierarchy https://googology.fandom.com/wiki/Middle-growing_hierarchy But this hierarchy can be defined for any ordinal with a system of notations.

I'm wondering if there is some deeper sense in this Patcail's predecessor function? Are there some follow up research on that?

Re: Goodsteins theorem

#19

Post by tromp »

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

Worth noting that this sequence was introduced, of all places, as an answer to a codegolf.stackexchange question in 2021! https://codegolf.stackexchange.com/a/219466

Indeed; a lot of gems are to be found there. Like this 49 bit program to exceed Graham's Number [1].

[1] https://codegolf.stackexchange.com/questions/6430/shortest-t...

Re: Goodsteins theorem

#20

Post by Karellen »

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…

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

Post reply on HN