Worlds of David Darling
Encyclopedia of Science
Home > Encyclopedia of Science

Gödel's incompleteness theorem

In a nutshell: All consistent axiomatic systems contain undecidable propositions. What does this mean? An axiomatic system consists of some undefined terms, a number of axioms referring to those terms and partially describing their properties, and a rule or rules for deriving new propositions from already existing propositions.

There are a couple of main reasons why axiomatic systems are so useful: first, they're compact descriptions of the whole field of propositions derivable from the axioms, so large bodies of math can be compressed down into a very small compass; second, because they're so abstract, these systems let us derive all, and only, the results that follow from things having the formal properties specified by the axioms. An axiomatic system is said to be consistent if, given the axioms and the derivation rules, it doesn't lead to any contradictory propositions. One of the first modern axiomatic systems was a formalization of simple arithmetic (adding and multiplying whole numbers), achieved the great logician Giuseppe Peano and now known as Peano arithmetic. What Kurt Gödel did was to show that every syntactically correct proposition in Peano arithmetic can be represented by a unique integer, called its Gödel number. (The trick is to replace each symbol in the proposition, including numerals, by a different string of digits. If we represent "1" by 01, "2" by 02, "+" by 10, and "=" by 11, then the Gödel number of "1 + 1 = 2" is 0110011102. Gödel numbers tend to be huge!) This lets us write down, unambiguously, propositions that are about propositions. In particular, we can write down self-referential propositions – ones that include their own Gödel number. From here, Gödel showed that, either the system is inconsistent, or there are true propositions that can't be reached from the axioms by applying the derivation rules. The system is thus incomplete, and the truth of those propositions is undecidable (within that system). Such undecidable propositions are known as Gödel propositions or Gödel sentences. Nobody knows what the Gödel sentences for Peano arithmetic are, though people have their suspicions about Goldbach's conjecture (every even number is the sum of two prime numbers).

So far we've just been talking about Peano arithmetic, but results about an axiomatic system apply to all kinds of things that satisfy the axioms. There are an immense number of other axiomatic systems, which either include Peano numbers among their basic entities or can be constructed from them. (These systems are said to provide models of Peano arithmetic.) It follows that these systems, too, contain undecidable propositions, and are incomplete.

Related category

   • LOGIC