Gödel's theorem

For more information on Gödel's theorem, visit Britannica.com.

The result, proved by K. Gödel in 1931, that any sufficiently advanced mathematical system must be incomplete in that there must always be a true sentence that is not provablein the system. Roughly speaking, Gödel showed how, for each such system, a sentence could be constructed that asserted its own nonprovability in the system.

Gödel considered mathematical systems that involve numbers, sets of numbers, and other purely mathematical entities. He demonstrated a still more remarkable result for these same systems, which include the most comprehensive mathematical systems known. He showed that if these systems are consistent, they cannot prove their own consistency. This is known as Gödel's, second incompleteness theorem.

Unfortunately, there are widespread misconceptions about this result. For example, Gödel's, second theorem is sometimes thought to imply the impossibility of knowing that these systems are consistent. In reality, the fact that a system cannot prove its own consistency does not constitute the slightest grounds for doubting its consistency. Indeed, if a system could in fact prove its own consistency, that of course would not be any guarantee that the system was consistent, since an inconsistent system can prove anything. The consistency of the systems considered by Gödel is known rather by the self-evident nature of the axioms and the obvious correctness of the rules of reasoning. Still, it is of interest that the systems, though obviously consistent, cannot prove their own consistency.

In the eighteenth century, G. Leibniz envisioned a universal calculating machine that could solve all mathematical problems. The impossibility of such a device has been conclusively demonstrated by further ramifications of Gödel's, work developed by A. Church and A. Turing. This work shows that mathematics cannot be mechanized, and that creativity and ingenuity will always be required. This is perhaps the most important consequence of Gödel's, work. Another way of stating this consequence is that human beings can never eliminate the necessity of using their own intelligence, regardless of how cleverly they try. See also Logic; Recursive function.

Gödel's first incompleteness theorem states that for any consistent logical system S able to express arithmetic there must exist sentences that are true in the standard interpretation of S, but not provable. Moreover, if S is omega-consistent then there exist sentences such that neither they nor their negations are provable. The second theorem states that no such system can be powerful enough to prove its own consistency.

These results, published in 1931 (‘Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I’; trs. as ‘On Formally Undecidable Propositions of Principia Mathematica and Related Systems I’), determined the limits of purely formal methods in mathematics, and in particular marked the end of Hilbert's programme. Additional philosophical significance attaches to the way Gödel proved his first result. This was by defining a formula P that whilst unprovable can be seen to be true, given the way it is constructed. The implied moral is that truth in some way outruns provability, at least when that is considered formally.

Gödel proceeded by encoding logical formulae as numbers, so that to a statement about provability in the metatheory there corresponded by the mapping a simple statement of elementary mathematics. The formalism of arithmetic thus contains sentences that, considered via the enumeration, express propositions of their own metamathematics. The formula P is such a one: it expresses, to one interpreting it via the enumeration, its own unprovability. Gödel's procedure thus is an instance of a diagonal argument, and it bears a vivid analogy to examples of the semantic paradoxes. It is thus extremely important that all the methods he used are perfectly rigorous.

Gödel's procedure and his results opened the way to a fully rigorous treatment of the notion of a computable function, and to our modern understanding of the power and limits of computation, and the possibility or otherwise of programs that test for consistency and completeness.