Gödel's Proof

There is an idea of reason in the Universe. It is an abstraction which mathematicians have never been content with. Given that scientists exclusively use logic (or mathematical reasoning) for theories and experiments it is of incredible importance to know the limits of logic. It turns out that the study of math itself, metamathematics, has amazing insights on what is knowable.

In 1931 an unassuming paper was published in a German mathematics journal, the title of the paper (translated to English) was 'On Formally Undecidable Propositions of Principia Mathematica and Related Systems I'. It is a confusing title and the kind of paper which I would not understand. The author was a 26 year old Austrian named Kurt Gödel and he had just created a revolutionary idea, but as with so many great ideas it was not simple and it took great minds to fully appreciate it.

The ideas he put forth have been extremely influential and the collective name for the theories that grew from it are known as Gödel's incompleteness theorem. This theorem is a revolutionary outcome in mathematical logical that has implications for not only the philosophy of mathematics, but philosophy in general. It is thus surprising how relatively unknown the theorem is to the general public and even many scientists. I recently read the book Gödel's Proof by Nagel and Newman in just a few sittings at a coffee shop. It is a short and concise explanation of the proof that incrementally brought me closer to understanding the intricacies of Gödel's works.

Gödel's incompleteness theorem is a massive mountain of ideas that I will not attempt to conquer, but I think it is important that everyone at least gets a view. Gödel basically found that no solid guarantee is possible that mathematics is entirely free of internal contradiction. However, Gödel was not out to trash mathematics, contrarily he used mathematics itself to temper the reach of mathematics and place constraints on what is possible to known through mathematics much like a physicist theorizing that a black hole's event horizon places a limit on spaces which the physicist could actually go and measure. Gödel created a new technique of analysis and introduced new probes for logical and mathematical investigation.

The specifics of Gödel's proof even as outlined on wikipedia are extremely complicated (the entire proof is long and there are on the order of 200 links in the article so by the time you were done reading all of the prerequisite mathematical definitions you would have read thousands of pages) for anyone without (or with) extensive mathematical training, so I must admit that I don't understand it completely and not have I attempted to read the actual paper. I want to present here the shortest definition of Gödel's theorem not the the most rigorous.

The key to Gödel's incompleteness theorem is a concept of mapping. In the information age the concept of mapping or coding is familiar to many as in the case of mapping Morse code dots to letter characters. In the explanation that follows take it as a given that it can be shown that all logic systems are equivalent to or mappable to the operators we will be using; this assumption is vital, and I can't quite explain it without detail so I refer the inquisitive mind to read Nagel and Newman's book.

Let us construct a simple logic system using the arbitrary operators P, N, ⊃, and x that have certain properties which we take as given by the table defined below. In the left column a combination of operators is given and in the right column a definition in English of the operators meaning is given.

P⊃x	'print x'
NP⊃x	'never print x'
PP ⊃x	'print xx'
NPP⊃x	'never print xx'

We can combine these statements and create more complicated statements. For example P⊃y where y=P⊃x would mean 'print P⊃x' (note that implicitly I am also using the equals operator). Crucially then NPP⊃x would mean 'never print xx', and this statement could also be written NP⊃xx.

Next ponder what the last statement used on itself means. The statement NPP⊃y where y=NPP⊃ would mean 'never print NPP⊃NPP⊃', but this strange statement could also be written NPP⊃NPP⊃.

So either our system prints NPP⊃NPP⊃ or it never prints NPP⊃NPP⊃. It must do one or the other. If our system prints NPP⊃NPP⊃ then it has printed a false statement because the statement contradicts itself by self reference once it is printed. On the other hand if the system never prints NPP⊃NPP⊃ then we know that there is at least one true statement our system never prints.

So either there are logic statements which may be printed which are false statements, or there are true statements which are never printed. Our system must print some false statements if it is to print all true statements. Or our system will print only true statements, but it will fail to print some true statements.

In the example above I have taken arguments very similar to that in Raymond Smullyan's book Gödels Incompleteness Theorems in order to create an extremely concise, but hopefully accurate description of what lies at the core of Gödel's insight. In Nagel and Newman's book they explain Gödel's proof in much more detail by working out the details of mapping. For example in the explanation above I mapped mathematical statements to the idea of printing, but print could be equivalently be existence. Further, Nagel and Newman argue as Gödel did that all formal axiometric systems can be mapped in some way such that even the most complicated mathematical systems using the common operators of +,-,=, x,0,(,),⊃ and so on can be shown to be incomplete.

Gödel's incompleteness theorem has many forms and implications. Briefly I will demonstrate an analogous, but weaker form of Gödel's incompleteness theorem by analogy to the halting problem. I believe this demonstration is of importance to those of us immersed in the information age and perhaps easier to grasp or at least more applicable than Gödel's work.

The halting problem is to decide whether given a computer program and some input, whether the program will ever stop or will it continue computing infinitely. The key to the halting problem is the concept of computation and algorithms. In the original proof by the enduring Alan Turing specific meanings to the concepts of algorithm and computation were defined. He used a computational machine now known as a Turing complete computer, or a Turing machine. The definition of what constitutes a computer is to the halting problem what the mapping of symbols is to Gödel's theorem. It is at the heart of the problem, and thus actually one of the harder points to define so I will again leave that task as an exercise to the reader.

So lets look at two psuedocode programs and lets imagine that we also have a very special program written by a genius scientist which is called Halting. The scientist claims that Halting can correctly tell your own code B(P,i) whether a program halts.

Program B(P,i)
  if Halting(P,i)==true then
    return true // the program halts
  else
    return false // the program does not halt


Now here is the important part. The genius scientist claims we can analyze any kind of computer program, this is indeed the crux of the halting program, we want to know if any and every program stops. Now imagine a program E that takes X, which is any program, as an argument.

Program E(X)
  if B(X,X)==true then
    while(true) //loops forever
  else
   return true


The first thing E does is take B and passes it X for both arguments. Program E will get back from B either true or false. If it receives back true it will enter an infinite loop and if it receives back false it will terminate.

So suppose I take B and feed it E for both arguments. What answer will B(E,E) give? Think about it.

We will be running our special Halting program on E(E) which will then run the program B(E,E). The answer to B(E,E) will either be either true or false. If the result is false the program E actually returns true and halts immediately; if the result is true then Halting thinks our program does halt, but the program E throws itself into a loop upon this condition and will never halt. Either way program E lies. E was written very craftily to break B on purpose, but nonetheless the damage is done. E cannot be made reliable even in principle. It matters not how clever you are and or how powerful your computer is. There is simply no reliable computer program that can determine whether another program halts on an arbitrary input. The incompleteness problem may have seemed a little bit distant and philosophical, but if you have read this far it should be evident that the halting problem has deep implications computing.

What does Gödel's theorem mean for the real word, experimental verification, and deductive sciences? Well take for example the Banach-Tarski paradox which states that a solid ball in three dimensional space can be split into a finite number of non-overlapping pieces, and then be put back together in a different way to yield two identical copies of the original ball. This process violates sensible physic notions of conservation of volume and area. It turns out that Banach and Tarski came to this conclusion based upon deductions from the Axiom of choice. Now, whether we know anything at all about the axiom of choice we do know that the deductive conclusions drawn from it are in violation of physics. Thus, a physicist could argue that the axiom of choice is not a valid axiom for our Universe. Within mathematics it is unknown, unprovable Gödel says, whether or not we should accept the axiom of choice, because it is after all an axiom. The argument for whether a given axiom is to be accepted must be discussed outside the confines of the logic structure one is arguing about. It turns out that the axiom of choice is important for many other really important mathematical proofs which are used in physics all the time. I don't know what to make of it really, perhaps a mathematician out their should weigh in on this question.

Another important theorem that goes along with Gödel's theorem is Tarski's undefinability theorem. Tarski's undefinabtliy theorem makes a more direct assertion about language and self referential systems. Basically any language sufficiently powerful to be expressively satisfying is limited. In summation we have two vital points to the concept of incompleteness.

1.  If a system is consistent, it cannot be complete and is limited.
2. The consistency of the assumptions or axioms cannot be proven entirely within the system.

The repercussions of the meta analysis of logic are profound and subtle. Gödel really has thrown us for a loop. It is unclear if we should draw the line and say this is just a mere curiosity of mathematics or a deep truth about the Universe. It has been proposed by Douglas Hofstadter (author of Gödel, Escher, Bach) that consciousness itself comes from a kind of 'strange loop' induced by a self referential system in our minds. Primarily, I think we can conclude that Gödel's incompleteness theorem implies that in most situations the tools science has to analyze the world are more than adequate because the situations are not self referential. However, I do see a limit to what we can know about the Universe. As physicists forge forward, generally quite successfully, in understanding the Universe it appears that there really is some consistent mathematical basis for our Universe. Many physicists are searching for this mathematical basis to the Universe, it is the so called theory of everything. But does Gödel's result imply that this mathematical basis cannot be self consistent?

Consider this scenario. One day our most powerful, successful, and comprehensive theory ever will predict something that experiment cannot verify or worse an experiment will patently disagree with. Some will argue that the theory must be thrown out because classically the scientific method states that a theory disagreeing with experiment, or making nonsense predictions, is untenable. Another theory will be introduced that makes consistent and testable predictions, however this theory is not able to predict the most intricate traces of nature. Actually, that first case kind of sounds like string theory. Perhaps we will have to start talking about theories being incomplete instead of wrong one day.