## Gödel's incompleteness theoremIn 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 | |||||

Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact |