Unfortunately this doesn't get at the heart of GIT. I'm pretty math-ignorant so correct me if I'm getting this wrong, but I'd do it like this:

Hey, $youngster, imagine that we have a Big Book of Mathematics. This book describes addition, multiplication, and some logic. There are pages like this:

    Fact: 1 + 4 = 5 
    Fact: 2 + 3 = 5

    Rule: Things that are equal to the same thing are equal to each other.

    So now we know: 1 + 4 = 2 + 3

On another page of the book you see this:

    Rule 1. The next sentence is false.
    Rule 2. The previous sentence is true.

    So now we know:... nothing??

It's kind of funny right? Both of those things can't be true within the rules they set up. The whole thing is inconsistent. We don't learn anything, we don't know anything. In fact this one page ruins the whole book. We should just rip it out.

But then, there's another book -- Gödel's book of Mathematics. On yet another page of the book there's this:

    Rule: You can't prove the rule on this page!

    So now we know: _________

That's just as funny, like the other one right? But here's the really weird part: is it wrong? (Let them get to No.) That's right, you can't prove the rule on this page. But it's still true. Fill in the blank: now we know "it's true!"

That means that there are at least a few weird things that you can't prove are true, but which are true. That's what Gödel thought was funny!

Next steps: try to get them to notice what's weird about both cases, in that they refer to themselves. Walk them through the idea that maybe you could just outlaw referring to a rule on the page. I can't think of an easy way to explain Gödel numbers, so I'd just have to say that he showed that if you allowed a book to have numbers and addition and whatnot, you could still sneak in weird things like that, by using a secret code.

I emailed this explanation to my son, and asked him if he understood it, He will be twelve on 2/2/12. His response was

"ya. it means that there is an unlimited space in between every number."

If the 12yo in question knows a bit of programming, a much simpler thing to explain would be the Halting problem, both the statement and the proof.

The bulk of Godel's proof is introducing recursive functions and the "godelization", which means mapping formulas to natural numbers and functions to arithmetic/first order expressions. This all comes for free if you know any programming language; if you don't like natural numbers, you can use strings (the source code itself and its manipulations).

From there, the diagonalization used in the Halting problem proof is the same used in Godel's theorem. In fact, the two theorems are intimately connected, essentially by the statements "you can write a first-order proof verifier in a programming language", and "you can write a computable function as a first-order arithmetic formula".

Great observation; as an undergrad, noticing this suddenly made GIT (which was taught to me by a mathematician in all its intricate detail) seem a lot less scary.

Indeed, the proof of the halting problem is much easier to sketch than the proof of Godel's incompleteness theorem (which the OP doesn't even attempt). So here he goes: a proof sketch of the halting problem for 12 year old programmers.

Suppose that somebody wrote us a program that can check whether another program will loop indefinitely or eventually halt when run on a particular input:

    bool halts(string program, string input){ 
       // halting checking code that checks 
       // whether program's main function
       // halts when given input
       // returns true or false
    }

For example:

    string program = 
      "void main(string foo){" +
      "  if(foo[0] == 'a'){ return; }" +
      "  else{ while(true){} }" +
      "}";
    
    halts(program, "abc") // returns true
    halts(program, "bar") // returns false

Now we can write the following program:

    bool halts(string program, string input){
       // same halting checking code as above
    }

    void main(string program){
      if(halts(program, program)){
        while(true){ }
      }
    }

Note that this is a perfectly valid program. halts() is supposed to work on any program, including a program that happens to contain the source code of halts(). We can just reuse the code that the person gave us and copy-paste it here.

Now the question is: what will our halts() function say about this program, when given its own code as input? In other words: what will the following code print?

    bool halts(string program, string input){
       // same halting checking code as above
    }
   
    void main(){
      string program = 
        "bool halts(string program, string input){" +
        "   // same halting checking code as above" +
        "}" +
        "void main(string program){" +
        "  if(halts(program, program)){" +
        "    while(true){ }" +
        "  }" +
        "}";

      print(halts(program,program));
    }

There are just 2 possibilities: either this program prints true, or this program prints false (if this program never terminates then halts() has a bug).

Case 1: suppose halts(program,program) returns true.

If the halts function is working correctly, that means that when we actually run the code in `program` with `program` as its input, it will halt. But now lets see what actually happens. When we run the main() function in `program` with `program` as its input, it first checks `if(halts(program,program))`. Well, we already assumed that halts returns true, so control flow will go inside the if block to the infinite loop. But that means that halts lied to us!

Case 2: suppose that halts(program,program) returns false.

Now a similar argument holds. run the code in `program` with `program` as its input, the condition of the if statement will be false, and the main function will terminate. So even though halts(program,program) returns false, the program actually terminates. It lied again!

As you can see, no matter what halts returns, it cannot tell the truth about the program we constructed. Hence it is impossible to fill in the missing code in halts() so that it will work correctly.

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.

Thank god-you are one of the rare individuals who can use the English language to explain a complex idea. The hideous bias I have encountered in the "hi tech" world is because my mind works like yours and I have always found your talent to be rare gem. Why anyone would think the reduction of complexity into simple terms means putting it into "12 year old" terms is beyond me. So I remain an exile.

This is a great explanation. There are a few things that more emphasis should have been placed on. In going over what an axiom is he should have noted that Godel's work only applies to theories which have a formal axiomatic basis and that the axioms are strong enough to encode the natural numbers enough to do certain arithmetic ops e.g. statements in the theory can be proven using induction. And maybe a bit more emphasis should have been placed on the fact that it is possible for a theory to be proven complete and consistent outside itself.

So for example, in line with the first theorem you can algorithmically verify/decide all statements in a subset of Euclidean Geometry (the subset which does not deal well with circles). And in the second part you can have theories which can verify themselves. Or that it is possible to prove a theory complete and consistent as long as you can find a suitably powerful model outside of it.

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.

Is that so? I think you mean that this is an explanation of the theorem, but not of a proof of the theorem.

You are correct - I was expecting an explanation of the proof because that's the part that is more difficult for me to understand, not because it was advertised.

I don't think this explanation would really work on a 12 year old. I doubt it will work on most adults, who have been through college, but maybe that's just me.

By the way, if you're interested in learning actual proofs of Godel's Theorems, you should take a look at this book: http://www.amazon.com/Introduction-G%25f6dels-Cambridge-Intr...

I haven't gone through all of it, but I've read much of the beginning. It actually starts off with easy proofs of Godel's Theorem, based much more on Computer Science explanations than Mathematical Logic.

Haven't read that one, but I try to re-read Nagel and Newman's at least once a year: http://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/081475837...

One thing I love about N&N is that it's short (160 pages) and the paperback is cheap ($7.65) so that I have no compunctions in lending it out.

Yes, I've read that one as well. It was a while ago, but from what I remember, it was higher-level than the Smith book. The Smith book is basically a normal mathematics curriculum book, not a "pop science" book (not to say that N&N is), which works out theorem after theorem to get to Godel's proof. Also, it starts off with computer-science proofs instead of the original Godel proofs, which many in this audience will probably prefer.

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.

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.

The Completeness Theorem (in one of its equivalent forms) says that every consistent first-order theory has a model, linking syntax and semantics. It doesn't tell you any thing about how you would go about justifying that a theory is consistent.

People hoped that some logical system capable of formalizing real mathematics would be able to justify its own consistency. Godel's Incompleteness Theorem (and stronger, related results) imply that any system capable of formalizing real mathematics (or even a very weak subset of it) can not justify its own consistency, requiring an appeal to a stronger system. Obviously, that raises the obvious question of why that stronger system is consistent. There are constructive proofs (due to Godel himself, Gentzen, and others) of the consistency of Peano Arithmetic, but by the Incompleteness Theorem they must all be non-finitary in some fashion, no matter how slight.

However, there are some limits to this understanding of Godel's Incompleteness Theorem. There are theories that are strong enough to prove (and perhaps more importantly, state) their own consistency but not strong enough to formalize diagonalization. If PA is consistent, then there is a theory that can state and prove its own consistency as well as the consistency of PA. The trick is that provability can be formalized on the basis that subtraction and division are total functions, whereas diagonalization requires addition and multiplication to be total functions. These theories can prove that subtraction and division are total functions, but not addition and multiplication.

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.

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.

Another great read, if you haven't already, is Brian Raiter's "Albert Einstein's Theory of Relativity: In Words of Four Letters or Less" is also a great read.

http://www.muppetlabs.com/~breadbox/txt/al.html

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 the completeness theorem.

(mathematicians: is that right?)

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 <handwave>certain relations</handwave> 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_...

I think the CH was used just to provide an example of an undecidable statement, not actually demonstrate something weird about the incompleteness theorem. Since the CH cannot be proven to be true or false within ZF (or ZFC), then you are correct, appending it would just provide an addition axiom.

So it is a weird example, since it NOT an example of a statement that is undecidable in every model.

This is not a weird example for that reason. For a given model, every statement is either true or false. Godel's Completeness Theorem says that a first-order theory is consistent if and only if it is true in some model. Therefore, for every undecidable statement there will be a model where it is true and a model where it is false.

These models can look very strange. For example, if ZF is consistent, then by the Second Incompleteness Theorem so is ZF + "ZF is inconsistent". By the Completeness Theorem, a model for this theory must exist. In this model ZF is inconsistent, so there is a 'proof' of a contradiction from the axioms of ZF. However, since we have assumed the consistency of ZF, such a 'proof' must necessarily involve nonstandard integers.

Well, the CH IS an example of a statement that is undecidable in ZF. Once you include is as an axiom, you essentially bypass the need to use ZF to justify it (or prove it). So, just because you are able to include the CH as an axiom, doesn't mean it is not an example of a undecidable statement within a given set of axioms. Does that make sense?

Yeah that was a tangent. The author got a bit overexcitrd and overshot.

Also not the OP's reply (paraphrased): "Thanks, but I wasn't interested in the understanding logic or math. I am thinking more along the lines of [metaphysical gobbledygook]. What can you say about that? "

The situation with Goedel sentence (let's call it G) is actually not very different. As neither G nor negation of G is provable, you could also say that it contains extra information, and add negation of G as a new axiom to PA, just like you could add CH to ZF.

If you do that, you could wonder what your new arithmetic looks like. This is actually very interesting question. Since "not G" says basically "it's not true that there's no proof of me", or, more specifically, "it's not true that there's no number that represents the proof of me", it's clear that "not G" asserts the existence of a certain "natural" number being the proof of G, which is not one of the natural numbers we know (since no "regular" natural number represents the proof of G). In our new universe there are "natural" numbers that you cannot reach by counting. Because of that, one can construct many different nonequivalent "implementations" (models) of PA + not G, which are necessarily different than the standard implementation of artihmetic we know (1, 2 = S(1), 3 = S(S(1)), ..., n = S(S(...S(1)...)), with + and *).

What is interesting about incompleteness theorem is that no matter if we add arbitrarily large number of axioms to PA, or even infinite number of axioms generated by computer program we write, the resulting system will still be incomplete, and each will have its own (many of them, actually) Goedel sentence.

Now someone please explain Skolem's paradox to a 12 year old.

It depends on whether the meaning of "exists" is, I think. By analogy to the finite universe (always dangerous in logic), it is like saying "we live in a sphere of diameter 4. We have proven (due some hypothetical variation of relativity) that all matter in the universe will never be able to move more than distance 1 from the original center of our existence. An object of length 3 can be mathematically described, but is theoretically impossible to construct." Or something.

One of the best - easiest to understand - explanations I have seen anywhere for Gödel's theorem.