Avigad on Incompleteness
If you’re interested in learning about recursion theory and the Godel incompleteness theorem, these lecture notes by Jeremy Avigad are terrific. In this approach, incompleteness follows from properties of algorithms, which I think is the clearest approach.
This entry was posted
on Wednesday, November 25th, 2009 at 1:33 pm and is filed under Uncategorized.
You can follow any responses to this entry through the RSS 2.0 feed.
You can skip to the end and leave a response. Pinging is currently not allowed.
These notes look helpful–thanks for sharing the link.
I definitely disagree… a model-theoretic view seems like it gets to the core idea and construction more clearly, whereas an algorithm-based approach essentially makes incompleteness a corollary of the unsolvableness of the halting problem.
Thoughts?
I think of incompleteness as a corollary of the unsolvableness of the halting problem. I find the argument through the Godel or Rosser sentence less clear. (Though Avigad also gives that version of the proof.)
The way I’ve gotten myself to understand it most cleanly recently is as a juxtaposition of the definability of provability in any recursive system and the undefinability of arithmetical truth. This has the advantage of showing just how far truth is from being decidable once you note that recursive predicates are Sigma-0, provability (like all r.e. predicates) is definable by a Sigma-1 formula, and truth is not even Sigma-n for any finite n. But it has the disadvantage of only giving the first incompleteness theorem and not the second. I need to find a nice way to internalize a proof of that one. (I assume that really understanding Loeb’s theorem will help.)
Really understanding Loeb’s theorem… ah, yes! That’s one of most jaw-droppingly astounding theorems I know. Goedel’s incompleteness theorems are obvious by comparison.
Anyone who wants to understand Loeb’s theorem should look at the cartoon version by Eliezer Yudkowsky.