FOM: The missing 1%

[Jeffrey Ketland]

Dear Hasan

Your question:

>I have read over and over that
>
>   "ZFC is a foundation of the %99 of mathematics."
>
>But what is the remaining %1 ?
>And why is ZFC not a foundation of this %1 ?

is an excellent question, one that involves most of the recent history of
the foundations of mathematics, including Godel's incompleteness theorems
and takes us right up to the present day.
Although I am not a historian of these topics, I will try and give a potted
history and explanation. (Comments, clarifications, refutations, etc.
welcome!)

1. 19th century foundational work

Prior to, say, 1900, mathematics was a pot-pourri of disciplines,
incorporating geometry, arithmetic (number theory), analysis, theory of
functions and differential equations, the beginnings of abstract algebra and
topology. However, around this time, many major mathematicians were
concerned with foundational questions - where does mathematics come from?
Around this time several currents of thought on foundational questions were
surfacing, including:

(i) early formalism, partly inspired by the discovery of non-Euclidean
geometries
(ii) Frege's logicism and his work on the foundations of arithmetic (1884:
Grundlagen der Arithmetic)
(iv) Dedekind and Peano on the foundations of arithmetic (roughly 1880s
onwards)
(v) early claims of or versions of finitism, constructivism and intuitionism
(vi) Cantor's work on transfinite sets (1880s onwards)
(vii) Hilbert's famous work on axiomatized geometry (1899: Grundlagen der
Geometrie)

Of particular importance was the work on the foundations of arithmetic.
Prior to this work by Frege, Dedekind and Peano, the 19th century program of
reducing analysis (theory of functions of the real variable) to arithmetic
had begun, mainly in the hands of Cauchy and Weierstrass, who succeeded in
giving precise definitons of such notions as "continuity" and "limit", which
didn't appeal to mysterious infinitesimals. Dedekind and Peano succeeded in
giving a system of axioms for arithmetic (now called Peano's Postulates or
Peano Arithmetic).

Frege thought he had provided a way of deducing these axioms for arithmetic
from pure logic alone! Frege thought he could define "number", "zero", and
"successor" and deduce all the axioms and theorems of Peano arithmetic from
a system of purely logical axioms. The ultimate foundation of all
mathematics would be pure logic. Hence the term *logicism*. However ....

2. The Paradoxes and the Rise of Set Theory

Frege's system of "logic" turned out to be logically inconsistent, as
discovered by Bertrand Russell, who communicated this to Frege in a letter
in 1901. (Cantor almost knew about this problem, and used the term
"inconsistent multiplicities" to refer to the inconsistent objects involved;
and so did Zermelo). Frege's axiomatic system (Frege's famous Axiom V)
implied the existence of the "Russell class", the class of all classes which
are not members of themselves. But this leads to a contradiction. The
mistake was this: Frege had assumed that the concept "class" or "extension
of a predicate" was a part of *logic*. He gave a famous axiom for the
concept of class (the comprehension scheme: every predicate has a class as
its extension) and this turned out to be inconsistent. The natural
conclusion is that questions about the existence of classes is not purely a
matter of logic after all, and if you assume too much about classes, then
you get inconsistency.

However, at roughly the same time Cantor had been developing a theory of
sets in order to solve certain problems about sets of real numbers (in
connection with the existence of Fourier expansions of real functions).
Cantor's theory of sets was regarded as blasphemy ("theology") by some
mathematicians, because Cantor treated infinite sets as mathematical
objects, and proved various strange theorems about infinite sets (e.g., the
power set of any infinite set X is larger than X). A couple of years later,
Ernst Zermelo first proved (1904) that the set of real numbers could be
well-ordered and, in response to some criticism from other mathematicians,
he gave (1908) a system of formal axioms for set theory. The system of
axioms is called Zermelo set theory or just Z (although, in order to prove
the well-ordering theorem, he needed an axiom called The Axiom of Choice, so
really the system he presented was ZC: Zermelo set theory with choice).

Meanwhile, in Cambridge, Bertrand Russell (with AN Whitehead) was trying to
extend Frege's logicist program, by showing how vast tracts of mathematics
(not just arithmetic) could be "translated" in the theory of sets (Russell's
own version of set theory is called the Theory of Types). In particular, all
the basic mathematical notions "zero", "successor", "plus", ..., "integer",
"function", "relation", "real number", "continuous", "limit" were getting
standard translations into set theory.

By the 1920s it was clear that a great deal of mathematics could be
translated into Zermelo's set theory (Russell's own Type theory was becoming
unpopular for various technical reasons). A few years later, Abraham
Fraenkel added a new axiom, called Replacement and the final axiom system,
ZFC, was born. (I don't know the exact date for this).
Very roughly, there were three main kinds of axiom systems around:

(i) axiomatic presentations of geometry (studied by Hilbert, and later by
Tarski and others)
(ii) axiomatic presentations of arithmetic (i.e., Peano arithmetic: PA)
(iii) axiomatic presentations of set theory (i.e., Russell's Type theory and
systems like Zermelo's Z).

There was a general feeling that any true statement of mathematics would be
a theorem of some axiomatic set theory (presumably Z or ZC or ZFC) and that
every true arithmetical statement would be provable in axiomatic arithmetic
(presumably PA). (Of course, geometry is a special case, since geometry is
really -- as Einstein's dicsoveries emphasized -- a part of physics, not
pure mathematics). So, although Frege's "logic" was not a good foundation
(being inconsistent, and thus not really being logic at all!), it might be
the case that axiomatic set theory was a good enough foundation for 100% of
mathematics.

It was just a question of further formalizing and so on, and every
mathematical problem could be solved in this way. David Hilbert was
especially optimistic on this score: his slogan was "Non Ignorabimus!" (we
shall not be ignorant).

3. The Bombshell: Godel's Incompleteness Theorems

In 1931, the Austrian mathematician Kurt Godel published what is widely
regarded as the most amazing mathematical discovery ever. He started with
the axioms given by Russell and Whitehead, known as PM (after their mammoth
treatise Principia Mathematica (1910-12)) and proved that,

 If the axioms of PM are consistent, then there are arithmetical sentences
which are neither provable nor refutable in PM.

In particular, he showed how to translate certain meta-mathematical
statements "x is a proof of a statement y in PM", "PM is consistent" into
statements of arithmetic. He showed how to construct:

 (i) a sentence G which means "G is not provable in PM"
 (ii) a sentence Con(PM) which means "PM is consistent"

and he showed that neither G nor Con(PM) are theorems of PM, if PM is
consistent. Indeed, if PM is true, then both G and Con(PM) are true, but
neither can be proved within PM.
In general, Godel proved that "any consistent sufficiently rich axiom system
must be incomplete". This applied not just to PA, but to Z, ZC, ZF, ZFC,
etc., etc.
(By an axiom system, we mean that there is a mechanical procedure for
deciding if a formula is an axiom and that there are mechanical inference
rules for generating proofs).
(Around the same time (1931-1933) Alfred Tarski developed a precise
meta-mathematical theory of truth and used similar Godelian arguments to
show that the set of true sentences in arithmetic is not definable in
arithmetic).

4. Since Then

Godel's incompleteness theorem implies that: If ZFC is consistent, then ZFC
is incomplete. There are true mathematical sentences (indeed, true
arithmetical sentences) which are not theorems of ZFC.

However, it is remains true that 99% of "ordinary" mathematical theorems
(perhaps 99.9999%) can be translated into the language of set theory and
proved.

Consequently, many mathematicians who reflected on this situation came to
the conclusion that, while Godel's discovery was amazing, there was
something strange about these weird unprovable "Godel sentences", and that
any "real" mathematical statement could, in fact, be proved from ZFC.
Indeed, they tended to forget all about foundations, and the incompleteness
theorems, and just carried on with their research (with tremendous success,
of course!).

However, it gradually became clear (between 1930s-1960s) that certain
fundamental problems (like the Continuum Hypothesis: Cantor's conjecture
about the size of the set of real numbers) could not be solved from the
axioms of ZFC. Independence results of this kind were given by Godel (1938)
and Cohen (1963).

In the 1970s a number of "ordinary mathematical statements" were shown to
behave like Godel sentences. In 1977, Paris and Harrington showed that a
version of a certain theorem due to Frank Ramsey is unprovable in PA.
Similarly, Harvey Friedman has shown that certain "combinatorial statements"
are not theorems of ZFC.

5. Now

ZFC is a very powerful system of axioms. It suffices to prove almost any
theorem you will find in any textbook in pure mathematics. ZFC provides a
kind of "unified theory of mathematics", just as physicists are looking for
a unified theory of gravity and quantum mechanics. Some people think that an
axiomatic set theory like ZFC formalized in first-order predicate logic
provides the fundamental way to think about mathematics as a unified whole
(NB: others pursue different foundational programmes, based, e.g., on
category theory or constructive mathematics).

There are various axiomatic subsystems of ZFC and there are various
axiomatic extensions of PA, which lie between PA and ZFC in strength. One
such system is called "Second-Order arithmetic" (confusingly called Z_2) and
it has various important subsystems, which have also been studied (such as
RCA_0, ACA_0, etc.). On this topic, Stephen G. Simpson has recently
published a (very advanced) monograph called "Subsystems of Second-Order
Arithmetic" (1999) which explains how vast amounts of core mathematics can
be formalized within Z_2 or some subsystem. Indeed, Simpson develops the
Reverse Mathematics program (associated with Harvey Friedman) in which
"core" mathematical statements are calibrated by being shown to be
equivalent (over what is called the base theory, standardly RCA_0) to some
subsystem of second-order arithmetic. For example, the Bolzano-Weierstrass
Theorem is equivalent to the subsystem known as ACA_0. In Simpson's book,
countless "core" mathematical theorems are located within this hierarchy of
formalized mathematical axiom systems.

6. Summary

In summary, there are a tiny number of mathematical statements that are
known to be independent of ZFC (assuming that ZFC is consistent). That is,
if A is one of these statements, then you cannot prove A in ZFC and you
cannot prove ~A either. The most obvious ones are just the original Godel
sentences, which are coded statements about provability and consistency.
There are also some very abstract set-theoretical statements concerning the
existence of extremely large sets, known as inaccessible cardinal numbers.
There is Cantor's Continuum Hypothesis itself; and there are the
"lower-level", more core or concrete combinatorial examples discovered by
Harvey Friedman.

This is why there has been a discussion recently on the fom discussion list
about whether "mathematics needs new axioms". These axioms -- the choice of
which (indeed, the very *meaning* of which) is very controversial -- would
be added as new axioms to solve these problems which cannot be settled using
ZFC.

Jeff

Dr Jeffrey Ketland
Department of Philosophy C15 Trent Building
University of Nottingham NG7 2RD
Tel: 0115 951 5843
E-mail: Jeffrey.Ketland at nottingham.ac.uk