Conversation started Jan 30, 2021 at 14:58.
Lost definition
Lost definition
Jan 30, 2021 14:58
@Lostdefinition: Smullyan does not disagree with what I wrote. His comments are misleading to beginners. PA has induction and is incomplete. PA− has no induction and is also incomplete. Talking about going beyond first-order induction is in fact not meaningful because there is simply no such thing in reality. Think about it, there is no formal system for second-order PA with full second-order semantics, so it's simply meaningless to ascribe 'force' to the second-order induction axiom in any foundational sense (which is what the incompleteness theorems are really about). [cont] — user21820 54 mins ago
@user21820, yes. I agree with you about the fundamentional issue. But Smullyan also says you could use this Carnap's rule in page 113 of Incompletess book.Then PA+ with this rule would be complete. I don't understand second-order logic, but it makes sense to me that such thing would be complete.
user21820
user21820
@Lostdefinition Please quote the relevant portions or provide a public link, for ease of reference.
In particular, you definitely should read carefully about what full second-order semantics means, because it is quite like scams; it promises a lot but delivers nothing in reality.
Lost definition
Lost definition
21
Q: Computability viewpoint of Godel/Rosser's incompleteness theorem

user21820 How would the Godel/Rosser incompleteness theorems look like from a computability viewpoint? Often people present the incompleteness theorems as concerning arithmetic, but some people such as Scott Aaronson have expressed the opinion that the heart of the incompleteness phenomenon is uncompu...

logic reference-request computability proof-theory incompleteness
I am not use to the chat... sorry, here are the transcripts of the comments of the link:

"In misconceptions: "It is not due to induction". Smullyan disagrees (see Gödel Incompleteness Theorems, p. 112), he says incompleteness is due to lack of induction. It's because first-order "induction doesn't express the full force of mathematical induction""

"@Lostdefinition: Smullyan does not disagree with what I wrote. His comments are misleading to beginners. PA has induction and is incomplete. PA− has no induction and is also incomplete. Talking about going beyond first-order induction is in fac…
user21820
user21820
Jan 30, 2021 15:48
@Lostdefinition Sorry I wasn't clear enough; that's not what I meant. I meant that you should quote the relevant parts about "Carnap's rule".
Google tells me this, but then what you said Smullyan wrote seems to be an empty objection to what I stated because that rule simply cannot be achieved in any foundational system! Since I know Smullyan is a real logician, his real point may be more subtle, but it's unclear what it might be from what you quoted.
Lost definition
Lost definition
@user21820 Yes, I will study better this problem with second order. But to put more clear this another issue, this Carnap rule, in first order, is: [ Form (for all x) F(x) you can infer F(0), F(1),... , F(n), ...., infinitily ] . Put this on PA, then you have a complete theory in first order. Then it seems the cause of incompleteness is something about the finite character of proofs in PA.
user21820
user21820
@Lostdefinition Ah so then there is no actual objection; it is merely an issue of different perspective.
My statement about induction in my post is concerning the fact that many people believe (wrongly) that PA is incomplete because it has induction. And this is false.
As per your last clarification, Smullyan's statement is not about that at all, but rather about the fact that one of the things that incompleteness relies on is that proofs in any foundational system are all finite.
That's completely true, of course.
And just to be clear, what we ought to be talking about is of course essential incompleteness (i.e. no computable extension is complete). If one takes away enough axioms from PA, it remains incomplete but may become completable. I think Robinson pointed out that his theory Q has axioms which are all necessary because removing any axiom yields a completable theory.
So one might believe (wrongly) that PA is incomplete because it snuck in some infinitary behaviour via the induction schema. This is false because PA− (or Q) has finitely many axioms and no induction axiom of any kind, and yet is essentially incomplete.
That is all that I was saying in my statement over at my post.
@Lostdefinition: Does that clear things up?
(I just won't use Smullyan's phrasing of "not enough induction", simply because there is no well-defined notion of enough induction. Carnap's rule doesn't count as induction because it's simply not induction; in standard logic texts it is called the ω-rule.) @Lostdefinition: hope this added remark is helpful as well.
Lost definition
Lost definition
Jan 30, 2021 16:10
Yes, it clear somethings. I will have to study more of this. I agree we are talking about essential incompleteness. And I agree that PA- and PA are essentially incomplete, it don't matter, the fistr order induction axiom wasn't used for anything in the proof of incompleteness. But it seems Smullyan wants to point that both systems lack the "real" induction, and if you put it something near it we have a non-axiomatizable theory or infinitely long proofs.
yes it is helpful
user21820
user21820
I understand that. Indeed, you basically need something uncomputable to escape incompleteness. I just quibble with still calling it induction. =)
Ah I have another comment that might shed more light on this.
Note that with the ω-rule, basically all quantifiers vanish. Do you see why? Basically you get rid of one quantifier at a time. ∃ on the outside is easy. ∀ on the outside disappears via the ω-rule. So every arithmetical truth can be proven with the ω-rule, even without all the axioms of PA!
So it becomes no longer sensible to think of this as PA plus ω-rule. It is just ω-rule!
Well, almost all the axioms of PA. You still need the basic stuff for the symbols.
In short, the ω-rule is so powerful that it is like a truth-oracle rather than any sort of induction.
Lost definition
Lost definition
"In short, the ω-rule is so powerful that it is like a truth-oracle rather than any sort of induction." Yeah, now I agree.
user21820
user21820
@Lostdefinition Haha okay. =P
 
Conversation ended Jan 30, 2021 at 16:25.