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.

G34.3

Wow, there really is something new to learn everyday.

I Hate Astrology

Perhaps it is cruel to snuff out the shinning gleam in the eyes of a person who upon hearing that I am an astronomer exclaims, "Oh, I love astrology!" and  I reply, "No, I study ASTRONOMY." But they don't understand it. The subtle differences in syllables of the words belies the vast gulf in empirical tendencies between the separate endeavors and it is too much to explain. I simply walk away.

I hate astrology and I hate when people get astronomy and astrology mixed up. I could be more understanding, but I have to choose my battles. I meet a lot of interesting people in coffee shops, bars, airplanes, parties and wherever else life takes me and when someone gets excited about the fact that I study astronomy it means they have a deep curiosity about the skies above. That curiosity is occasionally deeply misguided with astrology and their questions are so fundamentally misconceived I struggle to answer them with candor and accuracy (for example they ask, 'Do the planets affect our daily lives?' and I hesitate to answer honestly that we must consider their gravitational pull, so the answer must be yes). On the other hand I meet people who are genuinely interested in massive collections of gravitationally bound glowing gas and I am very happy to answer their questions.

There is a real danger when logic, or pseudologic, is applied to astrology. Recently there was an uproar about the shifting of the zodiac that made it into some news headlines. Briefly I shared the frustrated sentiments of astrologers because the shifted zodiac has been well known for some time, why is the public just now hearing about it? The book in the image above is from the seventies and claims right there on the cover that, 'Most astrology is unscientific and inaccurate', and goes on to explain the shifted zodiac and how to have a movie ending romance. The ideas in this book are the apotheosis of dangerous thought. A little bit of knowledge is a very dangerous thing when combined with pseudologic in the guise of rigorous proof. It has also not escaped my observation that many of the people I have known who believe in astrology also believe in God as if to demonstrate the utter confusion and inconsistency of their minds. I don't mean to badger defenseless people here. This is simply an honest expression of how I feel. I have summed up my sentiments into a paragraph which I think would be nice to place on a card with which to hand out to people who confuse astrology with astronomy:

I cannot rightly conceive of a logic which would allow one to study such disparate phenomena of love, planets, stars and come to see any connection. Perhaps, desperate for meaning people find it wherever they look; conclusions are forged before the data have been taken. Those who would apply science to astrology may as well attempt to apply science on whom to love and sociologists do study what makes a lasting relationship and neurobiologists study what chemicals are active in the brain during feelings of love, but no scientist will claim that Romeo shouldn't love Juliet. I believe science and an understanding of natural phenomena adds to the beauty life, but pseudologic and lies even when propagated with good intentions ultimately lead to pain and suffering. The human mind has the ability to find patterns anywhere, indeed often where they do not exist.

Making sense of a visible quantum object


Quantum mechanics predicts that nature is fundamentally uncertain. Particles are in multiple states at once; particles are here and there. As we extrapolate these properties of nature to macroscopic objects the results are counterintuitive. The counterintuitive predictions of quantum mechanics should be an observable phenomena, and indeed they are. In this talk the intuition is examined and in this paper by the same physicist, Aaron O'Connell, the physics is examined.

So I haven't been posting lately. I have been drowned in opportunities, hit by funding woes, and frankly it feels like my mind is melting. I will probably post more aggregated non-original content, like this post, but I also have lots of ideas and new things I am working on.