EI: An Explanation of Godel's Incompleteness Theorem

[Steve]

This link has a very terse explanation of Godel's Incompleteness Theorem, references in the book. It falls into the category of meta-logic (logic about logic).

If you're interested in that further and want heavy reading, consider Gödel, Escher, Bach: An Eternal Golden Braid. If you want lighter reading, look into Lady or the Tiger? And Other Logic Puzzles Including a Mathematical Novel That Features Gödel's Great Discovery instead.

[kvon]

I was wondering how much sense Delany's explanation made to someone unfamiliar with Godel. (I've read most of Godel Escher Bach--the pictures lightened the words a lot.)

[Sarah]

I don't think familiarness with Godel really mattered when it came to Delany's point. It seemed he was using Godel to represent the idea that there are truths which can't be proven, implying these are things like "big" truths like "being different" or stuff under myth or other humany things. My understanding is Godel's actual point was more like "you can write down infinite paradoxical sentences in a given system of logic." Ultimately I think Delany was playing with the idea of a world that looks human but is fundamentally not understandable by us, the idea that something can be true but irrational to all the tools humans use to think, not really making a point about formal logic and mathematics.

[Steve]

That's an interesting read on Godel's point, Sarah. I hadn't seen it that way.

I read it more as "if you make any non-trivial logic system, there is no way to list all the things that are true and there will always be internal inconsistencies (i.e., paradoxes)" Part of this comes from a big picture question of "can I make a proof generating machine for a logic system?" (no) and part from "can I make an internally consistent logical system?" (yes, but it will always be 'trivial', otherwise no).

[Sarah]

I'll admit that it's been quite a while since I took a class about this stuff, and it wasn't my strong suit anyways :/. And I guess what I meant by my shorthanding of Godel is that sure, there are an infinite number of "truths" that can't be proven with a given logic system, but these truths are just different ways of saying "it can't prove this sentence," aka gets it trapped in the "paradox" of something obvious being unprovable because the act of proving it would make the sentence false. Maybe I'm understanding it wrong and there are more complex or "important" true statements it's saying that are not provable, but my impression is that Godel's theorems are like a trick for making an unprovable statements, and if I understand it correctly all these guaranteed statements are just different ways of saying "a system can't prove it's own list of unprovable stuff." Like that a purely deductive system can't prove things that seem obvious when you apply contradiction (which I think still counts as "rational") to it.

And then the reason I think that's unimportant to Delany is that the part where Spider talks about it has more of the vibe of "some truths of the universe can't be reasoned out," which doesn't really mesh with Godel's "a specific logical system can't prove everything about itself." Delany is appealing to the existence of the irrational and mystery, Godel is saying you can't just run a single computer to spit out every last truth about itself. I hope that makes sense why I think Godel's theorem wasn't explained more in the book, and why I don't think that hurt anything (and may have helped).

[terpkristin]

Sarah wrote: "Ultimately I think Delany was playing with the idea of a world that looks human but is fundamentally not understandable by us, the idea that something can be true but irrational to all the tools humans use to think, not really making a point about formal logic and mathematics. "

I totally agree with this and had the same thought (though not so eloquently put) when I read it.

That said, if anybody is interested in Godel, I definitely recommend GEB. I haven't read The Lady or the Tiger, but I guess it's going on my "to-read" list! :D