2,889 karma · joined February 27, 2008
I repeat my objection to the Goldstein book raised elsewhere in this discussion.
http://www.logicmatters.net/2012/05/teach-yourself-logic-1-f...
Then get Smith's book An Introduction to Gödel's Theorems. It explains Gödel's results in great detail and doesn't assume too much background knowledge. A certain amount of perseverance will, of course, be required…
There's some supplementary material on his website: http://www.logicmatters.net/igt/
Additionally, first order logic is complete: for every statement true in all models of a theory, there is a proof of the statement from the theory.
These two constraints cannot both be satisfied in a sound deductive system for second order logic. To see that this is so, consider that in second order logic we can prove Dedekind's categoricity theorem: there is only one model (up to isomorphism) of the second order Peano axioms (PA2). Let's assume that the provability relation for second order logic is recursively enumerable. We know from Gödel's incompleteness theorem that the set of first order sentences true of the natural numbers is not recursively enumerable. So take a sentence of the form "If PA2 then _" for some sentence _ which is in that set but not in the extension of the provability relation (this is a legitimate statement since the PA2 axioms are finite so we can just take their conjunction). This should be a logical truth of second order logic, but it's not provable (by the argument just given), so second order logic is incomplete: there are statements which are logical consequences yet are unprovable. So in other words, yes, the incompleteness theorem is very much at play in this limitation of second order logic.
For the technical details I very much recommend chapters 3 and 4 of Shapiro's book; it's not terribly expensive, and any decent university library should have a copy.
(A small footnote to my earlier post: Shapiro's book originally came out in 1991, not 2000—that's just the date of the paperback edition, and I'm unsure as to whether there are any substantial differences between the two.)
Second order logic does not have a complete proof theory, so your Turing machine will not be able to compute the consequences of a theory formulated in second order logic. This can be avoided by employing Henkin semantics, but then you're not working with full second order logic anymore. Stewart Shapiro's 2000 book, Foundations without Foundationalism: A Case for Second-Order Logic has the technical details should you be interested.
http://www.lrb.co.uk/v28/n03/solomon-feferman/provenly-unpro...
http://math.stanford.edu/~feferman/papers/lrb.pdf (full text)
"Those who are fascinated by Gödel's theorems—and the general idea of limits to what we can know—may still hunger for a more universal view of their possible significance. But they should not be satisfied with Goldstein's 'vast and messy' goulash, hers is not a recipe for true understanding."
Eh? No it doesn't! If you add Con(PA) to the axioms of Peano arithmetic you obtain a stronger system. That system can't prove its own consistency, of course, but if you have a proof that the system PA + Con(PA) is inconsistent then you're probably in line for a Fields Medal.
Alan Turing worked on precisely this issue, developing ordinal logics in his PhD thesis (with Alonzo Church) to try to overcome incompleteness. Soloman Feferman, who in the 1960s proved a stronger result than Turing obtained, has written about this extensively. An accessible paper is this one:
I really don't understand this analogy. The first incompleteness theorem shows that there are statements true of the natural numbers which aren't provable from any sufficiently strong recursive theory. It's more like Th(N) (the set of statements true of the natural numbers) being a jigsaw puzzle from which many pieces will always be missing if you start with a recursive set of pieces and try to lay down only those pieces which a provable from your initial set. Nothing "won't fit": there aren't inconsistencies or incompatibilities at work here, but incompleteness.
This was fixed in the recent 0.8 release.
http://www.cambridge.org/gb/knowledge/isbn/item1175709/?site...
Steve Jobs appeared happy enough to have "Designed by Apple in California" inscribed on all Apple's products.
I submit that when people make claims of this sort, what they usually mean is actually "I'm used to doing it this way". Some actual studies of how new programmers learn would be valuable, and allow us to begin to evaluate claims like the above with at least a modicum of objectivity.
I recently attended a workshop devoted entirely to Tennenbaum's Theorem, his famous result that the only recursive model of PA is the standard model.
http://www.bbk.ac.uk/philosophy/our-research/ppp/tennenbaump...
If that's the case then I suggest he tries Hakyll, which has a dependency system built in so that it only rebuilds what it needs when files change.
http://www.guardian.co.uk/science/2009/apr/02/paul-dirac-str...
I once started a physics degree at Bristol, where Dirac was born and raised, and the department made a big show of 'their' man. The house he grew up in is a few minutes' walk from the department, and has a blue plaque indicating its status. It was some years before I discovered that Dirac had never been in the physics department at all, but in fact studied electrical engineering, before entering Cambridge, where he flourished as a physicist.