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.
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.
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 :-)
Agreed. It’s kind of obvious but I should’ve spelled that out, I guess.
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...
Yes.
Could you give a reference? Wikipedia seems to disagree but maybe I fail reading comprehension:
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.
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.
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 :-)