Conceptual Overview of Gödel's Incompleteness Theorem

Gödel essentially showed that given any formal mathematical system with the natural counting numbers 1,2,3,..., where the natural counting numbers have their usual symbolic meaning of "how many," it was always possible to come up with a completely different "symbol interpreter", where each number did not have it's usual meaning of "how many," but instead each number was interpreted by this new "symbol interpreter" as being a symbol for a mathematical statement. In this system the number 5 doesn't mean "five things" but instead is a symbol for some equation, such as "1+1=2".

If you're familiar with computer programming and the ASCII table, then consider how every equation which can be typed into a text editor is represented internally by a sequence of numbers, where each number is the ASCII number for that character.

ASCII TABLE | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

32 | 51 | 3 | 70 | F | 89 | Y | 108 | l | ||||||||||

33 | ! | 52 | 4 | 71 | G | 90 | Z | 109 | m | |||||||||

34 | " | 53 | 5 | 72 | H | 91 | [ | 110 | n | |||||||||

35 | # | 54 | 6 | 73 | I | 92 | \ | 111 | o | |||||||||

36 | $ | 55 | 7 | 74 | J | 93 | ] | 112 | p | |||||||||

37 | % | 56 | 8 | 75 | K | 94 | ^ | 113 | q | |||||||||

38 | & | 57 | 9 | 76 | L | 95 | _ | 114 | r | |||||||||

39 | ' | 58 | : | 77 | M | 96 | ` | 115 | s | |||||||||

40 | ( | 59 | ; | 78 | N | 97 | a | 116 | t | |||||||||

41 | ) | 60 | < | 79 | O | 98 | b | 117 | u | |||||||||

42 | * | 61 | = | 80 | P | 99 | c | 118 | v | |||||||||

43 | + | 62 | > | 81 | Q | 100 | d | 119 | w | |||||||||

44 | , | 63 | ? | 82 | R | 101 | e | 120 | x | |||||||||

45 | - | 64 | @ | 83 | S | 102 | f | 121 | y | |||||||||

46 | . | 65 | A | 84 | T | 103 | g | 122 | z | |||||||||

47 | / | 66 | B | 85 | U | 104 | h | 123 | { | |||||||||

48 | 0 | 67 | C | 86 | V | 105 | i | 124 | | | |||||||||

49 | 1 | 68 | D | 87 | W | 106 | j | 125 | } | |||||||||

50 | 2 | 69 | E | 88 | X | 107 | k | 126 | ~ |

For example, the string "1+1=2" is represented internally by the numbers: {49, 43, 49, 61, 50}

Symbols: | 1 | + | 1 | = | 2 | |||||

Numbers: | 49 | 43 | 49 | 61 | 50 |

Then, instead of thinking these as five separate numbers, push the numbers together to get one

Symbols: | 1 | + | 1 | = | 2 | |||||

Numbers: | 49 | 43 | 49 | 61 | 50 | |||||

Gödel #: | 4943496150 |

This isn't exactly the way Gödel did it, but I hope it gets across the conceptual idea that every equation can be converted to a unique number. This unique number is known as the equation's “Gödel number”.

The process also works in reverse — every Gödel number can be converted back to the corresponding equation it represents. In our example above we just run the steps in reverse:

- Starting with the
*huge*number 4943496150 - Break the number into its parts: 49 43 49 61 50
- Referring to the ASCII table, translate each number to the corresponding symbol it stands for:

49

→ 1

43

→ +

49

→ 1

61

→ =

50

→

2

We now have

Symbol Interpreter A: | "4943496150" | means | → | "how many" | ||

Symbol Interpreter B: | "4943496150" | means | → | "1+1=2" |

Thus a mathematical statement containing "4943496150" can be interpreted in two ways. It could be interpreted in the usual way as representing a particular "how many" type number, or, it could be interpreted in a Gödelian way as referring to the mathematical statement "1+1=2". Thus it is possible for a statement within a mathematical system to be interpreted as talking about another statement within the system itself. Gödel invented a symbol interpreter which makes it possible for statements within the system to be interpreted as talking about other statements within the system.

Hofstadter writes:

"This
unexpected double-entendre demonstrates that our system contains strings
which talk about other strings in our system. And this is not an accidental
feature, it is just as inevitable a feature as are the vibrations induced in
a record player when it plays a record. It seems as if vibrations should come
from the outside world -- for instance, from jumping children or bouncing
balls; but a side effect of producing sounds — and an unavoidable one
— is that they wrap around and shake the very mechanism which produces
them."^{2}

If a statement can be interpreted as talking about another statement within the system, is it then possible to come up with a statement which talks about

PREV | NEXT |

Endnotes:

1 Again this isn't the method Gödel used. The actual Gödel numbering scheme is a bit more complex.

2 Douglas Hofstadter,

3 It's also quite possible, even likely, that I don't know what I'm taking about.