Mr. Turing’s amazing machines - The Computing Universe: A Journey through a Revolution - page 103

more abstract formulation that allowed the exploration of new kinds of algebra
with different rules and symbols. This led to the development of new fields of
research such as “group theory” and “Hilbert spaces,” both of which ultimately
found application in physics. However, attempts to show that the whole edifice
of this more formal approach to mathematics was consistent and free from
contradictions had run into trouble. The key challenge was to show that manip-
ulating the symbols according to the agreed rules always made sense and did
not lead to contradictions such as being able to prove that 2 + 2 = 5.
The German logician Gottlob Frege ( B.6.2 ) and the Welsh mathematician
Bertrand Russell ( B.6.3 ) had independently approached the problem of prov-
ing the consistency of mathematics using the ideas of set theory. A set is just
a collection of objects characterized by a particular property. For example, we
can define a set that contains all the men in a town. We can also define a sub-
set of this set that comprises all the men in the town with red hair, and so on.
However, in 1901, Russell noticed that logical contradictions arose when he
tried to use “sets of all sets” in his arguments. He explained his paradox with
the example of a town that had only one male barber and where all the men
were clean shaven ( Fig. 6.1 ). The paradox can then be stated as: The barber in
this town shaves only men who do not shave themselves. In this case, we have the set
of all men in the town, and within this set there are two subsets - men who
shave themselves and men who are shaved by the barber. The paradox is into
which subset do we put the barber? Since these sets were taken to be abstract
entities there was no way of resolving the contradiction by asking what the
symbols really meant. The whole idea of Frege and Russell's program was “to
derive arithmetic from the most primitive logical ideas in an automatic, water-
tight, depersonalized way.” 2 Russell wrote a letter about this paradox to Frege
in 1902 and Frege's reply gives some idea of the consternation that Russell's
letter caused:

B.6.2. Gottlob Frege (1848-1925)
was working on the axiomatization
of mathematics trying to derive a
logical system that is complete and
has no contradictions. His pioneer-
ing work had a significant impact on
later discoveries in mathematics.

Your discovery of the contradiction has surprised me beyond words and, I
should almost like to say, left me thunderstruck, because it has rocked the
ground on which I meant to build arithmetic. Your discovery is at any rate
a very remarkable one and it may perhaps lead to a great advance in logic,
undesirable as it may seem at first sight. 3

By 1928, the focus had moved on from Frege and Russell's ambitious attempts
to determine what mathematics really was. Instead, Hilbert was asking deep
questions about the logical foundations of mathematics. In 1899 he had suc-
ceeded in finding a set of axioms - a small number of self-evident truths -
from which he could prove all the theorems of Euclidean geometry without
any need to relate his proofs to the geometry of the actual physical world.
A year later, at a conference in Paris, Hilbert proposed a list of twenty-three
important unsolved mathematical problems. The number two question on his
list was “the compatibility of the arithmetical axioms.” Of the many ques-
tions that could be asked about these axioms, he said that the most important
question was:

B.6.3. Bertrand Russell (1872-1970)
mathematician and philosopher.
With Alfred Whitehead in 1910
he published Principia Mathematica
with more than a thousand pages in
which they tried to put mathemat-
ics on solid foundations. They soon
learned that mathematics is not
“perfect” because there are many
paradoxes that mathematics cannot
answer.

To prove that they are not contradictory, that is, that a definite number of
logical steps based upon them can never lead to contradictory results. 4