Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Gödel and the limits of logic

plus.maths.org

Post reply on HN
Print view View original

21–30 of 80 posts

Re: Gödel and the limits of logic

#21

Post by ionfish »

"It's like an ill-designed jigsaw puzzle. No matter how you arrange the pieces, you'll always end up with some that won't fit in the end."

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.

Re: Gödel and the limits of logic

#22

Post by te_platt »

ionfish wrote: post #21

"It's like an ill-designed jigsaw puzzle. No matter how you arrange the pieces, you'll always end up with some that won't fit in the end." 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…

Pieces of puzzle = true statements about the natural numbers.

Pieces already put together = proved true statements.

Pieces that won't fit = true but unprovable statements.

Of course every analogy breaks down somewhere but I thought this one was pretty good.

Re: Gödel and the limits of logic

#24

Post by jackfoxy »

pndmnm wrote: post #16
vbtemp wrote: post #10

When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while. But as many mathematicians lament, the Incompleteness Theorem is one of the most popularly abused proofs of all time - used for non-experts to assert their own half-baked pseudo-philosophy (of course, the same goes for quantum mechanics as well). These are a…

Nagel's book is a wonderful exposition (three-page-long footnotes aside). In addition to these two, I might recommend Torkel Franzén's book "Gödel's Theorem: An Incomplete Guide to Its Use and Abuse". Some of the content is fairly technical but not inaccessible by any means. If you're interested in the corner cases of how incompleteness theorems can be applied, it's a terrific resource.

Thanks! I believe I read a reference to this book once on HN, then could not find it. Unless there is another book that focuses on the misuses of the incompleteness theorem, this is the one I'm looking for.

Re: Gödel and the limits of logic

#25

Post by stiff »

ionfish wrote: post #21

"It's like an ill-designed jigsaw puzzle. No matter how you arrange the pieces, you'll always end up with some that won't fit in the end." 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…

I think the point is that if you try to add those unprovable theorems to the system to try to make it complete it becomes inconsistent.

See for example:

http://en.wikipedia.org/wiki/Consistency_proof#Consistency_a...

Moreover, Gödel's second incompleteness theorem shows that the consistency of sufficiently strong effective theories of arithmetic can be tested in a particular way. Such a theory is consistent if and only if it does not prove a particular sentence, called the Gödel sentence of the theory, which is a formalized statement of the claim that the theory is indeed consistent.

Re: Gödel and the limits of logic

#26

Post by ezyang »

stiff wrote: post #25
ionfish wrote: post #21

"It's like an ill-designed jigsaw puzzle. No matter how you arrange the pieces, you'll always end up with some that won't fit in the end." 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…

I think the point is that if you try to add those unprovable theorems to the system to try to make it complete it becomes inconsistent. See for example: http://en.wikipedia.org/wiki/Consistency_proof#Consistency_a... Moreover, Gödel's second incompleteness theorem shows that the consistency of sufficiently strong effective theories of arithmetic can be tested in a particular way. Such a theory is consistent if and on…

But it really is mind-bending: if you, instead, add a theorem to the system (say, ZFC) which states, "ZFC is consistent", this system (ZFC+Con(ZFC)) is consistent! Even more strangely, if you instead add "ZFC is not consistent", this system (ZFC+notCon(ZFC)) is also consistent. We call these "self-hating theories."

Re: Gödel and the limits of logic

#27

Post by rgower »

vbtemp wrote: post #10

When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while. But as many mathematicians lament, the Incompleteness Theorem is one of the most popularly abused proofs of all time - used for non-experts to assert their own half-baked pseudo-philosophy (of course, the same goes for quantum mechanics as well). These are a…

I have no background in CS or Math, but a lot of philosophy. In other words, I'm a highly interested layman. What's my best plan of action to understanding Godel's theory? Maybe the best approach would be an entry level book on CS?

Re: Gödel and the limits of logic

#28

Post by vbtemp »

rgower wrote: post #27
vbtemp wrote: post #10

When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while. But as many mathematicians lament, the Incompleteness Theorem is one of the most popularly abused proofs of all time - used for non-experts to assert their own half-baked pseudo-philosophy (of course, the same goes for quantum mechanics as well). These are a…

I have no background in CS or Math, but a lot of philosophy. In other words, I'm a highly interested layman. What's my best plan of action to understanding Godel's theory? Maybe the best approach would be an entry level book on CS?

At the very least a good course in discrete mathematics is a good start (it's also a good start for anything technical as well - one of the most valuable math classes anyone can ever take, as far as I'm concerned)

Following that, a good class in the theory of computing: understanding what exactly a generative grammar is, properties of classes of languages (e.g., understanding what "regular languages are closed under complimentation" means), pumping lemma, diagnalization proofs, halting problem. The incompleteness theorem is intimately tied to this. This is the "CS-route" to getting a good understanding in Incompleteness, I'm sure math or physics majors come to approach it in each their own way.

Being a little blunt, a background in philosophy (whether it's academic or not) without a solid discrete math background, doesn't help you out at all. This isn't philosophy, it's just a fact about properties of formal systems of sufficient complexity. If you're looking for philosophy you won't find anything too deep in the proof of Incompleteness. The philosophical implications are not clear.

However, I do recommend Rebecca Goldstein's book. It's not technical, and she's a Princeton philosopher who will indulge you with possible philosophical ramifications of the theorem (along with a good narrative). I also recommend her other books as well, especially her first novella "The Mind-Body Problem". From a philosophical perspective, the dispute between Goedel and Wittgenstein who never accepted the Incompleteness Theorem "whereof we cannot speak we must pass over in silence", which, ironically, speaks of something of which we cannot speak.

Re: Gödel and the limits of logic

#29

Post by jhart3333 »

ionfish wrote: post #21

"It's like an ill-designed jigsaw puzzle. No matter how you arrange the pieces, you'll always end up with some that won't fit in the end." 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…

IIRC, In "The Emperors New Mind" Penrose mentions that Godel employed Cantor's "Method of Diagonalization" to show that within a system such as the natural numbers there can be true statements(uncountably infinite) not on the list of provable statements(countably infinite).

Re: Gödel and the limits of logic

#30

Post by zzzmarcus »

vbtemp wrote: post #10

When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while. But as many mathematicians lament, the Incompleteness Theorem is one of the most popularly abused proofs of all time - used for non-experts to assert their own half-baked pseudo-philosophy (of course, the same goes for quantum mechanics as well). These are a…

Another book that has several chapters related to GEB is David Deutsch's "The Beginning of Infinity." It's a very accessible read, and for me, eye-opening in more than one way.
Post reply on HN