Let me start with some autobiography. I was 17, a member of the school essay society, listening to a paper by the form atheist, who was putting forward a fairly abrasive version of reductive materialism. We were just blobs of protoplasm, bits of the primaeval slime that had evolved a bit, but still essentially a cocktail of carbon, hydrogen, oxygen and nitrogen. He was very persuasive. But then, I wondered, what did he think he was doing? Was he just trying to manipulate us, to program our nervous systems to go along with his opinions? No; he claimed to be in the right, to have reason on his side, to be pointing pout to us where the truth lay. But how could this be so, I asked, on his assumptions? If he was right, what we did, including what we said and what we thought, was completely determined by the material in our bodies and environment, and the laws of chemistry and physics that lay down what their movements and reactions must be.
It is an argument that has often come to me since, when I have heard people arguing against reason, and making out that all our apparent reasoning is merely the effect of our hormones, our infantile neuroses, or the economic interests of our class. In each case I counter that the very attempt to argue rationally belied materialism, Freudianism, or Marxism. It is a special case of a more general argument that has wide application in philosophy. When I started philosophy, Logical Positivism was very much in vogue, and my tutor tried hard to get me to believe the Verification Principle. So I asked him whether it was a tautology, perhaps showing some new meaning being given to `proposition', or `meaningful', so that only some selected instances could be accorded the favour of being thus described. He said No. Was the Verification Principle, then, an empirical proposition, discovered by careful research in which lots and lots of propositions had been examined, and none found to be meaningful except those that were analytic or empirical. He admitted, albeit a trifle reluctantly, that no such research had been carried out. In that case, I concluded triumphantly, the Verification Principle, if it were true, was itself meaningless, hoist by its own petard. He did not think it a very good argument, and told me to try harder to believe. But I thought it was a very good argument, and still think so, and regard it as one of the few arguments available to a philosopher when thinking about metaphysics, at a level of abstraction where most arguments fail to engage. See what it says about itself. Often it seems to be undercutting itself, cutting off the branch on which it is sitting, so to speak. It is silly to climb a ladder which is due to be thrown away when you have climbed it. Safer, and much more sensible to stay on the ground until one has found a destination which does not make out that really it is inaccessible.
I first heard of Gödel's Theorem in June 1948, when I had taken Maths Mods, and was wanting to change to Greats. I was told that there was some weird bit of mathematics involving prime numbers which was very strange. I suppose I had been trying to formulate my argument against materialism. Nine years later I was able to go to Princeton to study mathematical logic properly, and on my return tried out my argument on colleagues at Cambridge, then in a paper in 1959 to the Oxford Philosophical Society, which was finally published in 1961.
Gdel's argument is self-referential. It is a development of the Epimenides paradox, known to St Paul. Epimenides was a Cretan and said that All Cretans were Liars. A modern version would be a backboard on which was written:
If Pontius Pilate asks one of you `What is truth?' you can answer `I can't tell you, if I am only a machine---indeed, if I were, I should not be able even to understand the question.' (Unfortunately, when a tutor asks you, he is not disposed to think that you could tell him what truth is; nor even to understand the question.)
Instead of simply going for this negative conclusion, Gödel massaged truth, to represent it in formal logic so far as possible. Truth itself cannot be represented, but provability-according-to-the-rules-of-formal-logic can. What is a proof in formal logic? It is a sequence of well-formed formulae, starting with axioms, ending with the well-formed formula to be proved, with each successive step being a well-formed formula that follows from its predecessor according to some explicit rule of inference. So what Gödel needed to do was to code not just well-formed formulae---strings of symbols---but strings of well-formed formulae---strings of strings of symbols. But this can be done in essentially the same way as before, using this time not just the odd prime numbers, but 2 as well. Then a sequence of well-formed formulae can be expressed by an even number, and a putative proof of well-formed formula no.1729 would look something like
To give a proper definition of a formal proof, Gödel needed to specify the axioms, and to formulate precisely the requirement that each well-formed formula was either an axiom of followed from earlier members of the sequence in virtue of one of the rules of inference. And having done this in meta-logical terms, he needed to show that granted his coding system, these requirements could be represented as arithmetically definable properties of numbers. It was a mammoth task, and took pages and pages of detailed working. But he managed it, and was able to define a relation between numbers which obtained just in case the first (even) number was the Gdel number of a proof-sequence which was in fact a valid proof of the well-formed formula whose Gödel number was the second number in the relation. That is to say, there is a very complicated relation between numbers, Pr(x,y), which can be defined in terms of addition and multiplication, and holds when y is the Gödel number of a particular well-formed formula, and x is the Gödel number of a sequence of well-formed formulae which constitutes a proof of y. And then, generalising, he could have a general provability predicate which used the existential quantifier, and said just that there was a number which was the Gödel number of a sequence that was a proof of the well-formed formula whose Gödel number was the second number. So the well-formed formula, (Ex)Pr(x,1729) holds when there is a proof of the well-formed formula whose Gödel number is 1729, and conversely --(Ex)Pr(x,1729), holds when there is no proof of the well-formed formula whose Gödel number is 1729.
These two manoeuvres enable Gödel to refer to well-formed formulae by numbers, and to represent provability as a property of numbers definable in terms of the simple arithmetical operations of addition and multiplication, though the definitions are themselves very complicated. It remains to achieve self-reference, to find some Gödel number, 1729 as we have supposed for the sake of brevity, where wff no. 1729 turns out to be the wff --(Ex)Pr(x,1729) How can Gödel achieve this? He does it by means of a ``diagonalization operation'', like those used by Cantor to prove the non-denumerability of the continuum.
Cantor argues by Reductio Ad Absurdum. Suppose we could arrange all the real numbers between 0 and 1 in a denumerable list. The list would then look like
Cantor then shows that there is a real number between 0 and 1 that has been left out, contrary to hypothesis.
Let bmm be 1 if amm is 0, and 0 otherwise.
Consider the number
Gödel used a similar technique to devise a well-formed formula which used a negative existential quantifier to say that a certain (very large) number did not have a carefully constructed arithmetical property, where the very large number turned out to be the Gödel number of the well-formed formula itself, and the carefully constructed arithmetical property was the one possessed by the Gödel numbers of wffs that were unprovable in the given system. The essential move is to take a two-place predicate, F(m,n), and then consider the case where m=n, thus converting the two-place predicate into a somewhat peculiar one-place one.
Let me wave my hand over the enormous amount of careful working needed to achieve this in a water-tight fashion, and claim that we have achieved self-reference.
There are now useful expositions in
Roger Penrose, The Emperor's New Mind, Oxford, 1989; Shadows of the Mind, Oxford, 1994
which put forward the Gödelian argument against mechanism fully and carefully. See for the other Implications of Gödel's Theorem