Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
Describe, sure. Give a genuine sketch of a proof, no. –  André Nicolas Jul 27 '13 at 15:48
26  
Hilbert: "We must know, we will know." Godel: "We won't know, we can't know." –  RghtHndSd Jul 27 '13 at 15:51
7  
There are some books by Smullyan that do a good job of this, en.wikipedia.org/wiki/Raymond_Smullyan#Logic_puzzles –  Will Jagy Jul 27 '13 at 15:53
2  
I once attempted a blog post on a series of closely related topics, mostly as a consequence of an article by Richard Elwes on recent work of Harvey Friedman. You may find it interesting. –  Andres Caicedo Jul 27 '13 at 15:55
7  
I recommend to read the "Gödel, Escher, Bach: An Eternal Golden Braid" by Douglas Hofstadter, I found it very, very interesting and, also, related to the topic. Surprised no one have recommend it yet... –  m0nhawk Jul 28 '13 at 7:02

13 Answers 13

up vote 46 down vote accepted

The problem with Godel'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 Godel'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 simple 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$.)

share|improve this answer

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

share|improve this answer
2  
I can only hope that what you wrote is correct, because I found it to be highly accessible to me (as somebody with a less than impressive math education). The only thing which slightly trips me up: you (mathematicians in general, I guess) talk about 'proving', but what you are really doing is deducing implications, right? Like, you are only proving that if your axioms are true then some statement is also true (or false). –  Frerich Raabe Jul 28 '13 at 21:43
    
...hm, now that I think about it, that's probably what people do in real life when "proving" stuff as well: explaining how things come to be based on things everybody agrees on. –  Frerich Raabe Jul 28 '13 at 21:43
2  
@FrerichRaabe: Thanks. Take what I have written with a grain of salt. It is simplified. As I wrote in the beginning, it is difficult to give a simple explanation. That said, I hope that what I have written will give the right idea of what is going on. And, you are basically right. At the root, mathematicians deduce statements from axioms. We don't talk about if the axioms are true, we take(define) them as true. It might be more of a philosophical question, but I would say that we are not necessarily claiming that reality fits the axioms (even though the give a good description of it). –  Thomas Jul 29 '13 at 0:51
1  
Well explained. Thanks –  Sara Tancredi Jul 3 at 0:52

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!

share|improve this answer
8  
It is nice that you provide your book, but, in the interest of self-containment, it would be best if you could bring the relevant ideas here. –  robjohn Jul 28 '13 at 10:30
8  
That's a rather silly comment. There would have been precisely zero point, wouldn't there, in replicating Asaf's perfectly sensible and perfectly mainstream quick remarks at similar length. The link is evidently for those who would welcome a somewhat more expansive treatment along similar lines. –  Peter Smith Jul 28 '13 at 11:59
1  
"Book" might be misleading here, the freely available chapter the OP is referring to is 7 pages long. –  Did Jul 28 '13 at 12:33
6  
If that is the case, this might have been better as a comment to Asaf's answer. –  robjohn Jul 28 '13 at 12:35
1  
Chapter 1 is a hearty and fulfilling read. @robjohn is right, some excerpt belongs here, such as the first paragraph of section 1.4. I now proffer my own conjecture, true and unprovable, that the more you read about Godel the more you feel stoned. Emotions rise, logic feels foggy and defeated. –  BobStein-VisiBone Jul 28 '13 at 14:31

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.

share|improve this answer
1  
Oh yes, it is worth adding this! And for anyone who wants to follow this up, start with the first chapter of Smullyan's simply wonderful book Gödel's Incompleteness Theorems, and keeping reading ... –  Peter Smith Jul 28 '13 at 21:28
    
I get stuck at $\mathtt{NPR*NPR*}$ : what's the double $\mathtt{*}$? Previous invocations of $\mathtt{*}$ appear to have a variable bound after the last $\mathtt{*}$. Also, in "does not print $\mathtt{NPR*NPR*}$." - is there an 'N' too much? –  Frank Meulenaar Aug 1 '13 at 9:41

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.

share|improve this answer
4  
You might want to replace "Qvod erat demonstrandvm. ${}\ \ \blacksquare\ {}$" by either "Qvod erat demonstrandvm." or "${}\ \ \blacksquare\ {}$". –  Did Jul 28 '13 at 7:37

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.

share|improve this answer
2  
You probably want to say a bit more. The point of having arithmetic is that we can talk about recursive sequences (such as factorials, towers of exponentials, Fibonacci sequences, etc), and any computer program or formal system is essentially producing recursive sequences, so we can use this to talk about proofs, via "coding". This representation allows us to "diagonalize" and so produce statements that are unprovable. –  Andres Caicedo Jul 27 '13 at 15:59
2  
(The point is that it is not really arithmetic that we care about, but the possibility of discussing/mimicking a formal system within the system itself.) –  Andres Caicedo Jul 27 '13 at 16:00

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.

share|improve this answer
4  
That's a horrible way of explaining Godel's incompleteness, which will assure people will not understand it completely, and its necessarily requirement. Then you get questions (here, and elsewhere) "We know that there are no complete and consistent theories ...". No, that's definitely not a good way of explaining. –  Asaf Karagila Jul 28 '13 at 11:50
    
I admit this. You are correct, but it is still how I would explain it to a layman. –  oxinabox Jul 29 '13 at 5:30
1  
Then please don't. How does the fact that the theory of real closed fields is complete, consistent, and non-trivial? Oh yeah, it is also recursively enumerable. –  Asaf Karagila Jul 29 '13 at 10:05
2  
+1 Good answer, and appropriate for the layman who is looking for a short explanation of this size upon which to ponder. –  Matt Sep 5 '13 at 1:15
1  
In most formulations of Gödel's theorems one uses zero, successor, addition, and multiplication only, so I guess that would be called "Successor, addition, and multiplication of the natural numbers." Do real closed fields operate on a theory much larger than this or much smaller than this? At any rate the answer to the OP's question definitely has to state exactly what is meant by the formal system in question. –  Ray Toal Mar 16 at 21:09

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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 rules 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 rules 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.

share|improve this answer

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.