Goodsteins theorem • Hacker News Board

Re: Goodsteins theorem

#51

Post by cubefox » Wed, Dec 27, 2023, 9:29 AM UTC

throwaway81523 wrote: post #49

cubefox wrote: post #47

Earlier quoted context omitted.

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

Quine. His justification was quite bad though.

Re: Goodsteins theorem

#52

Post by Hugsun » Wed, Dec 27, 2023, 11:26 AM UTC

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

Couldn't you also do the substitution n times to make this ordinal emulate the fast growing hierarchy instead of the middle growing one?

Re: Goodsteins theorem

#53

Post by tromp » Wed, Dec 27, 2023, 3:10 PM UTC

Hugsun wrote: post #52

tromp wrote: post #26

Earlier quoted context omitted.

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

Couldn't you also do the substitution n times to make this ordinal emulate the fast growing hierarchy instead of the middle growing one?

Where would you get the number n from? All we have here are binary trees s and t of arbitrary shape.

Re: Goodsteins theorem

#54

Post by lanstin » Fri, Dec 29, 2023, 10:45 PM UTC

magneticnorth wrote: post #46

lanstin wrote: post #41

Earlier quoted context omitted.

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)

Wow.