Can someone explain Gödel's incompleteness theorems in layman terms?
The problem with Gödel's incompleteness is that it is so open for exploitations and problems once you don't do it completely right. You can prove and disprove the existence of god using this theorem, as well the correctness of religion and its incorrectness against the correctness of science. The number of horrible arguments carried out in the name of Gödel's incompleteness theorem is so large that we can't even count them all.
But if I were to give the theorem in a nutshell I would say that if we have a list of axioms which we can enumerate with a computer, and these axioms are sufficient to develop the basic laws of arithmetics, then our list of axioms cannot be both consistent and complete.
In other words, if our axioms are consistent, then in every model of the axioms there is a statement which is true but not provable.
Caveats:
- Enumerate with a computer means that we can write a program (on an ideal computer) which goes over the possible strings in our alphabet and identify the axioms on our list. The fact the computer is "ideal" and not bound by physical things like electricity, etc. is important. Moreover if you are talking to high school kids which are less familiar with theoretical concepts like that, it might be better to talk about them at first. Or find a way to avoid that.
- By basic laws of arithmetics I mean the existence of successor function, addition and multiplication. The usual symbols may or may not be in the language over which our axioms are written in. This is another fine point which a lot of people skip over, because it's usually clear to mathematician (although not always), but for high school level crowd it might be worth pointing out that we need to be able to define these operations and prove they behave normally to some extent, but we don't have to have them in our language.
- It's very important to talk about what is "provable" and what is "true", the latter being within the context of a specific structure. That's something that professional mathematician can make mistakes with, especially those less trained with the distinction of provable and true (while still doing classical mathematics, rather some intuitionistic or constructive mathematics).
Now, I would probably try to keep it simple. VERY simple. I'd talk about the integers in their standard model, and I would explain the incompleteness theorem within the context of this particular model, with a very specified language including all the required symbols.
In this case we can simply say that if $T$ is a list of axioms in our language which we can enumerate by an ideal computer, and all the axioms of $T$ are true in $\Bbb N$, then there is some statement $\varphi$ which is true in $\Bbb N$ but there is no proof from $T$ to the statement $\varphi$.
(One can even simplify things better by requiring $T$ to be closed under logical consequences, in which case we really just say that $\varphi\notin T$.)
${\underline{First}}$: The statement of Gödel's theorem(s) requires some knowledge of what axioms and proofs are. To really get a good feeling for what this is, I believe that one would need to work with it. So it is difficult to give a simple description of Gödel's theorems here in any short way. One will almost certainly say something that isn't completely (pun intended) true.
I can recommend the book Gödel's Proof by Nagel and Newman. I can also recommend the book Gödel's Theorem: An Incomplete Guide to Its Use and Abuse by Torkel Franzén. Both of these books aren't too expensive and they are fairly easy to read. (Disclaimer: I haven't actually read all of Franzén's book).
${\underline{Second}}: $That said, this is how I would attempt to explain the whole thing. In high school and, hopefully, earlier you learn for example how to add, subtract, multiply, and divide numbers. You might have learned that numbers are good for counting things. If you have a business, you use numbers to keep track of sales and for that we need to be able to "use math" with the numbers.
Now, you have probably also by now learnt that there are rules in math. We for example now that $4 + 7 = 7 + 4$. The order doesn't matter when we add numbers. One can't, for example, divide by zero. And so it is not hard to understand how math is built up by all the rules for how you are allowed to manipulate numbers.
Now, mathematicians (and other people) have tried to figure out if it is possible to write down a list of axioms and some rules of logic that would "give us all" of mathematics. We in particular want the axioms to "contain" "basic arithmetic" (think of arithmetic as doing math with the natural numbers). An axiom is something that we take for granted. It is a bit like a definition in that we don't have to prove it. An axiom is true because we say so.
With the axioms we have (want) rules for how to deduce new things. From the axioms, we might be able to prove that something is true or false. (If you want to see something concrete, you could look up the "axioms" of what a group is. With these "axioms" one can write down a proof that the so-called identity is unique. So here you have an example where we start with a definition and prove that a statement is true).
Part of what we require is that a statement is either true or false. If I write the statement that $\pi = 22/7$, then that is a false statement. If I write that $\sqrt{2}$ is irrational (as a real number), then that is a true statement. It might not be as obvious. So how would I prove that this is true. Well, using the rules of logic I can prove that from the axioms the statement follows.
Now a question: Since we are saying that all statements are either true or false, can we, given a statement, always arrive at a proof? That is, can we prove that any given statement is either true or false? If we (in theory) can either prove or disprove any given statement, we say that the system is complete. We would of course like a complete system.
Another question is: Can we prove that our system of axioms will never lead to a contradiction? That is, is it possible that we might have a statement that we can prove is true and false at the same time? If this does not happen we say that the system is consistent. Having a consistent system is of course essential. If one statement existed that is both true and false, then you can prove that all statements are true and false. That would be bad.
And with these two questions is problem located.
The answer is: It is impossible to write down a axiomatic system that while being consistent is also complete.
So if, in the "design" of the axiomatic system we want to make sure that we can't have theorems that are true and false at the same time, then we will have statements that we can't write down a proof of. We will have statements/theorems where we can't decide whether the statement is true or false. In fact we will have statements that we can prove that we can't prove i.e. continuum hypothesis
I'm not sure it's worth adding yet another discussion, but the following presentation of Gödel's theorem, due to Raymond Smullyan, is extremely simple. Suppose that you have some sort of machine for printing out statements about things. The machine might be some mathematical system, and instead of "printing out" statements it contains methods for "proving" statements. Or it could be a literal machine that actually prints statements on a long roll of paper. It could even be a silk top hat containing slips of paper with claims written on them. Whatever it is, we'll call it $\def\M{\mathcal M}\M$, for "mathematics" or "machine". (Or "mathematician"!)
Now suppose that among the statements that $\M$ might, or might not, print, assert, prove, or contain, are statements in the following forms, with the following interpretations:
$$ \begin{array}{rl} \mathtt{P*}x & \text{“The machine $\M$ will print $x$”} \\ \mathtt{NP*}x & \text{“The machine $\M$ will not print $x$”} \\ \mathtt{PR*}x & \text{“The machine $\M$ will print $xx$”} \\ \mathtt{NPR*}x & \text{“The machine $\M$ will not print $xx$”} \end{array} $$
For example, $\mathtt{P*FOOFOO}$ means that $\M$ will at some point print $\mathtt{FOOFOO}$. $\mathtt{PR*FOO}$ means the same.
We would like to find some implementation of $\M$ that prints all possible true statements. (Or, if it's a hat, it should contain slips of paper with all the true statements.) Unfortunately, it is the case that any $\M$ that prints all true statements must also print some false statements as well. Or conversely, any $\M$ that prints only true statements must fail to print some true statements. This is not hard to see: just ask whether $\M$ prints $\mathtt{NPR*NPR*}$. This is an assertion that $\M$ does not print $\mathtt{NPR*NPR*}$. If $\M$ does in fact print $\mathtt{NPR*NPR*}$, it has printed a false assertion. On the other hand, if $\M$ fails to print $\mathtt{NPR*NPR*}$, then $\mathtt{NPR*NPR*}$ is true and $\M$ has failed to print the true assertion $\mathtt{NPR*NPR*}$.
So far everything is fairly simple. The stroke of genius (and the difficult details) in Gödel's theorem is that arithmetic is sufficiently expressive to be able to express $\mathtt{NPR*}x$. This means that any machine (or system) $\M$ that is capable of expressing certain simple arithmetic properties is also able to express the property $\mathtt{NPR*}x$, which asserts that $xx$ will not be produced by $\M$ itself; it can then express a complex statement of arithmetic which amounts to asserting $\mathtt{NPR*NPR*}$. If it prints this complex statement $\mathtt{NPR*NPR*}$ it has printed a falsity; if it fails to print the complex statement, it has failed to print a truth.
Therefore, there is no machine that can print all the true statements of arithmetic unless it also prints some false statements of arithmetic (because one such statement is $\mathtt{NPR*NPR*}$, which says "this machine never prints $\mathtt{NPR*NPR*}$"); there is no logical system that can prove all the true statements of arithmetic unless it also proves some false statements of arithmetic (because one such statement is $\mathtt{NPR*NPR*}$, which means "this system cannot prove $\mathtt{NPR*NPR*}$"); there is no silk top hat that contains slips of paper with all the truths of arithmetic unless it also contains some slips with false statements (because one such statement is $\mathtt{NPR*NPR*}$, which means "the hat does not contain a slip that says $\mathtt{NPR*NPR*}$"), and so on.
It's not at all obvious that such an arithmetic formula could exist, which somehow expresses $\mathtt{NPR*NPR*}$ for a particular machine $\M$, but that's the technical part of the proof, and it's why Gödel is considered a genius.