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

41–50 of 80 posts

Re: Gödel and the limits of logic

#41

Post by GregBuchholz »

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?

I always liked "Godels Theorem Simplified". It doesn't rely on heavy technical prerequisites in mathematics or CS. It is pretty much as advertised, a simplification of Godel's original proof. Godel used a more complicated encoding scheme using prime numbers, which Gensler replaces with a simpler encoding scheme. He walks you through various less powerful formal systems, before you get to one complicated enough to have incompleteness issues. There is also discussion about the philosophical ramifications of Godel's theroems.

http://www.amazon.com/Godels-Theorem-Simplified-Harry-Gensle...

"Godel, Escher, Bach" is another interesting read, but that volume does have a lot of extraneous fluff.

Re: Gödel and the limits of logic

#42

Post by ionfish »

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…

"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."

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:

http://math.stanford.edu/~feferman/papers/turingnotices.pdf

Re: Gödel and the limits of logic

#43

Post by haliax »

JamesLeonis wrote: post #38
haliax wrote: post #36

Earlier quoted context omitted.

I've read it, but clearly didn't digest enough (a common problem I'm told :P). I will take another look, thanks!

If you didn't already know about it, there's a Reddit group that's doing a weekly readthrough and discussion. They're on chapter 13 currently. http://reddit.com/r/GEB

Awesome, thanks!

Re: Gödel and the limits of logic

#44

Post by [deleted] »

ezyang wrote: post #26
stiff wrote: post #25

Earlier quoted context omitted.

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."

[deleted]

Re: Gödel and the limits of logic

#45

Post by why-el »

jaysonelliot wrote: post #14

As an aside, if you look at the photo credit on that great color photo of Einstein and Gödel, it was snapped by Oskar Morgenstern, one of the fathers of game theory. http://en.wikipedia.org/wiki/Oskar_Morgenstern Morgenstern and Einstein were Gödel's closest friends, I've just now learned. It gives me goosebumps looking at that photo and imagining the three of them on that lawn. Semi-related, here's an account of Göd…

Thanks for the links. I read the account. I was surprised to see that Morgenstern didn't mention Gödel's arguments. It only made a reference to the steps leading up to Gödel's own findings, like what he read on and how much time it took him, but never mentioned the substantial argument, which is what I wanted to read.

Re: Gödel and the limits of logic

#46

Post by ionfish »

te_platt wrote: post #22
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.

The point must surely be that one can add the these true-but-unprovable statements to the original axioms without contradiction. They fit just fine: they're all elements of Th(N). It's a poor analogy because the natural way of thinking of a jigsaw puzzle is of a set of elements (pieces) that are consistent (every piece has a place), so if a piece doesn't fit then it's not consistent with the others. But this is false if the pieces are statements in the language of arithmetic that are true of the natural numbers.

Re: Gödel and the limits of logic

#47

Post by pmb »

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?

The statement "this fact is not provably true under the axioms of mathematics" is not provably true under the axioms of mathematics. Therefore, it is true, but we can never prove it.

I recommend approaching this via uncomputability, and the fact that for every program there is a proof and vice versa.

Re: Gödel and the limits of logic

#48

Post by ionfish »

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…

The Goldstein book is rubbish. Soloman Feferman destroys it in his LRB review.

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."

Re: Gödel and the limits of logic

#49

Post by ionfish »

haliax wrote: post #31

On a related note, does anyone know where I would look to understand reducibility of formal systems to one another? I'm really interested by questions like: Why is second order logic irreducible to first order logic if I could use first order logic to reason about the behavior of a turing machine running a second order logic theorem prover with whatever inputs I like? How do I get something that can do what I can do,…

'Reducibility' in general is an informal notion, and as such there are many different technically precise ways of capturing aspects of it. Mutual interpretability and bi-interpretability are two of these, but they apply to formal systems with the same underlying logic (that is, the same semantics and proof theory). There are also many other notions of translation between different logics like Gödel–Gentzen negative translation between classical logic and intuitionistic logic. I'm not sure if there is a good introduction to all of these different ways of capturing reducibility, but you could try asking on math.stackexchange.com, there are usually helpful responses to reference requests there.

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.

Re: Gödel and the limits of logic

#50

Post by nodemaker »

haliax wrote: post #36
Rickasaurus wrote: post #33

Earlier quoted context omitted.

Godel Escher Bach is a great book (it's entertaining and informative) for learning about formal systems. There are general rules (rules of inference) for their construction from axioms that will keep you from going wrong.

I've read it, but clearly didn't digest enough (a common problem I'm told :P). I will take another look, thanks!

My intelligence fails me whenever I try!
Post reply on HN