# Gödel's incompleteness theorem

In mathematical logic,

**Gödel's incompleteness theorems**are two celebrated theorems proved by Kurt Gödel in 1930. Somewhat simplified, the first theorem states:

*In any consistent formalization of mathematics that is sufficiently strong to define the concept of natural numbers, one can construct a statement that can be neither proved nor disproved within that system.*

*formal logic*, and as such is easy to misinterpret. There are many statements that sound similar to Gödel's first incompleteness theorem, but are in fact not true. These are discussed in Misconceptions about Gödel's theorems.

Gödel's second incompleteness theorem, which is proved by formalizing part of the proof of the first within the system itself, states:

*Any consistent system cannot be used to prove its own consistency.*

## 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, we write both mathematical statements and proofs 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 on computer, and in fact there are computer programs that will check the validity of proofs.

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 if each statement is an axiom or not. 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.

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. An incomplete system can mean simply that 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* discover the complete list of axioms. Each time you add a statement as an axiom, there will always be another statement out of reach.

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 satisfy 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. 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

The subsequent combined work of Gödel and Paul Cohen has given concrete examples of undecidable statements (statements which can be neither proven nor disproven): both the axiom of choice and the continuum hypothesis are undecidable in the standard axiomatization of set theory. 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. This result was later generalised in the field of recursive functions to Rice's theorem which shows that all non-trivial decision problems are undecidable in a system that is turing complete.

In 1973, the Whitehead problem in group theory was shown to be undecidable 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. 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 was the word problem for groups, first posed by Max Dehn in 1911, which states that there is a finitely presented group that has no algorithm to state whether two words are equivalent. It was not proven to be undecidable until 1952.

## Misconceptions about Gödel's theorems

- The theorem does not imply that every interesting axiom system is incomplete. For example, Euclidean geometry can be axiomized so that it is a complete system. (In fact, Euclid's original axioms are pretty close to being a complete axiomization. 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 "'x' 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 axiomizations.

## 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."

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 from within itself, then it is inconsistent.*

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.

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 which are consistent and complete, for instance Presburger arithmetic which proves every true first-order statement which only involves 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 Rosser in 1936.

In essence, the proof of the first theorem consists of constructing the statement

*p*= "This statement cannot be proven"

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 not to be provable, and it isn't) 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.

Roger Penrose claims that this (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. This claim is also addressed by JR Lucas in Minds, Machines and Gödel.

This view is not widely accepted, because as stated by Marvin Minsky, human intelligence is capable of error and of **understanding** statements which are in fact inconsistent or false. However, Marvin Minsky has reported that Kurt Gödel told him personally that he believed that human beings had an intuitive, not just computational, way of arriving at truth and that therefore his theorem did not limit what can be known to be true by humans.

The position that the theorem shows humans to have an ability that transcends formal logic can also be criticized as follows: We do not know whether the sentence *p* is true or not, because we do not (and can not) know whether the system is consistent.
So in fact we do not know any truth outside of the system.
All we know is the following statement:

- Either
*p*is unprovable within the system, or the system is inconsistent.

*within the system*. In fact, such a proof will now be given.

## 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 solve the Entscheidungsproblem, 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 then is 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 *~P*(*y*). Now the desired statement *p* that was mentioned above can be defined as:

*p*=*SU*(**G**(*SU*)).

*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

## See also

## External links and references

- K. Gödel:
*Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I.*Monatshefte für Mathematik und Physik, 38 (1931), pp. 173-198. Translated in van Heijenoort:*From Frege to Gödel*. Harvard University Press, 1971. - B. Rosser:
*Extensions of some theorems of Gödel and Church*. Journal of Symbolic Logic, 1 (1936), N1, pp. 87-91 - 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
- abelard:
*{http://www.abelard.org/metalogic/metalogicA1.htm The confusions of Gödel*, an analysis of the multiple problems and unsound foundations involved in Gödel’s theorems (in four parts).