Gödel’s Incompleteness Theorem

One of my favorite mathematical theorems is Gödel’s Incompleteness theorem. There have been several books written on it. My favorite one is Gödel, Escher, and Bach: An Eternal Golden Braid by Douglas Hofstadter. Just recently one of my favorite channels on You Tube, Numberphile, posted several videos on the topic: Gödel’s Incompleteness Theorem, Gödel’s Incompleteness Theorem (extra footage 1), and Gödel’s Incompleteness Theorem (extra footage 2) all interviews with professor Marcus du Sautoy.  They do a better job than I can at describing what the Theorem is but I’ll give it a shot. If I confuse you, I refer you to the videos or Hofstadter’s book.

First, I draw your attention to the paradox represented by the following sentences:

The next sentence is true. The previous sentence is false.

If you think about it for a minute you will see that neither sentence can be either true or false. If the first sentence is true then it tells us the second sentence is true. But the second sentence tells us that the first sentence is false. If, as the first sentence asserts, the second sentence is true then the first sentence must be false in which case the second sentence must be false. As you can see, we can’t come to a consistent conclusion about the truth or falsity of theses sentences.

What Kurt Gödel did was encode mathematical statements such that each one had a unique number that was derivable from the axioms used to prove it. Then he encoded the statement that asserted that: “there is no proof of this statement”. If there is a proof of the statement, the statement is false. If there isn’t a proof of the statement, the statement is true but isn’t provable thus there is a true statement that is not provable within the constraints of the mathematical system.

This has profound philosophical implications. It implies that there are things that are true but unprovable. This other disturbing conclusion is that there may be no such thing as objective reality. Reality may be a product of our interpretation of our sensory input and yet everyone may be perceiving the world differently.

So then we think about some of the more practical aspects of this idea. Take for example programming languages. Programming languages are formal mathematical systems for expressing procedural statements. They are subject to the same analysis as other formal mathematical systems such that given any particular language, there are truths that cannot be expressed in it.

Taken to the extreme, all sufficiently sophisticated languages can be shown to be ultimately equivalent. This is called being Turing complete. Since this class of languages can be shown to be equivalent, it can be deduced that there are some truths that cannot be programmed.

Further, it can be extrapolated that since our minds are finite electro-chemical systems that there are some truths that cannot be understood by the human mind. Perhaps that is as close to a proof of the existence of a superior being as we’ll ever be able to understand.

Sweet dreams, don’t forget to tell the ones you love that you love them, and most important of all, be kind.