552 19. LOGIC AND SET THEORYThe most influential figure in mathematical logic during the twentieth century
was Godel. The problems connected with consistency and completeness of arith-
metic, the axiom of choice, and many others all received a fully satisfying treatment
at his hands that settled many old questions and opened up new areas of investi-
gation. In 1931, he astounded the mathematical world by producing a proof that
any consistent formal language in which arithmetic can be encoded is necessarily
incomplete, that is, contains statements that are true according to its metalanguage
but not deducible within the language itself. The intuitive idea behind the proof is
a simple one, based on the statement that follows:
This statement cannot be proved.
Assuming that this statement has a meaning—that is, its context is properly
restricted so that "proved" has a definite meaning—we can ask whether it is true.
The answer must be positive if the system in which it is made is consistent. For
if this statement is false, by its own content, it can be proved; and in a consistent
deductive system, a false statement cannot be proved. Hence we agree that the
statement is true, but, again by its own content, it cannot be proved.
The example just given is really nonsensical, since we have not carefully de-
lineated the universe of axioms and rules of inference in which the statement is
made. The word "proved" that it contains is not really defined. Godel, however,
took an accepted formalization of the axioms and rules of inference for arithmetic
and showed that the metalanguage of arithmetic could be encoded within arith-
metic. In particular each formula can be numbered uniquely, and the statement
that formula ç is (or is not) deducible from those rules can itself be coded as a
well-formed formula of arithmetic. Then, when ç is chosen so that the statement,
"Formula number ç cannot be proved" happens to be formula n, we have exactly
the situation just described. Godel showed how to construct such an n. Thus, if
Godel's version of arithmetic is consistent, it contains statements that are formally
undecidable; that is, they are true (based on the metalanguage) but not deducible.
This is Godel's first incompleteness theorem. His second incompleteness theorem
is even more interesting: The assertion that arithmetic is consistent is one of the
formally undecidable statements.^14 If the formalized version of arithmetic that
Godel considered is consistent, it is incapable of proving itself so. It is doubtful,
however, that one could truly formalize every kind of argument that a rational per-
son might produce. For that reason, care should be exercised in drawing inferences
from Godel's work to the actual practice of mathematics.
3. Philosophies of mathematics
Besides Cantor, other mathematicians were also considering ways of deriving math-
ematics logically from simplest principles. Gottlob Frege (1848-1925), a professor
in Jena, who occasionally lectured on logic, attempted to establish logic on the basis
of "concepts" and "relations" to which were attached the labels true or false. He
was the first to establish a complete predicate calculus, and in 1884 wrote a treatise
called Grundgesetze der Arithmetik (Principles of Arithmetic). Meanwhile in Italy,
Giuseppe Peano (1858-1939) was axiomatizing the natural numbers. Peano took
the successor relation as fundamental and based his construction of the natural(^14) Detlefsen (2001) has analyzed the meaning of proving consistency in great detail and concluded
that the generally held view of this theorem—that the consistency of a "sufficiently rich" theory
cannot be proved by a "finitary" theory—is incorrect.