## Gödel's Theorem

*25 Apr 2013 16:16*

A much-abused result in mathematical logic, supposed by many authors who don't understand it to support their own favored brand of rubbish, and even subjected to surprisingly rough handling by some who really should know better.

Let me start by trying to make clear just what the theorem states, before
going on to poke at the two most common abuses. Gödel's theorem is a
result about axiomatic systems, which is already a source of some confusion.
In ordinary educated speech, axioms are undubitable truths; for mathematicians,
they are propositions it is convenient or amusing to start from. An axiomatic
system consists of some undefined terms, a bunch 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 really
two points to setting up an axiomatic system. First, it's a very compact
description 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 it's so abstract, the system lets us derive all and only the results
which follow from things having the formal properties specified by the axioms.
One can set up axiomatic systems describing, say, kinship networks, and then
you get results which depend only on having two parents, one of each sex, and
so are applicable to anything with that formal property; and similarly for
axiomatic geometry, algebra, etc., etc. An axiomatic system is said to be
*consistent* if, given the axioms and the derivation rules, we can never
derive two contradictory propositions; obviously, we want our axiomatic systems
to be consistent.

One of the first modern axiomatic systems was a formalization of simple
arithmetic (adding and multiplying whole numbers) by the great logician
Giuseppe Peano, called 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 which are about propositions. In
particular, we can write down self-referential propositions, ones which include
their own Gödel number. (This usually won't work if numerals are
represented by themselves, of course.) From here, Gödel showed that,
*either* the system is inconsistent (horrors!), *or* there are
true propositions which 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). [**Update, June 2005**: Actually, that's wrong.
Wolfgang Beirl has
pointed out to me that Goodstein's
Theorem is a result about natural numbers which is undecidable within Peano
arithmetic, but provable within stronger set-theoretic systems. And it's
actually a neat theorem, with no self-referential weirdness!]

So far we've just been talking about Peano arithemtic, but now comes the
kicker. Results about an axiomatic system apply to any bunch of things which
satisfy the axioms. There are an immense number of other axiomatic systems
which either include Peanese numbers among their basic entities, or where such
things can be put together; they either have numbers, or can construct them.
(These systems are said to provide *models* of Peano arithmetic.) It
follows that these systems, too, contain undecidable propositions, and are
incomplete.

There are two very common but fallacious conclusions people make from this,
and an immense number of uncommon but equally fallacious errors I shan't bother
with. The first is that Gödel's theorem imposes some some of profound
limitation on knowledge, science, mathematics. Now, as to science, this
ignores in the first place that Gödel's theorem applies to *deduction
from axioms,* a useful and important sort of reasoning, but one so far from
being our only source of knowledge it's not even funny. It's not even a very
common mode of reasoning in the sciences, though there are axiomatic
formulations of some parts of physics. Even within this comparatively small
circle, we have at most established that there are some propositions about
numbers which we can't prove formally. As Hintikka says, "Gödel's
incompleteness result does not touch directly on the most important sense of
completeness and incompleteness, namely, descriptive completeness and
incompleteness," the sense in which an axiom systems describes a given field.
In particular, the result "casts absolutely no shadow on the notion of truth.
All that it says is that the whole set of arithmetical truths cannot be listed,
one by one, by a Turing machine." Equivalently, there is no algorithm which
can decide the truth of *all* arithmetical propositions. And that is
all.

This brings us to the other, and possibly even more common fallacy, that
Gödel's theorem says artificial intelligence is impossible, or that
machines cannot think. The argument, so far as there is one, usually runs as
follows. Axiomatic systems are equivalent to abstract computers, to Turing
machines, of which our computers are (approximate) realizations. (True.)
Since there are true propositions which cannot be deduced by interesting
axiomatic systems, there are results which cannot be obtained by computers,
either. (True.) But we can obtain those results, so our thinking cannot be
adequately represented by a computer, or an axiomatic system. Therefore, we
are not computational machines, and none of them could be as intelligent as we
are; *quod erat demonstrandum.* This would actually be a valid
demonstration, were only the pentultimate sentence true; but no one has ever
presented any evidence that it *is* true, only vigorous hand-waving and
the occasional heartfelt assertion.

Gödel's result is of course quite interesting, if you're doing mathematical logic, and it even has some importance for that odd little specialization of logic, the theory of computation. (It is intimately related to the halting problem, for instance.) It also makes a fine piece of general mathematical culture; but it doesn't shake the foundations of the house of intellect, or exalt us above all else that greps.

(Thanks to Jakub Jasinski for politely pointing out an embarrassing error in an earlier version.)

- Recommended:
- Michael Arbib, Brains, Machines and Mathematics [A good sketch of the proof of the theorem, without vaporizing]
- George S. Boolos and Richard C. Jeffrey, Computability and Logic [Textbook, with a good discussion of incompleteness results, along with many other things. Intended more for those interested in the logical than the computational aspects of the subject — they do more with model theory than with different notions of computation, for instance — but very strong all around.]
- Torkel Franzen, Gödel's on the net [Gentle debunking of many of the more common fallacies and misunderstandings]
- Jaakko Hintikka, The Principles of Mathematics Revisited [Does a nice job of defusing Gödel's theorem, independently of some interesting ideas about logical truth and the like, about which I remain agnostic. My quotations above are from p. 95]
- Dale Myers, Gödel's Incompleteness Theorem [A very nice web page that builds slowly to the proof]
- Roger Penrose, The Emperor's New Mind [Does a marvelous job of explaining what goes into the proof — his presentation could be understood by a bright high school student, or even an MBA — but then degenerates into an unusually awful specimen of the standard argument against artificial intelligence]
- Willard Van Orman Quine, Mathematical Logic [Proves a result which is actually somewhat stronger than the usual version of Gödel's theorem in the last chapter, which however adds no philosophical profundity; review]
- Raymond Smullyan, Gödel's Incompleteness Theorems [A mathematical textbook, not for the faint at heart, though the first chapter isn't so bad; one of the few to notice the strength of Quine's result]

- To read:
- John C. Collins, "On the Compatibility Between Physics and Intelligent Organisms," physics/0102024 [Claims to have a truly elegant refutation of Penrose]
- Rebecca Goldstein, Incompleteness [Biography of Gödel, which seems to actually understand the math]
- Ernest Nagel and James R. Newman, Gödel's Proof [Thanks to S. T. Smith for the recommendation]
- Mario Rabinowitz, "Do the Laws of Nature and Physics Agree About What is Allowed and Forbidden?" physics/0104001
- Antonin Spacek, "Statistical Estimation of Semantic Provability", Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability (1961), vol. 1, pp. 655--668

*(Apr 17 15:52 1998)*