So I handed in my dissertation today, after the most intense writing period of my life. Probably should have started it earlier than a week before deadline. Alas...  
 
The title is as above, but specifically, it's about Gödel's Incompleteness Theorems and how they impacted maths and philosophy. 
 
As it is, there are definitely things that a few advisory meetings would have cleared up (I'm very vague on the proofs and there are aspects of my ontological argument which don't hold), but I'm genuinely pleased it's out of the way. Anyway, I'm going to post it in 3 parts over the next days. Feel free to have a read through. I'm only really doing this because I haven't read a finished copy (family and friends proof-read it) and I'd like to hear some opinions/instigate discussion.  
 
Part III is where most of the meat is, so consider Part I introductory (it's actually neither very focused nor argumentative, so pretty useless... still.) and Part II the technical portion (which, as I said, is pretty rough and not entirely spot-on). 
 
- - - - - - 
 

 Part I

The Pledge

In 1931, a relatively unknown Austrian mathematician by name of Kurt Gödel published his paper 'On formally undecidable propositions of Principia Mathematica and related systems I' to little reaction at all; its contents were virtually impenetrable, and even those who were in possession of the acutely mathematical requirements necessary for understanding failed to comprehend the resounding impact this would have on their field. This paper serves to enlighten on the subject, challenge some existing beliefs and examine some of the philosophical repercussions that the theorems entail.

• Background

To give a sense of his character, Gödel was described as cold and aloof : he was always thinking analytically. In a particularly memorable anecdote, as retold by Stephen Hawking, Gödel was involved in the necessary preparation for citizenship through naturalization:

He studied diligently for his hearing, much more diligently than necessary. The economist Oskar Morgenstern, one of his closest friends, noticed Gödel becoming more and more upset as the hearing date approached. Morgenstern simply thought that Gödel was nervous in anticipation of the hearing. A few days before the hearing, Gödel confided to Morgenstern that he had found a serious flaw in the American Constitution. The President could fill vacancies without Senate approval, while the Senate was in recess. This, Gödel reasoned, could lead to a dictatorship.

When the examination day eventually came, Einstein (with whom he shared a very close friendship, and whom Gödel became something of a confidante for) and Morgenstern accompanied him to the meeting. Einstein, very amusingly (though, at the time worried his friend may have caused problems for himself) divulged the events:

And then [the examiner] turned to Gödel and said, Now, Mr. Gödel, where do you come from?

Gödel: Where I come from? Austria.

The examiner: What kind of government did you have in Austria?

Gödel: It was a republic, but the constitution was such that it finally was changed into a dictatorship.

The examiner: Oh! This is very bad. This could not happen in this country.

Gödel: Oh, yes, I can prove it.

Entertaining, but it also goes some way towards helping us understand Gödel. So, while he was intently focused on producing one of the most important mathematical papers of his time, his peers were busying themselves in an attempt to reduce mathematics to a system based on formal logic: the desire to produce a set of axioms which would define any theory of mathematics. For example, a computer could be programmed, with said axioms, to understand all of a given theory of arithmetic.

Key among these efforts was that of a German mathematician, David Hilbert. He developed a programme by which he intended “ to vindicate classical mathematics, including Cantor's transfinite set theory, by (I) expressing that mathematics in a formal language which could then itself be regarded as an object of mathematical study (in proof theory, or meta-mathematics), and (II) using only finitary methods to prove that this formal system of infinitary mathematics is consistent by proving that no formula of the form '0 = 1' is provable in it.”

There was one, however, who before all else realised the importance of Gödel’s work and findings. John Von Neumann “who was lecturing on David Hilbert’s work at the time, read Gödel’s 1931 paper, [and] cancelled what was left of his course and began lecturing on Gödel’s findings.” When Gödel delivered a lecture, in which Von Neumann was in attendance, he approached the young mathematician to clarify if he had completely understood what Gödel had just said (indeed, the organisers were so oblivious to his findings, that the “session transcript featured no mention of Gödel’s findings”).

Kurt Gödel had effectively ruined Hilbert's attempts (specifically (II)), and further, the entire reductionist programme. His paper dealt a marriage of blows to the community: Incompleteness Theorems One and Two .

• The First Incompleteness Theorem

Gödel posited that, for any sufficiently consistent axiomatic system, there are true statements which it is unable to prove (completeness, of course being that if a theorem is true, it can be proved). That is, we can formulate a sentence G (Gödel sentence) from the arithmetic theory T's axioms, which encodes the statement “G is unprovable in T” . This bears what would seem to be a somewhat problematic resemblance to the Epimenides, or Liar, Paradox, “All Cretans are liars”, commonly reworded as “This sentence is false”, though it's implications and method are of a much more subtle, beautifully realised sort. If G is true, it must be unprovable, and by negation, if it is provable, it must be false. The statement, however, is most definitely true and, hence, undecidable in T: where the Liar paradox goes round in circles (if it is true, it is false, and vice-versa) Gödel successfully avoids a paradox, and actually provides us with a substantial proof. We will examine the proof in acute detail in Part II, the technical portion of this paper; for now, we will focus on what it says and, exactly, what this means.

Douglas R. Hofstadter, in his fantastic 'An Introduction to Gödel’s Theorems', offers that “Godelian incompleteness immediately defeats what is otherwise a surely attractive suggestion about the status of arithmetic – namely the logicist idea that it all flows deductively form a simple bunch of definitional truths that articulate the very ideas of the natural numbers, addition and multiplication.” Such carefully worded descriptions should not be taken out of context. We should, in fact, hang upon them. One could imagine that, by showing the unprovability of certain mathematical truths, Gödel's theorem could be construed as defeating mathematics wholly and completely. Thankfully, this isn't the case. While it does put some important mathematical foundations on very shaky ground, indeed, the first incompleteness theorem is specifically targeted at an elementary theory of arithmetic, one which is concerned entirely with integers. Only an axiomatic theory of the natural numbers, capable of supporting the Peano axioms, is at risk directly (though, in Part III we will examine the theory's effect on other principles). While the theory is proven to be incomplete, this is far favourable to being ruled inconsistent; because all statements are either provable or not provable (that is, they are either true or false, but not necessarily decidable within the axioms of the theory), Gt and ¬Gt are not both proven within the same theory. And so it remains consistent.

Real numbers, for example, are safe from Gödel’s results. In fact, Gödel himself proved that a formal system of real numbers is both consistent and complete by virtue of integers being undefinable within its parameters. Thus, the axiom of succession, the peano axioms, are not represented, and so the problem which corrupts the formal theory of the natural numbers doesn't arise for the reals (we will not examine the actual proof any more closely than this).

The problem lies (again, directly; there are indirect, far-reaching implications and problems to tackle later) with computational arithmetic. Where Hilbert's Programme tried to emulate all of mathematics in a formal system, the first incompleteness theorem shows us why it was unsuccessful. Effectively, our computer from before, which has been pre-programmed with the necessary axioms to form the theory T, would not perform as desired. Here we have a machine that would not be able to understand (in this case, prove) certain true statements which it is programmed to not only utilize, but comprehend (though, this is where a large portion of the trouble lies, and we will investigate the further nuance of a machines ability to 'fathom' at another point).

• The Second Incompleteness Theorem

The second theorem differs slightly, though is intrinsically tied with the first. In fact, its existence is logically entailed by the former. It states that, simply put, 'theory T cannot prove its own consistency' (consistency being that no proof contradicts another within the theorem). More unassuming than the first, but just as damning. Gödel, though, never laid out an exact proof; rather, he sketched the idea which takes form below.

Consider: from the first incompleteness theorem, we have a T-sentence which encodes something to the effect of 'G is unprovable in T'. Therefore, we know that facts are encodable within T-sentences. Given this, we can posit that there will be a sentence which encodes the claim that '0 = 1 cannot be derived in T'. We will call such a sentence Con , as it proves T's consistency. Then, as we know that for T to be consistent, G must be unprovable, we can also encode our sentence 'G is unprovable in T', with Con (as we should be able to encode any given sentence with a statement regarding the theory's numerical consistency, assuming both the truth and negation isn't proved): specifically, 'Con → G '. We know that T can only be consistent exactly because it cannot decide G in T. Thus, if T is consistent, it cannot prove Con .

The second theorem is easier to follow, simply for the reason that it is fairly self-evident. A theory cannot appeal self-referentially in an attempt to prove its own consistency. Any example would do here, but a simple analogy will suffice. Given the sentence 'I am right', it will not do to say, 'I am right because I am right' when explaining why . Though, obviously, there is more to the consistency reasoning than this. Further, if it were inconsistent , then we could derive anything at all that we wished, from T. We could formulate “T is consistent”, “T is inconsistent”, “T is a strange loop”, or whatever takes your fancy.

• Implications

The impact that Gödel’s theorems had on mathematics, logic and formalism was slow, but significant. They proved that no attempt to completely axiomatize mathematics could be entirely successful. There will, for one, as the first incompleteness theorem shows, always be true but unprovable sentences, so the reductionist desire to relate truth and provability is corrupted. With regard to the second theorem, Gödel showed that, for similar theorems which substantiate the necessary clauses (those which appeal to Peano Arithmetic), are unable to prove their own consistency.

In fact, considering Hilbert's Programme relied up 'safe reasoning', as a foundation for proving 'riskier' proposition, we can inductively come to the conclusion that, since we cannot prove T to be consistent, it leaves any richer theory T in danger. If we cannot prove the trunk (a metaphorical trunk, not that of analytic tableaux) of a theory, the 'safe' proposition, how are we to prove that a 'riskier' one is consistent.

Moreover, and this is the truly devastating part, since it is applicable to any sufficiently rich theory-T, it renders the entire of classical mathematics unable to be formalised. Further, The necessary spark, or flair, for understanding that the human mind has, cannot be replicated in machine (we will look at this more closely in Part III).

While we can see the abject disappointment this brings to Hilbert's programme; and though it is almost universally agreed to do so, there are those who still defend formalism to an extent. Michael Detlefson, of the University of Notre Dame, posits that, while formalism is not entirely without fault, there are at least reaches of it which Gödel’s theorems would appear to leave unscathed:

Is the distinction between a theory and its efficiency reduct significant? Certain facts suggest that it may be. These include the facts that:

A. For the average familiar formal system (e.g. PA, PA , ZF , etc.) we are far from knowing what any of its efficiency reducts would look like. In particular, we don't know whether or not it is a strict subtheory of the system in question.

B. Some of these theories have significant capacities to prove the consistency of important families of their subsystems. PA and ZF, for example, are reflexive – they prove the consistency of each of their finitely axiomatizable subtheories.

This seems acceptable, if a little weak. The strength of Gödel’s theorems is that, as we have just discovered, they dash the stronger theory-T's, and allow us to disregard riskier ones. Given that Detlefson appeals to subtheories, and theories which are not specifically first-order, I take some issue with it. His point is not wrong, but relying on one formal theory to prove the consistency of one of its own subtheories seems futile. Regardless, the strength of Gödel’s theorems has been proved: first-order formal systems remain incomplete.