Can someone explain Gödel's incompleteness theorems in layman terms?

Question

Can you explain it in a fathomable way at high school level?

Answer 1

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:

1. 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.
2. 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.
3. 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$.)

Answer 2

${\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

Answer 3

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}$ also means that $\M$ will print $\mathtt{FOOFOO}$.

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 is the technical part of the proof, and it's why Gödel is considered a genius.

Answer 4

Asaf, as always sensible, gives a good answer on some basics: for some amplification and further related ideas, you can download the first chapter of my book on Gödel's Incompleteness Theorems at http://www.logicmatters.net/igt/

This is certainly intended to be accessible without significant background knowledge (you just need to know that the negation sign '$\neg$' can be read 'It is not the case that'), and it tells you in informal terms what the Theorems say. So give it a go ... this opening chapter is only seven pages long!

Answer 5

In terms that I'm sure have been put on a t-shirt:

---

• Complete
• Consistent
  
• Non-trivial
  
  Choose Two

---

This is more of a wave in the direction of the meaning, but its whatI generally remember, knowing that I can look up the exact definition as required.

Complete: A system is complete if anything that can be stated, can be proved (within the system).

Consistent: A system is consistent if you can never prove a statement and its opposite.

Non-trivial: A system is non-trivial is it can be used for arithmetic calculations.

For example First Order Logic (aka Propositional Logic), is trivial, this means it can be both complete and consistent.

Answer 6

In layman's terms: Any axiomatic system which is capable of arithmetic is either incomplete or inconsistent. An incomplete system is the one in which there are theorems which may be true but cannot be proven. An inconsistent system, on the other hand, is the one in which there are contradictions. However, if we do not want contradictions, every axiomatic system which is capable of arithmetic must be incomplete. Moreover, a "stronger" result is due to Turing, who showed that the process of finding theorems that cannot be proven is undecidable. In general, a problem is undecidable if there exists no algorithm that, in finite time, will lead to a correct yes-or-no answer. In this case, the problem is undecidable because there is no algorithm that, in finite time, will tell you whether the theorem you want to prove can be proven.

By the way, the proof of Godel's Theorem is essentially a sophisticated Liar's Paradox, and the proof of Turing's Theorem uses Cantor's diagonal argument.

Answer 7

One thing not sufficiently emphasized in many accounts (although this may have improved in recent years) is the connection with computability.

In mathematics, the correctness of a proposed proof can be checked by very efficient algorithms.

Actually finding a proof is nowhere near as easy as checking its correctness after it's found.

This is essential because if one didn't insist on algorithmic proof-checking, then one could decide every question as follows: Let every true statement in arithmetic be an axiom. Then every true statement's proof could say "This is an axiom. Qvod erat demonstrandvm. ${}\ \ \blacksquare\ {}$"

The "language of arithmetic" can express things like "Every even number greater than $2$ is a sum of two prime numbers."

Gödel's theorem says you can't have a system of proof for which there is a proof-checking algorithm, and that proves only statements that are true of natural numbers, unless there are some statements in the language of arithmetic that cannot be proved or disproved within that system.

Answer 8

An informal but meaningful presentation would be to present Gödel's incompleteness theorems (and JB Rosser's trick) as rigorous versions of Richard's paradox for integers.

Create a list of English definitions of properties of natural numbers, ordered first by length of phrase and then (within phrases of equal length) by dictionary order (lexicographically). Number this list by natural numbers, starting with 1.

A natural number $n$ is said to be Richardian if it does not have the property defined by the $n$th phrase on the list. Since being Richardian is a property of natural numbers, it must appear somewhere on the list. For the $n$ corresponding to this definition, one asks if that natural number $n$ is Richardian. A paradox ensues. If this $n$ were Richardian, then it would not have the property of being Richardian. But as well, if this $n$ were not Richardian, it would mean that it was. Contradiction.

Because the English language is not formal (we have just introduced a "new" word Richardian to mean something that presumbably would not be known to any significant fraction of native English speakers), the paradox just outlined is open to a number of criticisms. However the version Gödel gives involves a numbering of proofs in a formal theory of arithmetic, and so far no one has produced an invalidating criticism of his argument. It quickly became an accepted result in the foundations of mathematics.

Answer 9

Perhaps not an actual answer, unless you stretch the term "layman" a bit. These are some excerpts from one of Scott Aaronson's lectures from his Quantum Computing course.

The Incompleteness Theorem says that, given any consistent, computable set of axioms, there's a true statement about the integers that can never be proved from those axioms. Here consistent means that you can't derive a contradiction, while computable means that either there are finitely many axioms, or else if there are infinitely many, at least there's an algorithm to generate all the axioms.

(I think it can qualify as high school level, providing that you did not skip math classes)

The proof is actually not that hard, if we cheat and use some (semi-)modern advances in mathematics:

First, though, let's see how the Incompleteness Theorem is proved. People always say, "the proof of the Incompleteness Theorem was a technical tour de force, it took 30 pages, it requires an elaborate construction involving prime numbers," etc. Unbelievably, 80 years after Gödel, that's still how the proof is presented in math classes!

Alright, should I let you in on a secret? The proof of the Incompleteness Theorem is about two lines. The caveat is that, to give the two-line proof, you first need the concept of a computer.

...

As I said, once you have Turing's results, Gödel's results fall out for free as a bonus. Why? Well, suppose the Incompleteness Theorem was false — that is, there existed a consistent, computable proof system $F$ from which any statement about integers could be either proved or disproved. Then given a computer program, we could simply search through every possible proof in $F$, until we found either a proof that the program halts or a proof that it doesn't halt. (This is possible because the statement that a particular computer program halts is ultimately just a statement about integers.) But this would give us an algorithm to solve the halting problem, which we already know is impossible. Therefore $F$ can't exist.

Answer 10

I'm just going to be honest with you. Hopefully you don't find this reply too brash.

If you want a true appreciation for Gödel's, you have to do the intellectual legwork and learn propositional and predicate logic. With that under your belt, you can read a book like Nagel, Newman and Hofstadter's "Gödel's Proof" to really get to grips with it. Gödel's Incompleteness Theorems just aren't simple enough to capture their essence in a Layman's explanation. As always, there is no royal road to geometry (or number theory!).

If you want a gentle introduction to the ideas behind Gödel's Incompleteness Theorems, there's a wealth of explanations written "for the layman" such as Logicomix, various websites, popular mathematics books, etc. I don't feel these materials generally convey the heart of the matter. It's like the difference between a postage stamp depicting the Sistine Chapel, and the Chapel itself.

Alright, all that being said, the most compressed explanation I can come up with is this: Right around the turn of the 19th century into the 20th, mathematicians such as Bertrand Russel, Gottlob Frege, Guissepe Peano and others were enamoured with the idea that logic and mathematics were, at the most basic level, the same thing. That is, all true mathematical statements could be reduced down to and derived from the laws of logic. The subtleties of the laws of logic are often difficult for people to grasp on first contact. This is why it's so important to know logic before you can proceed.

Now, skipping over a whole lot of stuff, Gödel showed that this notion was mistaken in every important sense. There are statements in mathematical logic which are of the form "I am not a provable statement"; which if false lead straight into paradox, and if true represent a dislocation between logic and mathematics - a true mathematical statement that cannot be derived from the laws of logic alone. These statements are close cousins of the ordinary language "liar paradox" which is the sentence "this sentence is false". If it's true, then it's false, and if it's false, then it's true. Similarly, if the statement "I am not provable" is true, then there's a hole in mathematics that logic can't fill. If it's false, then it's true that it's IS provable, implying it must also be unprovable, etc.

Hope that helps.

Answer 11

The following helped me with the First Theorem. I'll leave it to somebody else to add the Second.

We can use math to talk about the real world. Even though we don't find perfect points, lines, etc. outside of math class, geometry is still useful because large parts of it cross-apply to the real world. My favorite example is conic sections and planetary motion, but you can find plenty of other instances.

Turns out, we can "go meta" with this. One specific part of the real world is "mathematicians doing mathematics", and we can use math to talk about that.

Gödel's First Incompleteness Theorem is sort of the opposite of the infinite-monkeys scenario. An infinite number of mathematicians working for an infinite amount of time will never resolve all the questions you can put in front of them. Try as they might, as long as they play by the rules of math (and are working on a minimally complicated part of it) you can always put a question in front of them that they just cannot prove or disprove.

At this point, remember that there are many diverging views on the significance of that fact. I personally don't think you can judge between those views without diving into the relevant literature.

Answer 12

I can't, but Professor Eric C.R. Hehner did, in his article "Beautifying Gödel", chapter 18 in Feijen, van Gasteren, Gries, Misra (eds.): Beauty is our Business, Springer-Verlag silver series, New York, 1990, p.163-172 (PDF via his Publications List).

Answer 13

There are lots of sets of rules: school dress codes, traffic laws, the rules of Calvinball, etc. These are all valid sets of rules, but they're arbitrary - new rules can be made up that completely ignore old ones. Godel studied sets of rules where every new rule is a combination of older rules (like math where you use basic definitions to prove new rules), and he proved two theorems about them.

Godel's first theorem says that one of the following two things must be True about every set of rules that meet his conditions:

1. There must be rules that you can never prove ­­­­­­­
2. There must be rules that you can never express

Which just says that if you can prove everything you can write, then you must not be able to write everything. That doesn't seem so bad - there are things we can't write in English (e.g., what colors look like, or what emotions feel like), so why should math be any different?

You can also turn that around to say that if you can write everything, then you won't be able to prove some of the things you can write. That doesn't seem so bad either, there are lots of things we can write that we can't prove (e.g., The Liar's Paradox).

His second theorem says that if you try to define a set of rules that includes the statement:

Every rule can be proven True or False.

then that rule must be False. His second theorem just means that you can't cheat your way out of the first theorem.