THE SHAPE OF LOGIC
The Shape of Logic
As the superstructure of mathematics grew ever larger, a small number of mathematicians began to wonder whether the foundations could support its weight. A series of foundational crises - in particular the controversies over the basic concepts of calculus and the general confusion about Fourier series -had made it clear that mathematical concepts must be defined very carefully and precisely to avoid logical pitfalls. Otherwise the subject's towers of deduction could easily collapse in logical contradictions, because of some underlying vagueness or ambiguity.
At first, such worries were focused on complicated, sophisticate*] ideas, such as Fourier series. But slowly the mathematical worlfl came to realize that very basic ideas might also be susped Paramount among them was the concept of a number.The dreadful truth was that mathematicians had devoted so much effort to the discovery of deep properties of numbers that they had neglected lo ask what numbers were. And when it came to giving a logic.)I definition, they didn't know.
fn 1858, teaching a calculus course, Dedekind became worried about the basis of calculus. Not its use of limits, but the system of real numbers. He published his thoughts in 1872 as Stetigkeit und Irrationale Zaliien, pointing out that apparently obvious properties of real numbers had never been proved in any rigorous way. As an example he cited the equation /I /3 = /6. Obviously this fact follows by squaring both sides of the equation - except that multiplication of irrational numbers had never actually been defined. In his 1888 book Was Sind und was Sollen die Zahlen? (What are Numbers, and What do They Mean?) he exposed serious gaps in the logical foundations of the system of real numbers. No one had really proved that the real numbers exist.
He also proposed a way to fill these gaps, using what we now call Dedekind cuts. The idea was to start from an established number system, the rational numbers, and then to extend this system to obtain the richer system of real numbers. His approach was to start from the properties required of real numbers, find some way to rephrase them solely in terms of rational numbers and then reverse the procedure, interpreting those features of rational numbers as a definition of the reals. This kind of reverse engineering of new concepts from old ones has been widely used ever since.
Suppose, for the moment, that real numbers do exist. How do they relate to rational numbers? Some reals are not rational, an obvious example being (2 . Now, although it is not an exact fraction, it can be approximated as closely as we wish by rationals. It somehow sits in a specific position, sandwiched among the dense array of all possible rationals. But how can we specify that position? Dedekind realized that Jl neatly separates the set of rational numbers into two pieces: those that are less than /2 , and those that are greater. In a sense, this separation - or cut - defines the number /2 in terms of rationals. The only snag is that we make
308
309
TAMING THE INFINITE
THE SHAPE OF LOGIC
use of /2 in order to define the two pieces of the cut. However, there is a way out. The rational numbers greater than /2 are precisely those that are positive, and for which the square is greater than 2. The rational numbers less than (1 are all the others. These two sets of rational numbers are now defined without any explicit use of /!, but they specify its location on the real-number line precisely.
Dedekind showed that if, for the sake of argument, we assume that the real numbers exist, then a cut satisfying these two properties can be associated with any real number, by forming two sets: the set R of all rationals that are larger than that real number, and tin-set L of all rationals that are smaller than that real number, or equal to it. (The final condition is needed to associate a cut with any rational number. We don't want to leave them out.) Here L and R can be read as left and right in the usual picture of the real number line.
L X R
These two sets L and R obey some rather stringent conditions. First, every rational number belongs to precisely one of them. Second, every number in R is greater than any number in L. Finally, there is a technical condition that takes care of the rational numbers themselves: L may or may not have a largest member, but R never has a smallest member. Call any pair of subsets of the rationals witli these properties a cut.
In reverse engineering, we do not need to assume that real numbers exist. Instead, we can use cuts to define real numbers, so that effectively a real number is a cut. We don't usually think of >i real number that way, but Dedekind realized that we can do so if we wish. The main task is to define how to add and multiply cuts, so that the arithmetic of real numbers makes sense. This turns out to be easy. To add two cuts (Lx, Ri) and (L2, R2), define L; 4- L2 to !><■ the set of all numbers obtainable by adding a number in L, to a number in L2 and similarly define R[ + R2.Then the sum of the two
cuts is the cut (Li + L2, Ri + R2). Multiplication is similar, but positive and negative numbers behave slightly differently.
Finally, we have to verify that the arithmetic of cuts has all the features that we expect of real numbers.These include the standard laws of algebra, which all follow from analogous features of rational numbers.The crucial feature, which distinguishes the reals from the rationals, is that the limit of an infinite sequence of cuts exists (under certain technical conditions). Equivalently, there is a cut corresponding to any infinite decimal expansion. This is also fairly straightforward.
Assuming all this can be done, let's see how Dedekind can then prove that (1 /3 = /6 . We have seen that /I corresponds to the cut (Ll R[) where Rj consists of all positive rationals die square of which is greater than 2. Similarly, /3 corresponds to the cut (L2, R2) where R2 consists of all positive rationals the square of which is greater than 3. The product of these cuts is easily proved to be (L3, R3) where R3 consists of all positive rationals the square of which is greater than 6. But this is the cut corresponding to /6, Done!
The beauty of Dedekind's approach is that it reduces all issues concerning real numbers to corresponding issues about rational numbers - specifically, about pairs of sets of rational numbers. It therefore defines real numbers purely in terms of rational numbers and operations on those numbers. The upshot is that real numbers exist (in a mathematical sense) provided rational numbers do.
There is a small price to pay: a real number is now defined as a pair of sets of rationals, which is not how we usually think of a real number. If this sounds strange, bear in mind that the usual representation of a real number as an infinite decimal requires an infinite sequence of decimal digits 0-9. This is conceptually at least as complicated as a Dedekind cut. But it is actually very tricky to define the sum or product of two infinite decimals, because the usual arithmetical methods for adding or multiplying decimals
310
311
r
TAMING THE INFINITE
start from the right-hand end — and when a decimal is infinite, it doesn't have a right-hand end.
Mmm for vMM mm^;
Dedekind's book was all very well as a foundational exercise, but as the general point about defining your terms sank in, it was soon realized that the book had merely shifted attention from the reals to the rationals. How do we know that rational numbers exist? Well, if we assume the integers exist, this is easy: define a rational p/q to be a pair of integers (p, q) and work out the formulas for sums and products. If integers exist, so do pairs of integers.
Yes, but how do we know that integers exist? Apart from a plus or minus sign, integers are ordinary whole numbers.Taking care ol the signs is easy.So, integers exist provided whole numbers do.
We still haven't finished, though. We are so familiar with whole numbers that it never occurs to us to ask whether the familiar numbers 0, 1,2,3 and so on actually exist. And if they do, what arc they?
In 1889, Giuseppe Peano sidestepped the question of existence by taking a leaf out of Euclid's book. Instead of discussing the existence of points, lines, triangles and the like, Euclid simply wrote down a list of axioms - properties that would be assumed without further question. Never mind whether points and so on exisi - a more interesting question is: if they did, what properties would follow? So Peano wrote down a list of axioms for whole numbers. The main features were:
There exists a number 0. Every number n has a successor, s(n) (which we think of as n+l).
If P(n) is a property of numbers, such that P(0) is true, and whenever P(n) is true then P(s(n)) is true, then P(n) is true for every n (Principle of Mathematical Induction).
Mil   MIA: I ill men;
He then defined the numbers 1, 2 and so on in terms of those axioms, essentially by setting
1 = s(0)
2 = s(s(0))
and so on. And he also defined the basic operations of arithmetic and proved that they obey the usual laws. In his system, 2 + 2 = 4 is a provable theorem, stated as s(s(0)) + s(s(0)) = s(s(s(s(0)))).
A great advantage of this axiomatic approach is that it pins down exactly what we have to prove if we want to show, by some means or other, that whole numbers exist. We just have to construct some system that satisfies all of Peano's axioms.
The deep question here is the meaning of'exist' in mathematics. In the real world, something exists if you can observe it, or, failing that, infer its necessary presence from things that can be observed. We know that gravity exists because we can observe its effects, even though no one can see gravity. So, in the real world, we can sensibly talk about the existence of two cats, two bicycles or two loaves of bread. However, the number two is not like that. It is not a thing, but a conceptual construct. We never meet the number two in the real world. The closest we get is a symbol, 2, written or printed on paper, or displayed on a computer screen. However, no one imagines that a symbol is the same as the thing it represents.The word'cat' written in ink is not a cat. Similarly, the symbol 2 is not the number two.
Tire meaning of'number' is a surprisingly difficult conceptual and philosophical problem. It is made all the more frustrating by the fact that we all know perfectly well how to use numbers. We know how they behave, but not what they are.
$m mi dmm
In the 1880s Gottlob Frege tried to resolve this conceptual issue by constructing whole numbers out of even simpler objects - namely
312
313
TAMING THE INFINITE
THE SHAPE OF LOGIC
sets, or classes as he called them. His starting point was the standard association of numbers with counting. According to Frege, two is a property of those sets - and only those - that can be matched one-to-one with a standard set {a, b} having distinct members a and b.So
{one cat, another cat}
{one bicycle, another bicycle}
{one loaf, another loaf}
can all be matched with {a, b}, so they all determine - whatever thai means — the same number.
Unfortunately, using a list of standard sets as numbers seems to beg the question - it's very like confusing a symbol with what it represents. But how can we characterize 'a property of diose sets thai can be matched one-to-one with a standard set'? What is a property? Frege had a wonderful insight.There is a well-defined set that is associated with any property; namely, the set consisting of everything that possesses that property. The property 'prime' is associated with the set of all prime numbers; the property 'isosceles' is associated with the set of all isosceles triangles, and so on.
So Frege proposed that number two is the set comprising all sets that can be matched one-to-one with the standard set {a, b}. More generally, a number is the set of all sets that can be matched to any given set. So, for example, the number 3 is the set
{... {a, b, c}, {one cat, another cat, yet another cat}, {X, Y, Z},...} although it is probably best to use mathematical objects in place of cats or letters.
On this basis, Frege discovered that he could put all of the arithmetic of the whole numbers on a logical basis. It all reduced to obvious properties of sets. He wrote everything up in his masterwork Die Grundlagen der Arithmetik (The Foundations of Arithmetic) of 1884, but to his bitter disappointment Georg Cantor, a leading mathematical logician, dismissed the book as worthless. In 1893
Frege, undaunted, published the first volume of another book, Die Grundgesetze der Arithmetic (The Basic Laws of Mthmetk), in which he provided an intuitively plausible system of axioms for arithmetic. Peano reviewed it, and everyone else ignored it. Ten years later, Frege was finally ready to publish volume two, but by then he had noticed a basic flaw in his axioms. Others noticed this as well. While volume two was in press, disaster struck. Frege received a letter from the philosopher-mathematician Bertrand Russell, to whom he had sent an advance copy of his book. To paraphrase, the letter said roughly this: 'Dear Gottlob, consider the set of all sets that are not members of themselves. Yours, Bertrand.'
Frege was a superb logician and he immediately got Russell's point — indeed, he was already aware of the potential for trouble. Frege's whole approach had assumed, without proof, that any
Russell's Paradox
A less formal version of the paradox proposed by Russell is the village barber, who shaves everyone who does not shave themselves. Who shaves the barber? If he does shave himself, then by definition he is shaved by the village barber - himself! If he does not shave himself, then he is shaved by the barber - which, again, is himself.
Aside from various cooks -the barber is a woman, for instance -the only possible conclusion is that no such barber exists. Russell reformulated this paradox in terms of sets. Define a set X to consist of all sets that are not members of themselves. Is X a member of itself, or not? If it is not, then by definition it belongs to X - itself. If it is a member of itself, then like all members of X, it is not a member of itself. So, X is a member of itself if it is not, and it is not a member of itself it is. This time there is no way out-female sets are not yet part of the mathematical enterprise.
314
315
reasonable property defined a meaningful set, consisting of those objects that possess the property concerned. But here was an apparently reasonable property, not a member of itself, which manifestly did not correspond to a set.
A glum Frege penned an appendix to his magnum opus, discussing Russell's objection. He found a short-term fix: eliminate from the realm of sets any that are members of themselves. But he was never really happy with this proposal.
Russell, for his part, tried to repair the gap in Frege's construction of whole numbers from sets. His idea was to restrict the kind of property that could be used to define a set. Of course he had to find a proof that this restricted kind of property never led to a paradox. In collaboration with Alfred North Whitehead, he came up with a complicated and technical theory of types which achieved that objective, to their satisfaction at least.They wrote their approach in a massive three-volume tome Prinripia Mathematica of 1910-13. The definition of the number 2 is near the end of volume one, and the theorem 1 + 1 = 2 is proved on page 86 of volume two. However, Principia Mathematica did not end the foundational debate. The theory of types was itself contentious. Mathematicians wanted something simpler and more intuitive.
Cantor
These analyses of the fundamental role of counting as the basis for numbers led to one of the most audacious discoveries in the whole of mathematics: Cantor's theory of tronsfinite numbers - different sizes of infinity.
Infinity, in various guises, seems unavoidable in mathematics. There is no largest whole number - because adding one always produces a larger number still — so there are infinitely many whole numbers. Euclid's geometry takes place on an infinite plane, and he proved that there are infinitely many prime numbers. In the runup to calculus, several people, among them Archimedes, found it
316
useful to think of an area or a volume as being the sum of infinitely many infinitely thin slices. In the aftermath of calculus, the same picture of areas and volumes was used for heuristic purposes, even if the actual proofs took a different form.
These occurrences of the infinite could be rephrased in finite terms to avoid various philosophical difficulties. Instead of saying 'there are infinitely many whole numbers', for instance, we can instead say 'there is no largest whole number' .The second statement avoids explicit mention of the infinite, while being logically equivalent to the first. Essentially, infinity is here being thought of as a process, which can be continued widiout any specific limit, but is not actually completed. Philosophers call this kind of infinity potential infinity. In contrast, explicit use of infinity as a mathematical object in its own right is actual infinity.
Mathematicians prior to Cantor had noticed that actual infinities had paradoxical features. In 1632 Galileo wrote his Dialogue Concerning the Two Chief World Systems, in which two fictional characters, the sagacious Salviati and the intelligent layman Sagredo, discuss die causes of tides, from the geocentric and heliocentric viewpoints. All mention of tides was removed at the request of church audiorities, making the book a hypothetical exercise which nonetheless makes a powerful case for Copernicuss heliocentric theory. Along the way, the two characters discuss some of the paradoxes of infinity. Sagredo asks 'are there more numbers than squares?' and points out that since most whole numbers are not perfect squares, the answer must be yes. Salviati replies that every number can be matched uniquely to its square:
1	2	3	4	5	6	7
1	I	I	I	i	I	1
1	4	9	16	25	36	49
Therefore the number of whole numbers must be the same as that of squares, so the answer is no.
317
TAMING THE INFINITE
Cantor resolved this difficulty by recognizing that in the dialogue, the adjective 'more' is being used in two different ways. Sagredo is pointing out that the set of all squares is a proper subset of the set of all whole numbers. Salviati's position is subtler: he is arguing thai there is a one-to-one correspondence between the set of all squares and the set of all whole numbers. Those statements are different, and both can be true without leading to any contradiction.
Pursuing this line of thought, Cantor was led to the invention of an arithmetic of the infinite, which explained the previous paradoxes while introducing some new ones. This work was part of a more extensive programme, Mengenlehre, the mathematics of sets (Menge in German means set or assemblage). Cantor began thinking about sets because of some difficult questions in Fourier analysis, so the ideas were rooted in conventional mathematical theories. But the answers he discovered were so strange that many mathematicians of the period rejected them out of hand. Others, however, realized their value, notably David Hubert, who affirmed 'No one shall expel us from the paradise that Cantor has created'.
Set m®
Cantor's starting point was the naive concept of a set, which is a collection of objects, its members. One way to specify a set is to list the members, using curly brackets. For instance, the set of all whole numbers between 1 and 6 is written
{1, 2, 3, 4, 5, 6}
Alternatively, a set can be specified by stating the rule for membership:
{n : 1 £ n s 6 and n is a whole number}
The sets specified above are identical.The first notation is limited to finite sets, but the second has no such limitations. Thus die sets
(n : n is a whole number}
THE SHAPE OF LOGIC
and
{n : n is a perfect square}
are both specified precisely, and both are infinite.
One of the simplest things you can do with a set is count its members. How big is it?The set {1, 2, 3, 4, 5, 6} has six members. So does the set {1, 4, 9, 16, 25, 36} consisting of the corresponding squares. We say that the cardinality of the set is 6, and call 6 a cardinal number. (There is a different concept, ordinal number, associated with putting numbers in order, which is why the adjective 'cardinal' is not superfluous here.) The set of all whole numbers cannot be counted in this manner, but Cantor noticed that despite that, you can place the set of all whole numbers and the set of all squares in one-to-one correspondence, using the same scheme as Galileo. Each whole number n is paired with its square nz.
Cantor defined two sets to be equinumerous (not his word) if there exists a one-to-one correspondence between them. If the sets are finite, this property is equivalent to 'having the same number of members'. But if the sets are infinite, it apparently makes no sense to talk of the number of members; nevertheless the concept of equinumerosity makes perfect sense. But Cantor went further. He introduced a system of transfinite numbers, or infinite cardinals, which did make it possible to say how many members an infinite set has. Moreover, two sets were equinumerous if and only if they had the same number of members — the same cardinal.
The starting point was a new kind of number, which he denoted by the symbol H0. This is the Hebrew letter aleph with a subscript zero, read as aleph-null in German, nowadays aleph-zero. This number is defined to be the cardinality of the set of all whole numbers. By insisting that equinumerous sets have the same cardinality, Cantor then required any set that can be placed in one-to-one correspondence with the set of all whole numbers
TAMING THE INFINITE
THE SHAPE OF LOGIC
also to have cardinality Nq. For instance, the set of all squares has cardinality H0. So does the set of all even numbers:
1	2	3	4	5	6	7
4	4	I	4	I		4
2	4	6	8	10	12	14
set of all odd numbers:						
1	2	3	4	5	6 ,	7
4	4	4	4	4	4-	
1	3	5	7	9	11	13
One implication of these definitions is that a smaller set can have the same cardinality as a bigger one. But there is no logical contradiction here to Cantor's definitions, so he considered this feature to be a natural consequence of his set-up, and a price worth paying. You just have to be careful not to assume that infinite cardinals behave just like finite ones. But why should they?They are not finite!
Are there more integers (positive and negative) than whole numbers? Aren't there twice as many? No, because we can match the two sets like this:
1 4 0
3
i
4 4
5 4
2 -2
7 I
-3
The arithmetic of infinite cardinals is also strange. For instance, we have just seen that the sets of even and odd whole numbers have cardinal H0. Since these sets have no members in common, the cardinal of their union - the set formed by combining them -should, by analogy with finite sets, be HD + N0. But we know what
that union is: it is the whole numbers, with cardinal N0. So apparently we are forced to deduce that
No + *o = K>-
And so we are. But again, there is no contradiction: we cannot divide by Nq, to deduce that 1 + 1 = 1, because N0 is not a whole number and division has not been defined, let alone been shown to make sense. Indeed, this equation shows that division by KQ does not always make sense. Again, we accept this as the price of progress.
This is all very well, but it looks as though N0 is just a fancy symbol for good old «, and nothing new is really being said. Is it not the case that all infinite sets have cardinal Nc? Surely all infinities are equal?
One candidate for an infinite cardinal greater than N0 - that is, an infinite set that cannot be put in one-to-one correspondence with the set of all whole numbers - is the set of all rational numbers, which is usually denoted by Q. After all, there are infinitely many rational numbers in the gap between any two consecutive integers, and the kind of trick we used for the integers no longer works.
However, in 1873 Cantor proved that Q also has cardinal No.The one-to-one correspondence shuffles the numbers quite thoroughly, but no one said that they had to remain in numerical order. It was beginning to look remarkably as though every infinite set had cardinal N0.
In the same year, though, Cantor made a breakthrough. He proved that the set IR of all real numbers does not have cardinal N0. an astonishing theorem that he published in 1874. So even in Cantor's special sense, there are more reals than integers. One infinity can be bigger than another infinity.
How big is the cardinal of the reals? Cantor hoped diat it would be N,, the next largest cardinal after Hq. But he could not prove this, so he named the new cardinal c, for continuum. The hoped-for equation c = N] was called the continuum hypothesis. Only in 1960 did
TAMING THE INFINITE
THE SHAPE OF LOGIC
mathematicians sort out the relationship between c and , when Paul Cohen proved that the answer depends on which axioms you choose for set theory. With some sensible axioms, the two cardinals are the same. But with other, equally reasonable axioms, they are different.
Although the validity of the equation c = K, depends on the chosen axioms, an associated equality does not. This is c = 2V For any cardinal A we can define 2Aas the cardinal of the set of all subsets of A. And we can prove, very easily, that 2A is always bigger than A. This means that not only are some infinities bigger than others: there is no largest infinite cardinal.
The biggest task of foundational mathematics, however, was not proving that mathematical concepts exist. It was to prove thai mathematics is logically consistent. For all mathematicians knew -indeed, for all they know today - there might be some sequence of logical steps, all perfectly correct, leading to an absurd conclusion. Maybe you could prove that 2 + 2 = 5, or 1 = 0, for instance. Or that 6 is prime, or jt = 3.
Now, it might seem that one tiny contradiction would have limited consequences. In everyday life, people often operate very happily within a contradictory framework, asserting at one moment that, say, global warming is destroying the planet, and a moment later that low-cost airlines are a great invention. But in mathematics, consequences are not limited, and you can't evade logical contradictions by ignoring them. In mathematics, once something is proved you can use it in other proofs. Having proved 0 = 1, much nastier things follow. For instance, all numbers are equal. For if x is any number, start from 0=1 and multiply both sides by x. Then 0 = x. Similarly, if y is any other number, 0 — y. But now x = y. . Worse, the standard method of proof by contradiction means that anything can be proved once we have proved that 0 = 1. To prove Fermat's Last Theorem, say, we argue like this:
322
Suppose Fermat's Last Theorem is false. Then (as already proved) 0=1. Contradiction. Therefore Fermat's Last Theorem is true.
As well as being unsatisfying, this method also proves Fermat's Last Theorem is false:
Suppose Fermat's Last Theorem is true. Then (as already proved) 0=1. Contradiction. Therefore Fermat's Last Theorem is false.
Once everything is true - and also false - nodiing meaningful can be said. The whole of mathematics would be a silly game, with no content.
Hilbert
The next major foundations step was taken by David Hilbert, probably the leading mathematician of his day. Hilbert had a habit of working in one area of mathematics for about ten years, polishing off the main problems, and moving on to a new area. Hilbert became convinced that it should be possible to prove that mathematics can never lead to a logical contradiction. He also realized that physical intuition would not be useful in such a project. If mathematics is contradictory, it must be possible to prove that 0 = 1, in which case there is a physical interpretation: 0 cows = 1 cow, so cows can disappear in a puff of smoke. This seems unlikely. However, there is no guarantee that the mathematics of whole numbers actually matches the physics of cows, and it is at least conceivable that a cow might suddenly disappear. (In quantum mechanics, this could happen, but with a very low probability.) There is a limit to the number of cows in a finite universe, but there is no limit to the size, of mathematical integers. So physical intuition could be misleading, and should be ignored.
323
TAMING THE INFINITE
THE Sil All m ■ i it: IC
David Hilbert graduated from the University of Königsberg in 1885 with a thesis on invariant theory. He was on the university's staff until taking up a professorship at Göttingen in 1895. He continued to work in invariant theory, proving his finite basis theorem in 1888. His methods were more abstract than the prevailing fashion, and one of the leading figures in the field, Paul Gordan, found the work unsatisfactory. Hilbert revised his paper for publication in IheAnnalen, and Klein called it 'the most important work on general algebra that [the journal] has ever published.'
In 1893 Hilbert began a comprehensive report on number theory, the Zahlbericht. Although this was intended to summarize the known state of the theory, Hilbert included a mass of original material, the basis of what we now call class field theory.
By 1899 he had changed fields again, now studying the axiomatic foundations of Euclidean geometry. In 1900, at the Second International Congress of Mathematicians in Paris, he presented a list of 23 major unsolved problems. These Hilbert problems had a tremendous effect on the subsequent direction of mathematical research.
Around 1909 his work on integral equations led to the formulation of Hilbert spaces, now basic to quantum mechanics, He also came very close to discovering Einstein's equations for general relativity in a 1915 paper. He added a note in proof to the effect that the paper was consistent with Einstein's equations, which gave rise to an erroneous belief that Hilbert might have anticipated Einstein.
In 1930, on his retirement, Hilbert was made an honorary citizen of Königsberg. His acceptance speech ended with the words 'Wir müssen wissen, wir werden wissen' (we must know, we shall know) which encapsulated his belief in the power of mathematics and his determination to solve even the most difficult problems.
Hilbert came to this point of view in his work on the axiom, il li basis of Euclid's geometry. He discovered logical flaws in Euclid'1, axiom system, and realized that these flaws had arisen because Euclid had been misled by his visual imagery. Because he knew that a line was a long thin object, a circle was round and a point was a dot, he had inadvertently assumed certain properties of these objects, without stating them as axioms. After several attempts, Hilbert put forward a list of 21 axioms and discussed their role in Euclidean geometry in his 1899 Grundlagen der Geometrie (Foundations of Geometry).
Hilbert maintained that a logical deduction must be valid, independently of the interpretation imposed on it. Anything that relies on some particular interpretation of the axioms, but fails in other interpretations, involves a logical error. It is this view of axiomatics, rather than the specific application to geometry, that is Hilbert's most important influence on the foundations of mathematics. In fact, the same point of view also influenced the content of mathematics, by making it much easier - and more respectable - to invent new concepts by listing axioms for them. Much of the abstraction of early 20th century mathematics stemmed from Hilbert's viewpoint.
It is often said that Hilbert advocated the idea that mathematics is a meaningless game played with symbols, but this overstates his position. His point was that in order to place the subject on a firm logical basis, you have to think about it as if it is a meaningless game played with symbols. All else is irrelevant to the logical structure. But no one who takes a serious look at Hilbert's mathematical discoveries, and his deep commitment to the subject, can reasonably deduce that he thought he was playing a meaningless game.
After his success in geometry, Hilbert now set his sights on a far more ambitious project: to place the whole of mathematics on a sound logical footing. He followed the work of the leading logicians closely, and developed an explicit programme to sort out the foundations of mathematics once and for all. As well as proving that
324
325
TAMING THE INFINITE
THE SHAPE OF LOGIC
mathematics was free of contradictions, he also believed that in principle every problem could be solved — every mathematical statement could either be proved or disproved. A number of early successes convinced him that he was heading along the correct path, and that success was not far away.
IMM
There was one logician, however, who remained unconvinced by Hilbert's proposal to prove that mathematics is logically consistent. His name was Kurt Godel, and his worries about Hilbert's programme forever changed our view of mathematical truth.
Before Godel, mathematics was simply though to be true - and. it was the highest example of truth, because the truth of a statement like 2 + 2 = 4 was something in the realm of pure thought, independent of our physical world. Mathematical truths were not
What logic did for them
Charles Lutwidge Oodgson, better known as Lewis Carroll, used his own formulation of a branch of mathematical logic, now known as . prepositional calculus, to set and solve logical puzzles. Atypical example from his Symbolic Logic of 1896 is:.
• Nobody, who really appreciates Beethoven, fails to keep silence while the Moonlight Sonata is being played;
• Guinea-pigs are hopelessly ignorant of music;
• No one, who is hopelessly ignorant of music, ever keeps silence while the Moonlight Sonata is being played.
The deduction is that no guinea-pig really appreciates Beethoven. This form of logical argument is called a syllogism, and it goes back to classical Greece.
326
things that might be disproved by later experiments. In this they were superior to physical truths, such as Newton's inverse square law of gravity, which was disproved by observations of the motion of the perihelion of Mercury, supporting the new gravitational theory suggested by Einstein.
After Godel, mathematical truth turned out to be an illusion. What existed were mathematical proofs, the internal logic of which might well be faultless, but which existed in a wider context -foundational mathematics - where there could be no guarantee diat the entire game had any meaning at all. Godel did not just assert this: he proved it. In fact, he did two things, which together left Hilbert's careful, optimistic programme in ruins.
Godel proved that if mathematics is logically consistent, then it is impossible to prove that. Not just that he could not find a proof, but that no proof exists. So, remarkably, if you do succeed in proving that mathematics is consistent, it immediately follows that it's not. He also proved that some mathematical statements can neither be proved nor disproved. Again, not just that he personally could not achieve this, but that it is impossible. Statements of this type are called undecidable.
He proved these statements initially within a particular logical formulation of mathematics, that adopted by Russell and Whitehead in their Principia Mathemotica.To begin with, Hilbert thought that there might be a way out: find a better foundation. But as the logicians studied Godel's work, it quickly became apparent that the same ideas would work in any logical formulation of mathematics strong enough to express the basic concepts of arithmetic.
An intriguing consequence of Godel's discoveries is that any axiomatic system for mathematics must be incomplete: you can never write down a finite list of axioms that will determine all true and false theorems uniquely. There was no escape: Hilbert's programme cannot work. It is said that when Hilbert first heard of Godel's work he was extremely angry. His anger may well have been
327
IAMINK IHL INFINITE
THE SHAPE OF LOGIC
I n 1923, when Godel went to the University of Vienna, he was I still unsure whether to study mathematics or physics. His decision was influenced by lectures of a severely disabled mathematician, Philipp Furtwangler (brother of the famous conductor and composer Wilhelm). Godel's own health was fragile, and Furtwangler's will to overcome his disabilities made a big impression. In a seminar given by Moritz Schlick, Godel began studying Russell's Introduction to Mathematical Philosophy, and it became clear that his future lay in mathematical logic.
His doctoral thesis of 1929 proved that one restricted logical system, first-order propositional calculus, is complete - every true theorem can be proved and every faise one can be disproved. He is best known for his proof of 'Godel's Incompleteness Theorems'. In 1931 Godel published his epic paper Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systems. In it, he proved that no system of axioms rich enough to formalize mathematics can be logically complete. In 1931 he discussed his work with the logician Ernst Zermelo, but the meeting fared badly, possibly because Zermelo had already made similar discoveries but had failed to publish them,
In 1936 Schlick was murdered by a Nazi student, and Godel had a mental breakdown (his second). When he had recovered, he visited Princeton. In 1938 he married Adele Porkert, against his mother's wishes, and returned to Princeton, shortly after Austria had been incorporated into Germany. When the Second World War started, he was worried that he might be called up into the German Army, so he emigrated to the USA, travelling through Russia and Japan. In 1940 he produced a second
seminal work, a proof that Cantor's continuum hypothesis is consistent with the usual axioms for mathematics.
He became a US citizen in 1948, and spent the rest of his life in Princeton. Towards the end of his life he worried more and more about his health, and eventually became convinced that someone was trying to poison him. He refused food, and died in hospital. To the end, he liked to argue philosophy with his visitors.
328
directed at himself, because the basic idea in Godel's work is straightforward. (The technical implementation of that idea is distinctly difficult, but Hubert was good with technicalities.) Hilbert probably realized that he should have seen Godel's theorems coming.
Russell demolished Frege's book with a logical paradox, the paradox of the village barber who shaves everyone who does not shave himself: the set of all sets that are not members of themselves. Godel demolished Hilbert's programme with another logical paradox, the paradox of someone who says: this statement is a lie. For in effect Godel's undecidable statement - on which all else rests - is a theorem T that states: 'this theorem cannot be proved'.
If every theorem can either be proved, or disproved, then Godel's statement T is contradictory in both cases. Suppose T can be proved: then T states that T cannot be proved, a contradiction. On the other hand, if T can be disproved, then the statement T is false, so it is wrong to state that T cannot be proved. Therefore T can be proved, another contradiction. So the assumption that every theorem can either be proved or disproved tells us that T can be proved if and
only if it cannot be proved.
■
Wmti ■ m m> urns?
Godel's theorems changed the way we view the logical foundations of mathematics. They imply that currently unsolved problems may
329
TAMING THE INFINITE
have no solution at all -neither true nor false, but in the limbo of undecidability. And many interesting problems have been shown to be undecidable. However, the effect of Godel's work has not, in practice, extended much beyond the foundational area where it took place. Rightly or wrongly, mathematicians working on the Poincare conjecture, or the Riemann hypothesis, spend their time either looking for proofs or disproofs. They are aware that the problem may be undecidable, and might even look for a proof of undecidability if they could see how to get started. But most known undecidable problems have a self-referential feel to them, and without that, a proof of undecidability seems unattainable anyway.
As mathematics built ever more complicated theories on top of earlier ones, the superstructure of mathematics began to come to pieces because of unrecognized assumptions that turned out to be false. In order to shore up the entire edifice, serious work was needed on the foundations.
The subsequent investigations delved into the true nature of numbers, working backwards from complex numbers to reals, to rationals and then to whole numbers. But the process did not stop there. Instead, the number systems themselves were reinterpreted in terms of even simpler ingredients, sets.
Set theory led to major advances, including a sensible, though unorthodox, system of infinite numbers. It also revealed some fundamental paradoxes related to the notion of a set. The resolution of these paradoxes was not, as Hilbert hoped, a complete vindication of axiomatic mathematics, and a proof of its logical consistency. Instead, it was a proof that mathematics has inherent limitations, and that some problems do not have solutions. Tire upshot was a profound change in the way we think about mathematical truth and certainty. It is better to be aware of our limitations than to live in a fool's paradise.
330
THE SHAPE OF LOGIC
What logic does for us
A profound variant on Godel's incompleteness theorem was discovered by Alan Turing in an analysis of which computations are feasible, published in 1936 as On Computable Numbers, with an application to the Entscheidungsproblem (The decision problem). Turing began by formalizing an algorithmic computation - one that follows a pre-stated recipe - in terms of a so-called Turing machine. This is a mathematical idealization of a device which writes symbols 0 and 1 on a moving tape according to specific rules. He proved that the halting problem for Turing machines - does the computation eventually stop for a given input? - is undecidable. This means that there is no algorithm that can predict whether the computation halts or not.
Turing proved his result by assuming the halting problem to be decidable and constructing a computation that halts if and only if it does not hart, a contradiction. His result demonstrates that there are limits to computability. Some philosophers have extended these ideas to determine limits on rational thinking, and it has been suggested that a conscious mind cannot function algorithmically. However, the arguments here are currently inconclusive. They do show that it is naive to think that a brain works much like a modern computer, but this may not imply that a computer cannot simulate a brain.
331