cousin_it comments on No one knows what Peano arithmetic doesn't know - Less Wrong

17 Post author: cousin_it 16 December 2011 09:36PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (52)

Comments (52)

You are viewing a single comment's thread. Show more comments above.

Comment author: cousin_it 16 December 2011 10:41:48PM *  1 point [-]

No, you need guarantees on the formal system's complexity, similar to the ones in Godel's incompleteness theorem(s).

Agreed. It's kind of obvious but I should've spelled that out, I guess.

This is stronger than your "has a model containing the standard integers", and is equivalent to "has the standard integers as a model".

I agree that my version is wrong, but yours doesn't sound completely right either. ZFC doesn't have the standard integers as a model, or does it? I thought it also included other objects...

Note that you're assuming here that PA is sound and in particular consistent.

Yes.

The halting oracle's uncomputability degree is the smallest possible uncomputable degree, so no.

Could you give a reference? Wikipedia seems to disagree but maybe I fail reading comprehension:

Emil Post studied the r.e. Turing degrees and asked whether there is any r.e. degree strictly between 0 and 0′. The problem of constructing such a degree (or showing that none exist) became known as Post's problem. This problem was solved independently by Friedberg and Muchnik in the 1950s, who showed that these intermediate r.e. degrees do exist.

Comment author: Anatoly_Vorobey 16 December 2011 10:53:00PM 2 points [-]

I agree that my version is wrong, but yours doesn't sound right either. ZFC doesn't have the standard integers as a model, or does it? I thought it also included other objects...

My version is right, but perhaps too restricted. The reason your argument works for ZFC is because it interprets PA by proving its axioms as applied to particular sets in ZFC. So the general requirement would be for a system to be strong enough to prove certain true statements about the natural numbers and to disprove certain false statements.

Could you give a reference?

No, I wrote nonsense - I realized that and wanted to come back and edit it pointing out this exact link you gave, but you did that before me. I don't know enough about Post's problem or the Friedberg/Muchnik solutions to say whether they can be suitably presented as provability classes.

Comment author: cousin_it 16 December 2011 10:57:49PM *  0 points [-]

The reason your argument works for ZFC is because it interprets PA by proving its axioms as applied to particular sets in ZFC.

Nice! I didn't realize that. I guess the easiest way is to ask for the same guarantees that Gödel's theorems use, do you agree? For now, changed the post accordingly :-)

Powered by Reddit Powered by Reddit