Gödel's incompleteness theorems

From Wikipedia, the free encyclopedia

In mathematical logic, Gödel's incompleteness theorems, proved by Kurt Gödel in 1931, are two theorems stating inherent limitations of all but the most trivial formal systems for arithmetic of mathematical interest.

The theorems are also of considerable importance to the philosophy of mathematics. They are widely regarded as showing that Hilbert's program to find a complete and consistent set of axioms for all of mathematics is impossible, thus giving a negative answer to Hilbert's second problem. Authors such as J. R. Lucas have argued that the theorems have implications in wider areas of philosophy and even cognitive science, but these claims are less generally accepted.

Contents 1 First incompleteness theorem 1.1 Extensions of Gödel's original result 2 Second incompleteness theorem 3 Meaning of Gödel's theorems 4 Examples of undecidable statements 5 Limitations of Gödel's theorems 6 Discussion and implications 6.1 Minds and machines 7 Proof sketch for the first theorem 8 Proof sketch for the second theorem 9 See also 10 Footnotes 11 References 11.1 Articles by Gödel 11.2 Articles by others 11.3 Books about the theorems 12 External links

[edit] First incompleteness theorem

Gödel's first incompleteness theorem, perhaps the single most celebrated result in mathematical logic, states that:

For any consistent formal theory that proves basic arithmetical truths, an arithmetical statement that is true¹ but not provable in the theory can be constructed. That is, any theory capable of expressing elementary arithmetic cannot be both consistent and complete.

Here, "theory" refers to an infinite set of statements, some of which are taken as true without proof (these are called axioms), and others (the theorems) that are taken as true because they are implied by the axioms. "Provable in the theory" means "derivable from the axioms and primitive notions of the theory, using standard first-order logic". A theory is "consistent" if it never proves a contradiction. "Can be constructed" means that some mechanical procedure exists which can construct the statement, given the axioms, primitives, and first order logic. The resulting true but unprovable statement is often referred to as "the Gödel sentence" for that theory. In fact, there are infinitely many statements in the theory that share with the Gödel sentence the property of being true but not provable from the theory. "Elementary arithmetic" consists merely of addition and multiplication over the natural numbers.

Some technical hypotheses have been omitted here; the most important is the stipulation that the theory be computably enumerable. That is, for Gödel's theorem to be applicable, it must be possible in principle to write a computer program that correctly decides whether statements are axioms of the theory, and a second computer program that, if allowed to run forever, would output (one at a time) a list containing all the theorems of the theory and no other statements.

The first incompleteness theorem first appeared as Proposition VI in his 1931 paper On Formally Undecidable Propositions in Principia Mathematica and Related Systems I. In Gödel's original notation, it states:

To every ω-consistent recursive class κ of formulas 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, asserts: "G cannot be proven true". If G were able to be proven true under the theory's axioms, then the theory would have a theorem, G, which contradicts itself, and thus the theory would be inconsistent. But if G were not provable, then it would be true (for G expresses this very fact) and thus the theory would be incomplete.

The argument just given is in ordinary English and thus not mathematically rigorous. In order to provide a rigorous proof, Gödel represented 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 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.

[edit] Extensions of Gödel's original result

Gödel demonstrated the incompleteness of the theory of Principia Mathematica, a particular theory of arithmetic, but a parallel demonstration could be given for any effective theory of a certain expressiveness. Gödel commented on this fact in the introduction to his paper, but restricted the proof to one system for concreteness. In modern statements of the theorem, it is common to state the effectiveness and expressiveness conditions as hypotheses for the incompleteness theorem, so that it is not limited to any particular formal theory.

Gödel's original statement and proof of the incompleteness theorem requires the assumption that the theory is not just consistent but ω-consistent. A theory is ω-consistent if it is not ω-inconsistent, and is ω-inconsistent if there is a predicate P such that for every specific natural number n the theory proves ~P(n), and yet the theory also proves that there exists a natural number n such that P(n). That is, the theory says that a number with property P exists while denying that it has any specific value. The ω-consistency of a theory implies its consistency, but consistency does not imply ω-consistency. J. Barkley Rosser later strengthened the incompleteness theorem by finding a variation of the proof that does not require the theory to be ω-consistent. This is mostly of technical interest, since all true formal theories of arithmetic, that is, theories with only axioms that are true statements about natural numbers, are ω-consistent and thus Gödel's theorem as originally stated applies to them. The stronger version of the incompleteness theorem that only assumes consistency, not ω-consistency, is now commonly known as Gödel's incompleteness theorem.

[edit] 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 is 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 consistent 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₁ satisfying the technical conditions outlined above can't prove the consistency of any theory T₂ which proves the consistency of T₁. This is because then T₁ can prove that if T₂ proves the consistency of T₁, then T₁ is in fact consistent. For the claim that T₁ 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₁". If T₁ were in fact inconsistent, then T₂ would prove for some n that n is the code of a contradiction in T₁. But if T₂ also proved that T₁ is consistent, i.e. there is no such n, it would itself be inconsistent. We can carry out this reasoning in T₁ and conclude that if T₂ is consistent, then T₁ is consistent. Since by second incompleteness theorem, T₁ does not prove its consistency, it can't prove the consistency of T₂ 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.

The consistency of first-order arithmetic has been proved assuming that a certain ordinal called ε₀ is wellfounded. See Gentzen's consistency proof.

[edit] 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 infinitely many 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. Or one might say, no formal system which aims to define the natural numbers can actually do so, as there will be true number-theoretical statements which that system cannot prove. Some argue this refutes the logicism of Gottlob Frege and Bertrand Russell, which aims to reduce/define the natural numbers to/in terms of logic.

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 finite list of axioms, or even an infinite list that can be produced by a computer program. Each time you add a statement as an axiom, there will always be other true statements that still cannot be proved as true, even with the new axiom. Furthermore if the system can prove that it is consistent, then it is inconsistent.

It is possible to have a complete and consistent list of axioms that cannot be produced by a computer program (that is, the list is not computably enumerable). For example, one might take all true statements about the natural numbers to be axioms (and no false statements). But then there is no mechanical way to decide, given a statement about the natural numbers, whether it is an axiom or not.

Gödel's theorem has another interpretation in the language of computer science. In first-order logic, theorems are computably 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 Principia 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.

[edit] Examples of undecidable statements

There are two distinct senses of the word "undecidable" in contemporary use. The first of these is the sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system. The second sense is used in relation to computability theory and applies not to statements but to decision problems, which are countably infinite sets of questions each requiring a yes or no answer. Such a problem is said to be undecidable if there is no computable 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, effective 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".

Because of the two meanings of the word undecidable, the term "independent" is sometimes used instead of undecidable for the "neither provable nor refutable" sense. The usage of "independent" is also ambiguous, however. Some use it to mean just "not provable", leaving open whether an independent statement might be refuted.

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 determined by other means. Undecidability only implies that the particular deductive system being considered does not prove the truth or falsity of the statement. 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.

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.

The combined work of Gödel and Paul Cohen has given two concrete examples of undecidable statements (in the first sense of the term): 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. Gödel proved in 1940 that neither of these statements could be disproved in ZF or ZFC set theory. In the 1960s, Cohen proved that neither is provable from ZF, and the continuum hypothesis cannot be proven from ZFC.

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 generalized to Rice's theorem.

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, Paris and Harrington proved that the Paris-Harrington principle, 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 second-order arithmetic.

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 statement about the Ramsey theory of the natural numbers that Kirby and Paris showed is undecidable in Peano arithmetic.

Gregory Chaitin produced undecidable statements in algorithmic information theory and proved another incompleteness theorem in that setting. Chaitin's theorem states that for any theory that can represent enough arithmetic, there is an upper bound c such that no specific number can be proven in that theory to have Kolmogorov complexity greater than c. While Godel's theorem is related to the liar paradox, Chaitin's result is related to Berry's paradox.

[edit] Limitations of Gödel's theorems

The conclusions of Gödel's theorems only hold for the formal systems that satisfy the necessary hypotheses (which have not been fully described in this article). Not all axiom systems satisfy these hypotheses, even when these systems have models that include the natural numbers as a subset. For example, there are first-order axiomatizations of Euclidean geometry and real closed fields that do not meet the hypotheses of Gödel's theorems. The key fact is that these axiomatizations are not expressive enough to define the set of natural numbers or develop basic properties of the natural numbers.^[1]

A second limitation is that Gödel's theorems only apply to systems that are used as their own proof systems. For example, the consistency of the Peano arithmetic can be proved in set theory if set theory is consistent (However, one cannot prove that the latter is consistent in that framework). In 1936, Gerhard Gentzen proved the consistency of Peano arithmetic using a formal system which was more powerful in certain aspects than arithmetic, but less powerful than standard set theory.

[edit] 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, "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 use 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.

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, obtained in 1936, showed 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 such a system of typed metalanguages, along 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 computably 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 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. If the axiomatic system is ω-consistent, then the negation of p cannot be proven either, and so p is undecidable. In a system which is not ω-consistent (but consistent), either we have the same situation, or we have a false statement which can be proven (namely, the negation of p).

Adding p to the axioms of the system would not solve the problem: there would be another Gödel sentence for the enlarged theory. Theories such as Peano arithmetic, for which any computably enumerable consistent extension is incomplete, are called essentially incomplete.

[edit] Minds and machines

Main article: Mechanism (philosophy)#Gödelian arguments

Authors including J. R. Lucas have debated what, if anything, Gödel's incompleteness theorems imply 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.

Hilary Putnam (1960) suggested that while Gödel's theorems cannot be applied to humans, since they make mistakes and are therefore inconsistent, it may be applied to the human faculty of science or mathematics in general. If we are to believe that it is consistent, then either we cannot prove its consistency, or it cannot be represented by a Turing machine.

[edit] Proof sketch for the first theorem

Main article: Proof sketch for Gödel's first incompleteness 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. It is similar to the way ASCII code is defined. 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 or class-sign. 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. For certain formulas one can show that for every natural number n, F(n) is true if and only if it can be proven (the precise requirement in the original proof is weaker, but for the proof sketch this will suffice). In particular, this is true for every specific arithmetic operation between a finite number of natural numbers, such as "2*3=6".

Statement forms themselves are not statements and therefore cannot be proved or disproved. But every statement form F(x) can be assigned with 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).

Now comes the trick: The notion of provability itself can also be encoded by Gödel numbers, in the following way. Since a proof is a list of statements which obey certain rules, we can define the Gödel number of a proof. Now, for every statement S, we may ask whether a number x is the Gödel number of its proof. The relation between the Gödel number of S and x, the Gödel number of its proof, is an arithmetical relation between two numbers.

A statement form F is called self-unprovable if F(G(F)) (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: if z = G(F) for some particular form F(x), then for every number x, x is not the Gödel number of the proof of F(G(F)).

An important feature of the SU is that it can be (roughly) defined in such a way, that in a consistent system, for every specific natural number z, SU(z) is provable if and only if it is true (this is because having one number x the Gödel number of the proof of the statement S, where y = G(S)), is a straightforward arithmetic relation between x and y, and can be simply "checked"). This claim is not accurate but will be good enough for this proof sketch.

Now the desired statement p that was mentioned above can be defined as:

p = SU(G(SU)).

This is equivalent to the statement, that SU(G(SU)) cannot be proven, i.e. p cannot be proven.

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 omega-consistent.

If p were provable, then it would be true. But p is equivalent to the statement that 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 we can prove that there exists a Gödel number of the proof of SU(G(SU)). However for every specific number x, x cannot be the Gödel number of the proof of SU(G(SU)) since p = SU(G(SU)) is not provable, as we have already shown. Thus on one hand we can prove that there is a number with a certain property (it is the Gödel number of the proof of p), but on the other hand for every specific number, we can prove that it does not have this property. This is impossible in an omega-consistent system. Thus the negation of p is not provable.

So the statement p is undecidable, i.e. it can neither be proved nor disproved within our system. ∎

It should be noted that p is not provable (and thus true) in every consistent system. omega-consistency is only required for the negation of p to be not provable. Thus:

• In an omega-consistent formal system we may prove neither p nor its negation, and so p is undecidable.
• In a consistent formal system we may either have the same situation, or we may prove the negation of p; In the later case, we have a statement ("not p") which is false but provable.

Note that if one tries to "add the missing axioms" in order to avoid the undecidability of the system, then one has to add either p or "not p" as axioms. But then the definition of "being a Gödel number of a proof" of a statement changes. Thus we may build a new statement form SU, different from the previous one, and the new SU(G(SU)) will be undecidable if the new system is omega-consistent.

[edit] 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. ∎

[edit] See also

• Consistency proof
• Diagonal lemma
• Self-reference
• Self-verifying theories
• Logicism
• Minds, Machines and Gödel
• Löb's Theorem
• Gödel, Escher, Bach: an Eternal Golden Braid
• set of all sets
• theory of everything
• Tarski's indefinability theorem

[edit] Footnotes