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

Explaining Gödel's Incompleteness Theorem to a Twelve Year Old

reddit.com

Post reply on HN
Print view View original

11–20 of 37 posts

Re: Explaining Gödel's Incompleteness Theorem to a Twelve Year Old

#11

Post by Dn_Ab »

andrewcooke wrote: post #4

i'm not a mathematician, but his final point about the continuum hypothesis seemed odd to me. the CH is "outside" ZF, but that just means (afaik) that it contains some extra "information" that is not in ZF. adding it to ZF doesn't force any kind of contradiction, in the way that adding "this system is consistent" would. so CH is (just) an example of an independent axiom - it doesn't illuminate what is so weird about…

His example is to do with the first theorem. There are two incompleteness theorems. The one most people think of when they hear Godel is the second even though the first is key. The first one has to do with decidability - for any given statement from a theory is it algorithmically verifiable given the axioms of the theory? If you can encode the natural numbers with its axioms and pose certain relations with that encoding then no. This ties Godel's work to Turing. http://www.scottaaronson.com/democritus/lec3.html

Here is a list of undecidable statements in ZFC: http://en.wikipedia.org/wiki/List_of_statements_undecidable_...

Re: Explaining Gödel's Incompleteness Theorem to a Twelve Year Old

#13

Post by bjornsing »

I remember a joke from college that went something like this: There was this mathematics professor that used to tell his students that if they failed at proving a conjecture they should try to prove the opposite, and if they couldn't do that either they should quit mathematics. He had to stop saying that after Gödel published his paper. :)

I haven't studied Gödel's proof and have to admit I would probably have to brush up quite a bit on my maths to be able to, but to me this simple joke offers a more pedagogical and perhaps more meaningful understanding of Gödel's (first) incompleteness theorem.

Re: Explaining Gödel's Incompleteness Theorem to a Twelve Year Old

#16

Post by RockofStrength »

This is my layman's understanding of Godel's incompleteness theorems: Any set of axioms powerful enough to decide all its theorems will always have inconsistencies in its theorems (e.g. "if true then false"). To be consistent, the set of axioms must be incomplete (some of its theorems are undecidable).

The following sentences have some of the 'flavor' of Godel's theorems:

"This sentence is false." →if true, then false.

"These are not words." →if true, then irreconcilable with its own truth.

Re: Explaining Gödel's Incompleteness Theorem to a Twelve Year Old

#17

Post by zipdog »

VMG wrote: post #12

To be clear this is an explanation of the consequences of Gödel's Incompleteness Theorem

Exactly. An "explain like I'm twelve" for Godel's Incompleteness Theorum itself would revolve around the idea of self-referential statements (such as 'the set of all sets which don't contain themselves', or 'the barber of Seville shaves everybody who doesn't shave themselves').

In my understanding, Godel created a system that mapped statements to numbers, and then looked at the numbers that represented statements like 'this statement is provable' and found a way to show that the equivalent number had a property that wasn't provable.

Re: Explaining Gödel's Incompleteness Theorem to a Twelve Year Old

#18

Post by nandemo »

scoofy wrote: post #14

Am i wrong or does 'Well here's what Godel proved: There's no way to really know whether or not any theory is consistent.' completely ignore Gödel's completeness theorem for first order logic.

Yeah. It should be something like "any sufficiently strong theory". But that's still a justifiable simplification. Other parts of the explanation are totally incomprehensible to someone who doesn't already know what's he talking about.

Re: Explaining Gödel's Incompleteness Theorem to a Twelve Year Old

#20

Post by EdM »

scoofy wrote: post #14

Am i wrong or does 'Well here's what Godel proved: There's no way to really know whether or not any theory is consistent.' completely ignore Gödel's completeness theorem for first order logic.

I don't think there is a contradiction, but someone please correct me if I'm wrong. Godel's theories are something I've recently begun trying to wrap my head around.

Godel's completeness theorem proves the equivalence of logical implication and deducibility. Logical implication being the formal definition of what it means for a collection of sentences (axioms) to logically imply another sentence (theorem); deducibility being the method with which a working mathematician would like to use to show logical implication (i.e. any proof you've ever read in a mathematical textbook).

Incompleteness, on the other hand, shows that there are some true sentences that cannot be deduced from any set of axioms (and therefore, by completeness, are not logically implied by any set of axioms).

This is my understanding after having spent a few weeks reading Enderton's "A Mathematical Introduction to Logic." If I am misunderstanding this, I would love input (so please comment). Godel's theorems are something I'm very anxious to wrap my head around.

Post reply on HN