wuthefwasthat comments on No one knows what Peano arithmetic doesn't know - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (52)
I'm not an expert either, so I'm probably just being unclear
The axioms don't need to be r.e. If they were, the oracle would never be more helpful than a halting oracle, no?
I don't either. It's just a strong intuition which I'm not sure I can justify, and which might be wrong.
ETA: By silly, I don't necessarily mean as simple as the examples I gave. Basically if you have a formula phi(S(x), T, F), which holds for arbitrary sentences S(x), provably true T, and provably false S, then you can replace S(x) with R(x), T with R(x in L), and S with R(x not in L). Not sure if that was well explained, but yeah.
At least it looks like my answer is correct :). Also my proof should generalize, if it does work. So I would have guessed that Feferman's (stronger) result was true, and I wouldn't be surprised if the argument was along these lines, though maybe the details are harder.
But we want the oracle to be less helpful than the halting oracle...
Anyway, the question is settled now, thanks a lot :-)
Oops sorry! Ignore what I said there. Anyways, the axioms aren't necessarily r.e., but as far as I can tell, they don't need to be.