Essay:Gödel's incompleteness theorem simply explained

From RationalWiki
Jump to: navigation, search
Essay.svg This essay is an original work by Tetronian.
It does not necessarily reflect the views expressed in RationalWiki's Mission Statement, but we welcome discussion of a broad range of ideas.
Unless otherwise stated, this is original content, released under CC-BY-SA 3.0 or any later version. See RationalWiki:Copyrights.
Feel free to make comments on the talk page, which will probably be far more interesting, and might reflect a broader range of RationalWiki editors' thoughts.

The Rationalwiki page on Gödel's incompleteness theorems does a good job of explaining the theorems' significance, but it does not provide a very intuitive explanation of what they are. In this essay I will attempt to explain the theorem in an easy-to-understand manner without any mathematics and only a passing mention of number theory.

Explanation 1: The Vow of Honesty and Completeness[edit]

Imagine that I have to take a sacred vow: the Vow of Honesty and Completeness. This vow has two stipulations:


  1. If I am given a statement and it is false, I cannot say it out loud.
  2. If I am given a statement and it is true, I must say it out loud.


This seems like a rigorous but doable task; it seems logical to assert that I can apply these rules to any possible statement that I encounter. (Remember this feeling: it's important.) Let's look at a simple example:


(On a cloudy day)

  • My friend: It is cloudy outside.
  • Me: It is cloudy outside.
  • My friend: It is sunny.
  • Me: ...


Simple, right? Now, let's look at a slightly more complex example:


(On a cloudy day)

  • My friend: I can honestly say that it is cloudy out.
  • Me: I can honestly say that it is cloudy out.
  • My friend: I cannot honestly say "it is sunny out."
  • Me: I cannot honestly say "it is sunny out."


Do you understand why I can say the second sentence? If not, let's look at the first in more detail. My friend says "I can say 'it is cloudy out,'" which is the same as saying "'It is cloudy out' is true." Since that sentence as a whole is true, I am allowed (in fact - I have to) say it. In the second sentence, he says "I cannot say 'it is sunny out,'" which is the same as saying "'It is sunny out' is false." Since this sentence as a whole is true, I must say it.

Still, it certainly looks like my Vow's rules can be applied to any particular case, no matter how convoluted-sounding. This, however, is where Gödel said no. There are some statements, he said, that show that it is impossible to be both completely accurate and completely universal (that is, be able to apply my vow to all statements). How did he show this? Let's look at another example conversation, in which my friend is replaced by the crafty Gödel:


  • Gödel: Imagine the sentence G, which equals "'I can never say G' is true."


Now I am confronted with a serious problem. If I say Gödel's sentence in the quotations, then it is false, since I did say "'I can never say G' is true." This means that I uttered a false statement, which is against the rules of my Vow. But if I remain silent, then "'I can never say G' is true" is a true statement, and then I am in violation of the Vow because I am supposed to always say a statement that is true when I hear it.

Confused? Let's break it down:


  • If I say G, which is "'I can never say G' is true," then G is false and I have broken the rules.
  • If I do not say G, which is "'I can never say G' is true," then G is true and I have broken the rules.


Thus, said Gödel, it is impossible to be completely accurate and completely universal. In terms of the example of the Vow, this means that no one can really be both Honest and Complete; there are some statements that you can never say even though they are true. If this still doesn't quite make sense, read on...

Explanation 2: The magic printer[edit]

Imagine that my printer is magical. When I type a true statement into my computer, it will print out that statement. When I type a false statement into my computer, it does nothing. Let's look a basic example:


(At 12:00 noon)

  • Me: It is daytime.
  • Printer: It is daytime.
  • Me: It is night.
  • Printer: ...

Notice how this is almost exactly the same as the previous example - like me under the Vow, the printer will print a statement if it is true and do nothing if it is false. Now, in addition to simple statements, I can use pre-programmed commands to make the printer examine some more complex statements. I have four of these at my disposal:

1. P (print) - this is the equivalent of, "I can print the statement ___."

  • For example:
  • Me: P it is daytime.
  • Printer: P it is daytime.
  • Or:
  • Me: P it is nighttime.
  • Printer: ...

2. NP (not-print) - this is the equivalent of, "I cannot print the statement ___."

  • For example:
  • Me: NP it is nighttime.
  • Printer: NP it is nighttime.
  • Or:
  • Me: NP it is daytime.
  • Printer: ...

3. DP (double print) - this is the equivalent of, "I can print the statement ___ twice."

  • For example:
  • Me: DP it is daytime.
  • Printer: DP it is daytime.
  • Or:
  • Me: DP it is nighttime.
  • Printer: ...

4. NDP (not-double print) - this is the equivalent of, "I cannot print the statement ___ twice."

  • For example:
  • Me: NDP it is daytime.
  • Printer: ...
  • Or:
  • Me: NDP it is nighttime.
  • Printer: NDP it is nighttime.

If this doesn't make sense, I recommend reading it over again and imagining each example as you go. Then, if you want to get creative, come up with a few more yourself and try to imagine what the printer would do.

Now, let's say I walk away from the computer and Gödel sits down in my place. He types:

  • NDP NDP

Or, in simple language, "I cannot print twice "I cannot print twice." " What will the printer do? If it prints NDP NDP, then it is printing a false statement, because it can print NDP NDP. But if it does nothing, then NDP NDP is true but it refused to print it, which it isn't supposed to do. As a result, it follows that there are some true statements (in this case, NDP NDP) that the printer will not print.

Do you see how this is almost exactly the same as the previous example? In both cases, Gödel shows that it is impossible to be completely truthful and completely universal; you can never say every true statement without saying some false ones, or, alternatively, you can never say only true things without being forced to withhold some true statements.