Gödel's incompleteness theorem
In mathematical logic, Gödel's incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931.
Contents
- 1 First incompleteness theorem
- 2 Second incompleteness theorem
- 3 Gentzen's theorem
- 4 Meaning of Gödel's theorems
- 5 Examples of undecidable statements
- 6 Misconceptions about Gödel's theorems
- 7 Discussion and implications
- 8 Minds and machines
- 9 Proof sketch for the first theorem
- 10 Proof sketch for the second theorem
- 11 See also
- 12 Footnotes
- 13 References
- 14 External links
First incompleteness theorem
Gödel's first incompleteness theorem is perhaps the most celebrated result in mathematical logic. It basically says that:
- For any consistent formal theory including basic arithmetical truths, it is possible to construct an arithmetical statement that is true ^{1} but not included in the theory. That is, any consistent theory of a certain expressive strength is incomplete.
Here, "theory" has the special sense of a set of statements closed under logical inference rules. (A theory is in general an infinitely large set.) A theory is "consistent" if it contains no contradictions. The meaning of "it is possible to construct" is that there is some mechanical procedure which when given the axioms of the theory, produces another statement. That this statement is not included in the theory means that it cannot be derived from statements of the theory using the standard rules of first-order logic. The statement produced by the procedure is often referred to as "the Gödel sentence" for that theory, though there are actually infinitely many statements that have the same property (of being true but not provable from the theory).
Gödel's Theorem
Gödel's Theorem appears as Proposition VI in his 1931 paper "On Formally Undecidable Propositions in Principa Mathematica and Related Systems I." It states:
- To every ω-consistent recursive class κ of formulae there correspond recursive class signs r, such that neither v Gen r nor Neg(v Gen r) belongs to Flg(κ) (where v is the free variable of r).
Roughly speaking, the Gödel statement, G, can be expressed: 'G is not provable'. If one were to suppose that G were provable (from the theory) then the theory would have a theorem, G, saying the opposite of what was just supposed. So we are forced to conclude that G is not provable; yet it is true. Q.E.D.
The demonstration just given is in ordinary English and thus not mathematically rigorous. In order to provide a well-defined demonstration, Gödel represents statements by numbers; then the theory, which is already about numbers, also pertains to statements, including its own. Questions about the provability of statements are represented as mathematically definable questions about the properties of numbers, which would be decidable by the theory if it were complete. In these terms, the Gödel sentence is a claim that there does not exist a natural number with a certain property. A number with that property would be a proof of inconsistency of the theory. If there were such a number then the theory would be inconsistent, contrary to hypothesis. So there is no such number, and the Gödel statement is true, but the theory cannot prove it.
Gödel demonstrated the incompleteness of a theory of arithmetic, but it is clear that the demonstration could be given for any theory and language of a certain expressiveness.
Gödel originally proved a weaker theorem than the one stated above. In the theorem proved by Gödel the assumption is that the theory is (not just consistent but) omega-consistent. Omega-consistency is a technical concept which applies to a theory T if, for no property P, T proves that every specific natural number lacks P, yet T proves that there exists some natural number with P. Note that omega-consistency implies consistency, but consistency does not imply omega-consistency. J. Barkley Rosser later strengthened the theorem by removing the requirement for the theory to be omega-consistent. This is mostly of technical interest, since all true formal theories of arithmetic, i.e. theories the axioms of which are true statements about natural numbers, are omega-consistent and thus Gödel's original theorem applies to them.
Second incompleteness theorem
Gödel's second incompleteness theorem can be stated as follows:
- For any formal theory T including basic arithmetical truths and also certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent.
(Proof of the "if" part:) If T is inconsistent then anything can be proved, including that T is consistent. (Proof of the "only if" part:) If T is consistent then T does not include the statement of its own consistency. This follows from the first theorem.
There is a technical subtlety involved in the second incompleteness theorem, namely how exactly are we to express the consistency of T in the language of T. There are many ways to do this, and not all of them lead to the same result. In particular, different formalizations of the claim that T is consistent may be inequivalent in T, and some may even be provable. For example, first order arithmetic (Peano arithmetic or PA for short) can prove that the largest consistent subset of PA is consistent. But since PA is consistent, the largest consistent subset of PA is just PA, so in this sense PA "proves that it's consistent". What PA does not prove is that the largest consistent subset of PA is, in fact, the whole of PA. (The term "largest consistent subset of PA" is rather vague, but what is meant here is the largest initial segment of the axioms of PA ordered according to some criteria, e.g. by "Gödel numbers", the numbers encoding the axioms as per the scheme used by Gödel mentioned above).
In case of Peano arithmetic or any familiar explicitly axiomatized theory T, it is possible to define the consistency "Con(T)" of T in terms of the non-existence of a number with a certain property, as follows: "there does not exist an integer coding a sequence of sentences, such that each sentence is either one of the (canonical) axioms of T, a logical axiom, or an immediate consequence of preceding sentences according to the rules of inference of first order logic, and such that the last sentence is a contradiction". However, for arbitrary T there is no canonical choice for Con(T).
The formalization of Con(T) depends on two factors: formalizing the notion of a sentence being derivable from a set of sentences and formalizing the notion of being an axiom of T. Formalizing derivability can be done in canonical fashion, so given an arithmetical formula A(x) defining a set of axioms we can canonically form the predicate Prov_{A}(P) which expresses that P is provable from the set of axioms defined by A(x). Using this predicate we can express Con(T) as "not Prov_{A}('P and not-P')". Solomon Feferman showed that Gödel's second incompleteness theorem goes through when the formula A(x) is chosen so that it has the form "there exists a number n satisfying the decidable predicate P" for some P. In addition, Prov_{A}(P) must satisfy the so-called Hilbert-Bernays provability conditions:
1. If T proves P, then T proves Prov_{A}(P)
2. T proves 1., i.e. T proves that if T proves P, then T proves Prov_{A}(P)
3. T proves that if T proves that (P implies Q) then T proves that provability of P implies provability of Q
Gödel's second incompleteness theorem also implies that a theory T_{1} satisfying the technical conditions outlined above can't prove the consistency of any theory T_{2} which proves the consistency of T_{1}. This is because then T_{1} can prove that if T_{2} proves the consistency of T_{1}, then T_{1} is in fact consistent. For the claim that T_{1} is consistent has form "for all numbers n, n has the decidable property of not being a code for a proof of contradiction in T_{1}". If T_{1} were in fact inconsistent, then T_{2} would prove for some n that n is the code of a contradiction in T_{1}. But if T_{2} also proved that T_{1} is consistent, i.e. there is no such n, it would itself be inconsistent. We can carry out this reasoning in T_{1} and conclude that if T_{2} is consistent, then T_{1} is consistent. Since by second incompleteness theorem, T_{1} does not prove its consistency, it can't prove the consistency of T_{2} either.
This easy corollary of the second incompleteness theorem shows that there is no hope of proving e.g. the consistency of first order arithmetic using finitistic means provided we accept that finitistic means are correctly formalized in a theory the consistency of which is provable in PA. It's generally accepted that the theory of primitive recursive arithmetic (PRA) is an accurate formalization of finitistic mathematics, and PRA is provably consistent in PA. Thus PRA can't prove the consistency of PA. This is generally seen to show that Hilbert's program of validating the use of "ideal" mathematical principles to prove "real" (finitistic) mathematical statements by showing that the "ideal" principles are consistent by finitistically acceptable principles can't be carried out.
This corollary is actually what makes the second incompleteness theorem epistemologically relevant. As Georg Kreisel remarked, it would actually provide no interesting information if a theory T proved its consistency. This is because inconsistent theories prove everything, including their consistency. Thus a consistency proof of T in T would give us no clue as to whether T really is consistent; no doubts about T's consistency would be resolved by such a consistency proof. The interest in consistency proofs lies in the possibility of proving the consistency of a theory T in some theory T' which is in some sense less doubtful than T itself, e.g. weaker than T. For most naturally occurring T and T', such as T = Zermelo-Fraenkel set theory and T' = primitive recursive arithmetic, the consistency of T' is provable in T, and thus T' can't prove the consistency of T by the above corollary of the second incompleteness theorem.
Gentzen's theorem
In 1936 Gerhard Gentzen proved the consistency of first order arithmetic. In itself, the result is rather trivial, since the consistency of first order arithmetic has a very easy proof: the axioms are true—in a mathematically defined sense—the rules of predicate calculus preserve truth and no contradiction is true, hence no contradiction follows from the axioms of first order arithmetic. What makes Gentzen's proof interesting is that it shows much more than merely that first order arithmetic is consistent. Gentzen showed that the consistency of first order arithmetic is provable, over the very weak base theory of primitive recursive arithmetic mentioned earlier, using the principle of quantifier free transfinite induction up to the ordinal ε_{0}.
The principle of quantifier free transfinite induction up to epsilon-0 says that for any formula A(x) with no bound variables transfinite induction up to ε_{0} holds. ε_{0} is the first ordinal , such that , i.e. the limit of the sequence:
To express ordinals in the language of arithmetic a notation is needed, i.e. a way to assign natural numbers to ordinals less than ε_{0}. This can be done in various ways, one example provided by Cantor's normal form theorem. That transfinite induction holds for a formula A(x) means that A does not define an infinite descending sequence of ordinals smaller than ε_{0} (in which case ε_{0} would not be well-ordered). Gentzen assigned ordinals smaller than ε_{0} to proofs in first order arithmetic and showed that if there is a proof of contradiction, then there is an infinite descending sequence of ordinals < ε_{0} produced by a primitive recursive operation on proofs corresponding to a quantifier free formula.
Gentzen's proof also highlights one commonly missed aspect of Gödel's second incompleteness theorem. It's sometimes claimed that the consistency of a theory can only be proved in a stronger theory. The theory obtained by adding quantifier free transfinite induction to primitive recursive arithmetic proves the consistency of first order arithmetic but is not stronger than first order arithmetic. For example, it doesn't prove ordinary mathematical induction for all formulae, while first order arithmetic does (it has this as an axiom schema). The resulting theory is not weaker than first order arithmetic either, since it can prove a number theoretical fact - the consistency of first order arithmetic - that first order arithmetic can't. The two theories are simply incomparable.
Gentzen's proof is the first example of what is called proof theoretical ordinal analysis. In ordinal analysis one gauges the strength of theories by measuring how large (constructive) ordinals they can prove to be well-ordered, or equivalently for how large (constructive) ordinals is transfinite induction provable. A constructive ordinal is the order type of a recursive well-ordering of natural numbers.
Meaning of Gödel's theorems
Gödel's theorems are theorems in first-order logic, and must ultimately be understood in that context. In formal logic, both mathematical statements and proofs are written in a symbolic language, one where we can mechanically check the validity of proofs so that there can be no doubt that a theorem follows from our starting list of axioms. In theory, such a proof can be checked by a computer, and in fact there are computer programs that will check the validity of proofs. (Automatic proof verification is closely related to automated theorem proving, though proving and checking the proof are usually different tasks.)
To be able to perform this process, we need to know what our axioms are. We could start with a finite set of axioms, such as in Euclidean geometry, or more generally we could allow an infinite list of axioms, with the requirement that we can mechanically check for any given statement if it is an axiom from that set or not (an axiom schema). In computer science, this is known as having a recursive set of axioms. While an infinite list of axioms may sound strange, this is exactly what's used in the usual axioms for the natural numbers, the Peano axioms: the inductive axiom is in fact an axiom schema - it states that if zero has any property and whenever any natural number has that property, its successor also has that property, then all natural numbers have that property - it does not specify which property and the only way to say in first-order logic that this is true of all properties is to have an infinite number of statements.
Gödel's first incompleteness theorem shows that any such system that allows you to define the natural numbers is necessarily incomplete: it contains statements that are neither provably true nor provably false.
The existence of an incomplete system is in itself not particularly surprising. For example, if you take Euclidean geometry and you drop the parallel postulate, you get an incomplete system (in the sense that the system does not contain all the true statements about Euclidean space). A system can be incomplete simply because you haven't discovered all the necessary axioms.
What Gödel showed is that in most cases, such as in number theory or real analysis, you can never create a complete and consistent list of axioms. Each time you add a statement as an axiom, there will always be another true statement(s) which cannot be proved as true. This exists for any system with zero, any finite, or indeed, any infinite number of axioms on which the system is based. Furthermore if the system can prove itself as complete then it is inconsistent.
You can add an infinite number of axioms; for example, you can add all true statements about the natural numbers to your list of axioms, but such a list will not be a recursive set. Given a random statement, there will be no way to know if it is an axiom of your system. If I give you a proof, in general there will be no way for you to check if that proof is valid.
Gödel's theorem has another interpretation in the language of computer science. In first-order logic, theorems are recursively enumerable: you can write a computer program that will eventually generate any valid proof. You can ask if they have the stronger property of being recursive: can you write a computer program to definitively determine if a statement is true or false? Gödel's theorem says that in general you cannot.
Many logicians believe that Gödel's incompleteness theorems struck a fatal blow to David Hilbert's program towards a universal mathematical formalism which was based on Principa Mathematica. The generally agreed upon stance is that the second theorem is what specifically dealt this blow. However some believe it was the first, and others believe that neither did.
Examples of undecidable statements
It should be noted that there are two distinct senses of the word "undecidable" in use. The first of these is the sense used in relation to Gödel's theorems, i.e., that of a statement being neither provable nor refutable, in some specified deductive system. The second sense is used in relation to recursion theory and applies not to statements but to decision problems, which are countably infinite sets of questions each requiring a yes/no answer. Such a problem is said to be undecidable if there is no recursive function that correctly answers every question in the problem set. The connection between these two is that if a decision problem is undecidable (in the recursion theoretical sense) then there is no consistent formal system which proves for every question A in the problem either "the answer to A is yes" or "the answer to A is no".
(For this reason, the term "independent" is often preferred to "undecidable", for the "neither provable nor refutable" sense. However "independent" is also ambiguous; some use it to mean just "not provable", and leave open whether an independent statement might be refuted.)
It should be noted that undecidability of a statement, in a particular deductive system, does not in and of itself address the question of whether the truth value of the statement is well-defined, or whether it can be known. It says only that the particular deductive system being considered does not decide the issue. Whether there exist so-called "absolutely undecidable" statements, whose truth value can never be known or is ill-specified, is a controversial point among various philosophical schools.
The subsequent combined work of Gödel and Paul Cohen has given concrete examples of undecidable statements (statements that, in some specified deductive system, can be neither proved nor disproved): The continuum hypothesis can neither be proved nor refuted in ZFC (the standard axiomatization of set theory), and the axiom of choice can neither be proved nor refuted in ZF (which is all the ZFC axioms except the axiom of choice). These results do not require the incompleteness theorem.
In 1936, Alan Turing proved that the halting problem—the question of whether or not a Turing machine halts on a given program—is undecidable, in the second sense of the term. This result was later generalised in the field of recursive functions to Rice's theorem which shows that all non-trivial properties of recursive functions are undecidable, i.e. there is no recursive function which returns 1 when given a description of a recursive function having the property and returns 0 otherwise. In this context a non-trivial property is one which is true for some, but not all, recursive functions.
In 1973, the Whitehead problem in group theory was shown to be undecidable, in the first sense of the term, in standard set theory. In 1977, Kirby, Paris and Harrington proved that a statement in combinatorics, a version of the Ramsey theorem, is undecidable in the axiomatization of arithmetic given by the Peano axioms but can be proven to be true in the larger system of set theory. Kruskal's tree theorem, which has applications in computer science, is also undecidable from the Peano axioms but provable in set theory. In fact Kruskal's tree theorem (or its finite form) is undecidable in a much stronger system codifying the principles acceptable on basis of a philosophy of mathematics called predicativism. Goodstein's theorem is a relatively simple statement about natural numbers that is undecidable in Peano arithmetic.
Gregory Chaitin produced undecidable statements in algorithmic information theory and in fact proved his own incompleteness theorem in that setting.
One of the first problems suspected to be undecidable, in the second sense of the term, was the word problem for groups, first posed by Max Dehn in 1911, which asks if there is a finitely presented group for which no algorithm exists to determine whether two words are equivalent. This was shown to be the case in 1952.
Misconceptions about Gödel's theorems
Since Gödel's first incompleteness theorem is so famous, it has given rise to many misconceptions. They are refuted here:
- The theorem does not imply that every interesting axiom system is incomplete. For example, Euclidean geometry can be axiomatized so that it is a complete system. (In fact, Euclid's original axioms are pretty close to being a complete axiomatization. The missing axioms express properties that seem so obvious that it took the emergence of the idea of a formal proof before their absence was noticed.)
- The theorem only applies to systems that allow you to define the natural numbers as a set. It is not sufficient that the system contain the natural numbers. You must also be able to express the concept " is a natural number" using your axioms and first-order logic. There are plenty of systems that contain the natural numbers and are complete. For example both the real numbers and complex numbers have complete axiomatizations.
- The theorem only applies to systems that are used as their own proof systems. Gentzen's work shows the consequences of using a proof theory that is not the same theory, but a more powerful one.
Discussion and implications
The incompleteness results affect the philosophy of mathematics, particularly viewpoints like formalism, which uses formal logic to define its principles. One can paraphrase the first theorem as saying that "we can never find an all-encompassing axiomatic system which is able to prove all mathematical truths, but no falsehoods."
On the other hand, from a strict formalist perspective this paraphrase would be considered meaningless because it presupposes that mathematical "truth" and "falsehood" are well-defined in an absolute sense, rather than relative to each formal system.
The following rephrasing of the second theorem is even more unsettling to the foundations of mathematics:
- If an axiomatic system can be proven to be consistent and complete from within itself, then it is inconsistent.
Therefore, in order to establish the consistency of a system S, one needs to utilize some other more powerful system T, but a proof in T is not completely convincing unless T's consistency has already been established without using S.
The consistency of the Peano axioms for natural numbers for example can be proven in set theory, but not in the theory of natural numbers alone. This provides a negative answer to problem number 2 on David Hilbert's famous list of important open questions in mathematics (called Hilbert's problems).
In principle, Gödel's theorems still leave some hope: it might be possible to produce a general algorithm that for a given statement determines whether it is undecidable or not, thus allowing mathematicians to bypass the undecidable statements altogether. However, the negative answer to the Entscheidungsproblem shows that no such algorithm exists.
There are some who hold that a statement that is unprovable within a deductive system may be quite provable in a metalanguage. And what cannot be proven in that metalanguage can likely be proven in a meta-metalanguage, recursively, ad infinitum, in principle. By invoking a sort of super Theory of Types with an axiom of Reducibility -- which by an inductive assumption applies to the entire stack of languages -- one may, for all practical purposes, overcome the obstacle of incompleteness.
Note that Gödel's theorems only apply to sufficiently strong axiomatic systems. "Sufficiently strong" means that the theory contains enough arithmetic to carry out the coding constructions needed for the proof of the first incompleteness theorem. Essentially, all that is required are some basic facts about addition and multiplication as formalized, e.g., in Robinson arithmetic Q. There are even weaker axiomatic systems that are consistent and complete, for instance Presburger arithmetic which proves every true first-order statement involving only addition.
The axiomatic system may consist of infinitely many axioms (as first-order Peano arithmetic does), but for Gödel's theorem to apply, there has to be an effective algorithm which is able to check proofs for correctness. For instance, one might take the set of all first-order sentences which are true in the standard model of the natural numbers. This system is complete; Gödel's theorem does not apply because there is no effective procedure that decides if a given sentence is an axiom. In fact, that this is so is a consequence of Gödel's first incompleteness theorem.
Another example of a specification of a theory to which Gödel's first theorem does not apply can be constructed as follows: order all possible statements about natural numbers first by length and then lexicographically, start with an axiomatic system initially equal to the Peano axioms, go through your list of statements one by one, and, if the current statement cannot be proven nor disproven from the current axiom system, add it to that system. This creates a system which is complete, consistent, and sufficiently powerful, but not recursively enumerable.
Gödel himself only proved a technically slightly weaker version of the above theorems; the first proof for the versions stated above was given by J. Barkley Rosser in 1936.
In essence, the proof of the first theorem consists of constructing a statement p within a formal axiomatic system that can be given a meta-mathematical interpretation of:
- p = "This statement cannot be proven in the given formal theory"
As such, it can be seen as a modern variant of the Liar paradox, although unlike the classical paradoxes it's not really paradoxical.
If the axiomatic system is (omega-)consistent, Gödel's proof shows that p (and its negation) cannot be proven in the system. Therefore p is true (p claims to be not provable, and it is not provable) yet it cannot be formally proved in the system. Note that adding p to the axioms of the system would not solve the problem: there would be another Gödel sentence for the enlarged theory.
Minds and machines
Many scholars have debated over what Gödel's incompleteness theorem implies about human intelligence. Much of the debate centers on whether the human mind is equivalent to a Turing machine, or by the Church-Turing thesis, any finite machine at all. If it is, and if the machine is consistent, then Gödel's incompleteness theorems would apply to it.
One of the earliest attempts to use incompleteness to reason about human intelligence was by Gödel himself in his 1951 Gibbs lecture entitled "Some basic theorems on the foundations of mathematics and their philosophical implications." In this lecture, Gödel uses the incompleteness theorem to arrive at the following disjunction: (a) the human mind is not a consistent finite machine, or (b) there exist Diophantine equations for which it cannot decide whether solutions exist. Gödel finds (b) implausible, and thus seems to have believed the human mind was not equivalent to a finite machine, i.e., its power exceeded that of any finite machine. However, he recognized that this was only a conjecture, since he could not disprove (b).
In subsequent years, more direct anti-mechanist lines of reasoning were apparently floating around the intellectual atmosphere. In 1960, Hilary Putnam published a paper entitled "Minds and Machines," in which he points out the flaws of a typical anti-mechanist argument. Informally, this is the argument that the (alleged) difference between "what can be mechanically proven" and "what can be seen to be true by humans" shows that human intelligence is not mechanical in nature. Or, as Putnam puts it:
Let T be a Turing machine which "represents" me in the sense that T can prove just the mathematical statements I prove. Then using Gödel's technique I can discover a proposition that T cannot prove, and moreover I can prove this proposition. This refutes the assumption that T "represents" me, hence I am not a Turing machine.
Putnam objects that this argument ignores the issue of consistency. Gödel's technique can only be applied to consistent systems. It is possible, argues Putnam, that the human mind is inconsistent. If one is to use Gödel's technique to prove that proposition that T cannot prove, one must first prove (the mathematical statement representing) the consistency of T, a daunting and perhaps impossible task. Thus, it is not necessary that one is able to prove something which T cannot.
J. R. Lucas in Minds, Machines and Gödel (1963), and later in his book The Freedom of the Will (1970), lays out an anti-mechanist argument closely following the one described by Putnam, including reasons for why the human mind can be considered consistent. Lucas admits that, by Gödel's second theorem, a human mind cannot formally prove its own consistency, and even says (perhaps facetiously) that women and politicians are inconsistent. Nevertheless, he sets out arguments for why a male non-politician can be considered consistent. These arguments are philosophical in nature and are the subject of much debate; Lucas provides references to responses on his own website.
Another notable work was done by Judson Webb in his 1968 paper "Metamathematics and the Philosophy of Mind." Webb claims that previous attempts have glossed over whether one truly can see that the Gödelian statement p pertaining to oneself, is true. Using a different formulation of Gödel's theorems, namely, that of Raymond Smullyan and Emil Post, Webb shows one can derive convincing arguments for oneself of both the truth and falsity of p. He furthermore argues that all arguments about the philosophical implications of Gödel's theorems are really arguments about whether the Church-Turing thesis is true.
Later, Roger Penrose entered the fray, providing somewhat novel anti-mechanist arguments in his books, The Emperor's New Mind (1989) [ENM] and Shadows of the Mind (1994) [SM]. These books have proved highly controversial. Martin Davis responded to ENM in his paper "Is Mathematical Insight Algorithmic?" (ps), where he argues that Penrose ignores the issue of consistency. Solomon Feferman gives a critical examination of SM in his paper "Penrose's Gödelian argument" (pdf).
Proof sketch for the first theorem
The main problem in fleshing out the above mentioned proof idea is the following: in order to construct a statement p that is equivalent to "p cannot be proved", p would have to somehow contain a reference to p, which could easily give rise to an infinite regress. Gödel's ingenious trick, which was later used by Alan Turing to show that the Entscheidungsproblem is unsolvable, will be described below.
To begin with, every formula or statement that can be formulated in our system gets a unique number, called its Gödel number. This is done in such a way that it is easy to mechanically convert back and forth between formulas and Gödel numbers. Because our system is strong enough to reason about numbers, it is now also possible to reason about formulas.
A formula F(x) that contains exactly one free variable x is called a statement form. As soon as x is replaced by a specific number, the statement form turns into a bona fide statement, and it is then either provable in the system, or not. Statement forms themselves are not statements and therefore cannot be proved or disproved. But every statement form F(x) has a Gödel number which we will denote by G(F). The choice of the free variable used in the form F(x) is not relevant to the assignment of the Gödel number G(F).
By carefully analyzing the axioms and rules of the system, one can then write down a statement form P(x) which embodies the idea that x is the Gödel number of a statement which can be proved in our system. Formally: P(x) can be proved if x is the Gödel number of a provable statement, and its negation ~P(x) can be proved if it isn't. (While this is good enough for this proof sketch, it is technically not completely accurate. See Gödel's paper for the problem and Rosser's paper for the resolution. The key word is "omega-consistency".)
Now comes the trick: a statement form F(x) is called self-unprovable if the form F, applied to its own Gödel number, is not provable. This concept can be defined formally, and we can construct a statement form SU(z) whose interpretation is that z is the Gödel number of a self-unprovable statement form. Formally, SU(z) is defined as: z = G(F) for some particular form F(x), and y is the Gödel number of the statement F(G(F)), and ~F(y). Now the desired statement p that was mentioned above can be defined as:
- p = SU(G(SU)).
Intuitively, when asking whether p is true, we ask: "Is the property of being self-unprovable itself self-unprovable?" This is very reminiscent of the Barber paradox about the barber who shaves precisely those people who don't shave themselves: does he shave himself?
We will now assume that our axiomatic system is consistent.
If p were provable, then SU(G(SU)) would be true, and by definition of SU, z = G(SU) would be the Gödel number of a self-unprovable statement form. Hence SU would be self-unprovable, which by definition of self-unprovable means that SU(G(SU)) is not provable, but this was our p: p is not provable. This contradiction shows that p cannot be provable.
If the negation of p= SU(G(SU)) were provable, then by definition of SU this would mean that z = G(SU) is not the Gödel number of a self-unprovable form, which implies that SU is not self-unprovable. By definition of self-unprovable, we conclude that SU(G(SU)) is provable, hence p is provable. Again a contradiction. This one shows that the negation of p cannot be provable either.
So the statement p can neither be proved nor disproved within our system.
Proof sketch for the second theorem
Let p stand for the undecidable sentence constructed above, and let's assume that the consistency of the system can be proven from within the system itself. We have seen above that if the system is consistent, then p is not provable. The proof of this implication can be formalized in the system itself, and therefore the statement "p is not provable", or "not P(p)" can be proven in the system.
But this last statement is equivalent to p itself (and this equivalence can be proven in the system), so p can be proven in the system. This contradiction shows that the system must be inconsistent.
See also
- Consistency proof
- Self-reference
- Self-verifying theories
- Logicism
- Minds, Machines and Gödel
- Löb's Theorem
- Principia Mathematica
Footnotes
Template:Ent The word "true" here is being used disquotationally; that is, the statement "G_{T} is true" means the same thing as G_{T} itself. Thus a formalist might reinterpret the claim
- for every theory T satisfying the hypotheses, if T is consistent, then G_{T} is true
- to mean
- for every theory T satisfying the hypotheses, it is a theorem of Peano Arithmetic that Con(T)→G_{T}
- where Con(T) is the natural formalization of the claim "T is consistent", and G_{T} is the Gödel sentence for T.
References
Scientific articles
- K. Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik, 38 (received 17 Nov 1930, published 1931), pp. 173-198. Translated in van Heijenoort: From Frege to Gödel. Harvard University Press, 1971. pp. 596-616.
- K. Gödel: Some basic theorems on the foundations of mathematics and their implications (1951). Printed in Collected works / Kurt Gödel v.III; edited by Solomon Feferman. Clarendon Press ; New York : Oxford University Press, 1995. pp. 304-323.
- J.R. Lucas: Minds, Machines, and Gödel. Philosophy XXXVI (1961):112-127.
- Putnam, Hilary. Minds and Machines, Dimensions of Mind: A Symposium, edited by Sidney Hook. New York University Press: New York, 1960. Reprinted in Minds and Machines, edited by A.R. Anderson, Prentice-Hall: Englewood Cliffs, New Jersey, 1964. page 77.
- B. Rosser: Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic, 1 (1936), N1, pp. 87-91.
- van Heijenoort, Jean. Gödel's Theorem, in Paul Edwards (editor), Encyclopedia of Philosophy, vol. 3. New York : Macmillan, 1963. pp. 348-357.
- J. Webb. Metamathematics and the Philosophy of Mind. Philosophy of Science, Vol 35, Issue 2, (Jun 1968):156-178.
Books
- Hao Wang: A Logical Journey: From Gödel to Philosophy Bradford Books (January 10, 1997) ISBN 0262231891
- Kārlis Podnieks: Around Goedel's Theorem, http://www.ltn.lv/~podnieks/gt.html
- D. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid, 1979, ISBN 0465026850. (1999 reprint: ISBN 0465026567).
- Ernest Nagel, James Roy Newman, Douglas R. Hofstadter: Gödel's Proof, revised edition (2002). ISBN 0814758169.
- Hilbert's second problem (English translation)
- Norbert Domeisen, Logik der Antinomien. Bern etc.: Peter Lang. 142 S. 1990. (ISBN 3-261-04214-1), Zentralblatt MATH
- Torkel Franzén, Gödel's Theorem: An Incomplete Guide to its Use and Abuse, AK Peters (2005), ISBN 1568812388
- Rudy Rucker: Infinity and the Mind: The Science and Philosophy of the Infinite, (Princeton, 1995)
- Peter Smith, An Introduction to Gödel's Theorems, (Forthcoming)
External links
- Gödel's biography with photo
- Gentzen's biography with photo
- Godel's Theorem explained further
- Can the cosmos be modeled as a Turing machine? Private web site concludes that Godel's incompleteness theorem forbids this.