Stack Exchange
log in

Lost definition

♦  Logic

This room is meant for discussion about logic, including found...
1
6
Lost definition
Jan 30, 2021 19:07
Yes, Y combinator seems like magic. Thank you for the answers.
Lost definition
Jan 30, 2021 19:06
@user21820 Hmmm... very nice!
Lost definition
Jan 30, 2021 17:29
Could you make the same argumentation using the recursion fix-point theorem?
Lost definition
Jan 30, 2021 17:28
@user21820 And, by the way, I actually get to this post by this other answer:math.stackexchange.com/questions/1002540/… . I have some questions about it too. If I am right you are simulating lambda calculus rules in arithmetic via definitorial expansions. But to do that wouldn't you still have to have the result that computational enumerable (r.e.) predicates are weak representable in PA?
Lost definition
Jan 30, 2021 16:18
"In short, the ω-rule is so powerful that it is like a truth-oracle rather than any sort of induction." Yeah, now I agree.
Lost definition
Jan 30, 2021 16:11
yes it is helpful
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.
Lost definition
Jan 30, 2021 15:52
@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.
Lost definition
Jan 30, 2021 15:08
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…
Lost definition
Jan 30, 2021 15:06
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
Lost definition
Jan 30, 2021 15:02
@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.
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