Lecture 4: Proof and Time

Introduction

1 In this lecture we are going to take a look at the foundations of mathematics. We are going to talk about proof. Since a proof has a number of steps, sometimes a very large number, this will lead us to think about time.

2 First recall where we finished last week:

Since human beings became conscious of themselves and began to record their thoughts in writing, we have seen our conception of the size of the universe gradually expand. From Aristotle to Copernicus to Newton to Einstein we have seen the universe grow to an unbounded spacetime at least 20 billion light years around, if that has any meaning.

What I now propose is not an expansion in physical size, but in something less tangible. For too long we have though of our universe, our planet and ourselves as second class or defective, in some way puppets who do not know who or what is pulling their strings. I claim that this is not so. This universe is it. In theological terms, it is god.

How do we understand god? The only constraint we put on god is that it be consistent. In time, we will see that this is no constraint at all.

If we allow non-constructive proofs, consistency is the only constraint acting on mathematics. This leads us to identify mathematics and the universe with the slogan the universe is mathematics incarnate.

... we have seen that Cantor's theorem must be true in a consistent universe. As I interpret it, Cantor's theorem tells us that there is no limit to the generation of new symbols from old. There is no limit to the creative power of a consistent universe.

Foundations

3 In this lecture I want to follow through the effects of Cantor's discovery.

4 In the process of laying the foundations of the theory of transfinite aggregates, Cantor developed the theory of aggregates, and greatly strengthened the foundations of arithmetic.

5 The foundations of arithmetic are what make it strong and reliable, invincible if you like. The superheroes of mathematics, the theorems, are considered to be more powerful than the superheroes in any other trade, even fighting. All our soldiers depend upon the same mathematics. If that same mathematics says there is a better way of fighting, we should listen.

6 I cannot emphasise this point too much. We are familiar with security of day to day manifestations of mathematics. The arithmetical operations of addition and multiplication and subtraction and division work perfectly, day after day in billion of locations around the globe. There are completely reliable patterns of behaviour in the universe. They are laws of nature.

7 Not only does mathematics deliver laws of nature, but it can show us how laws of nature come to be. That is, it can produce a consistent theory of its own creation.

8 The easiest way for me to explain this is to give you my version of the history of the last century of mathematics.

Cantor

9 Cantor came first. His theory of transfinite numbers, published in 1895, changed the face of mathematics. His method was the theory of aggregates.

10 He defined an aggregate as any collection into a whole of definite and separate objects of our intuition or our thought.

11 The first fundamental idea of the theory of aggregates is that the elements of the aggregate must be definite and separate objects. When Cantor first started his work, the elements he was concerned with were points in a line.

12 In the theory of aggregates he replaced the old mathematical definition of point with the new definition of element. What was something with position but no magnitude became a definite and separate object. At a stroke he broadened the compass of mathematics from points and lines to anything.

13 The elements of an aggregate are definite and separate objects, and if all is well the aggregate itself is a definite and separate object.

14 For a given aggregate, each definite thing in the universe is either in the aggregate or out of it. There is no halfway. If you cannot decide whether something is in an aggregate or not, then either the thing or the aggregate is not properly defined.

15 The second fundamental idea in the theory of aggregates is that of pairing things up. If you want to count sheep, you pair the sheep up one by one with the numbers, one sheep, two sheep, three sheep, and so on. When you have run out of sheep, the number you have come to is the number of sheep you have.

16 This pairing up is easily expressed by the theory of aggregates. Each pair is an aggregate formed by the two elements, say the number three and a particular sheep. Pairing is the same as the use of symbols to point to one another. The numbers point to the sheep. The sheep point to the numbers.

17 In the last lecture we used the word symbol to point to both these ideas. A symbol is a definite and separate object. Symbol also carries the idea of pairing, since it points to something else.

18 Cantor was able to use his theory of aggregates to explain, in a very obvious way, how addition and multiplication and all the other operations of simple arithmetic work.

19 Because his theory of aggregates was so solidly logical, he was able to leap from the ordinary counting numbers to the transfinite numbers. Having gained the high ground of transfinity, he was able to look back on the finite numbers and understand them more clearly than ever before.

Paradox

20 As we have seen however, Cantor's theory of aggregates also led to trouble. He found that his proof from consistency led to paradox, that is to inconsistency. Many people, notably Bertrand Russel and David Hilbert, attacked the paradox problem, and found that it was more difficult than they had anticipated.

21 There are many paradoxes besides Cantor's Paradox. Russel worked on the paradox problem for years. He once wrote:

It seemed unworthy of a grown man to spend time on such trivialities, but what was I to do? ... Every morning I would sit down before a blank sheet of paper. Throughout the day, with a brief interval for lunch, I would stare at the blank sheet. Often when evening came it was still empty. ... the two summers of 1903 and 1904 remain in my mind as a period of complete intellectual deadlock.

22 Meanwhile, mathematics was on the sideline. What was to be done if careful use of the notion of consistency led inevitably to inconsistency?

Formalism

23 While mathematics dealt with mundane things like counting and measuring, it seemed to form a natural part of the world. When Cantor introduced transfinite numbers, however, mathematics took on an entirely different complexion. To many, it appeared to have transcended the visible universe and taken on an existence of its own.

24 This new existence and the problems of consistency led David Hilbert to the formalist theory of mathematics. Hilbert said mathematics was not to be looked upon as a theory drawn from the visible world, but had a life of its own. It was like a game, played by manipulating a set of symbols according to a set of rules.

25 This formalist theory not only cleanly cut the problems in mathematics away from any real bearing on life in the real world; it also freed mathematics from its concern with mundane considerations like being useful or having anything to do with observed facts.

26 Hilbert's hope, using his formalist approach, was to locate the sources of paradox in mathematics and eliminate them. After many years, he was able to express his project in three questions.

27 First, he wanted to know, is mathematics consistent? In other words, is it free of paradox. He presumed that the answer would be yes, that no two lines of mathematical argument, starting from the same place, could reach contradictory conclusions.

28 Second, he wanted to know is mathematics complete? He presumed once again that the answer would be yes. In other words it would be possible to prove that every possible mathematical statement was either true or false. It would not be possible to come up with a legitimate mathematical statement which could not either be proved or disproved.

29 Hilbert's third question was is mathematics decidable? That is, given that a proof or disproof of every mathematical statement does exist, can we find that proof or disproof by a purely straightforward mechanical process, and so decide whether the statement is consistent or inconsistent?

Goedel

30 We are already familiar with Kurt Goedel's answer to the first and second questions. If mathematics is consistent, then it must be incomplete. Goedel proved that there exist statements for which no proof or disproof exists. In other words, if mathematics is consistent then we can prove that there must be statements which are impossible to prove.

31 This result came as a shock, but it also showed a way to deal with the paradox problem. Cantor's theorem is true. Goedel's incompleteness theorem is also true. Cantor's paradox depends upon the existence or non-existence of a greatest aggregate.

32 Goedel's theorem suggests that this question is out of the range provability. We simply cannot prove that there is a biggest aggregate, nor that there is not. Cantor's Paradox is avoided by locating it in an area of uncertainty. The aggregate of all aggregates is not a definite and separate object.

33 This uncertainty is not merely a matter of human ignorance. Goedel proved that an area of uncertainty must exist if mathematics is to be consistent.

Turing

34 Hilbert's third question was: if a proof or disproof exists for a given mathematical statement, can we ever find it by a mechanical process?

35 I don't think you can get through school without seeing a few mathematical proofs. Pythagoras' theorem is one of the most famous in the world and one of the oldest. What we want to do is prove that in a right angled triangle the square on the hypotenuse is equal to the sum of the squares on the other two sides.

36 I'm not going to give you the proof here, but you might be able to remember what it looks like. Basically, the proof comprises a series of logical steps each of which follows from one or more of the steps before it.

37 Gradually the proof builds a logical link between the different elements of the theorem. Finally, when the last logical link has been forged, the logical connections between all the parts of the statement become clear, and it becomes obvious that the theorem must be true.

38 The proof itself is a path to certainty. When I was at school a common question in a maths exam would be Prove Pythagoras' theorem. Usually I could write the theorem down. But finding the correct proof was not always so easy. It was easy to wander off into irrelevant bywaters or run up against logical inconsistencies.

39 The question that Hilbert asked was just the same as the exam question, but in a much broader context. Is it possible, Hilbert asked, to find proofs or disproofs of all possible mathematical statements by a mechanical process?

40 You can see that this was quite an impertinent question. What would happen to the mathematical community if it was proved that their exalted spiritual work could be done by a purely mechanical process?

41 Hilbert's third question was answered by Alan Turing. Turing's proof required two steps. First he had to construct something which would embody the concept of purely mechanical process.

42 The idea he came up with is a device called the Turing machine, which is the theoretical forerunner of the computer. The Turing machine is like a computer in that it can be programmed to do anything.

43 Turing was able to show that this machine is able to carry out any logical process whatever, and it operated by a purely mechanical process. Each step that a Turing machine takes is determined perfectly by its previous steps. It never has to guess or ask for outside help.

44 Having found something which performed the mechanical process, at least in theory, Turing then asked it Hilbert's question. This was done setting the machine up to find the proof of a given theorem then setting it in motion. It would chug along a step at a time looking for the proof. If it found a proof, it would stop, and it would keep on going until it did find one.

45 Turing did not build a Turing Machine. All his work was done on paper.

46 Turing thus translated Hilbert's question into a new question: can we guarantee that if we set up a Turing Machine to prove any possible mathematical statement it will eventually come to a halt.

47 Turing found that there were mathematical statements for which halting could not be guaranteed, Some mathematical statements require an infinite number of steps in a Turing machine to prove or disprove.

48 Even when the Turing machine does find a proof and come to a halt it requires some finite number of steps.

Time

49 We may think of each step of a Turing machine as a tick of time. The Turing machine is the mathematical prototype of the digital computer. In computers we have a part called the clock which calls out the steps and keeps all parts of the computer operating in synchronicity.

50 We often estimate how many clock cycles it will take a computer to solve a particular problem. Even for ordinary problems this may be millions of cycles. Modern electronic computers generally complete between a million and a billion operations every second, but there are plenty of calculation problems that are too big for them. For the whole Star Wars thing to work, we need some radical improvements in computer power.

51 We can identify each tick of the clock with a step of the Turing Machine. What Turing proved is that there are problems that are so big that an ideal computer will take an infinite time to solve them. He had answered Hilbert's third question in the negative, and given us the beginnings of a mathematical notion of time.

The theory

52 We now have the main mathematical ingredients of a theory of peace. I will list them for you briefly.

53 Cantor's theorem says that a consistent symbolic system, even an infinite one, will generate new transfinite symbols without limit.

54 Goedel's theorem tells us that every consistent structure is surrounded by a cloud of uncertainty.

55 Turing's theorem tells us that the discovery of consistent structures, that is proofs, among the symbols produced by Cantor's theorem will take a certain number of steps. This number may be infinite, meaning that there are proofs so long that they can never be completed.

56 Goedel tells us that some symbols are in principle unprovable. Turing tells us that some might be proved but it would take an infinitely long time to do it, and some can be proved in a finite time.

Interpretation

57 How can we fit this set of mathematical results onto the world of experience?

58 We divide our experience into past, present and future. The past is absolutely certain. Nothing will change what has actually happened, although we are always free to re-interpret the events of the past.

59 The future, because it contains the past, also has an element of certainty. In particular, we are confident that all the mathematical theorems that hold now will hold in the future. The passage of time makes no difference to a proof. It is eternal.

60 The future is also uncertain. Our lives can take gigantic swings in no time. One moment you may have just won the lottery and married the person of your dreams, only to find yourself moments later dying an agonising death under a bus.

61 I claim that the relationship between the certainty of the past and the mixture of certainty and uncertainty in the future arises from Goedel's theorem. This theorem, proved and therefore certain throughout all time, says that any island of certainty is surrounded by a sea of uncertainty.

62 We progress into the future by finding certain paths through this sea of uncertainty. Only those things can exist which are consistent, both within themselves and with all that exists before them. In other words possibilities in the future become realities in the present and the past by proving themselves to exist.

63 Turing showed that proof takes many steps. So it takes us time to sift through the possibilities of the future and decide what to do next.

64 The mathematical theory suggests that the possibilities of the future are transfinite with respect to the present. We can never explore them all, and so there are some possible structures we will never find. On the other hand we will soon learn that it is always possible to find consistent structure in the future. A consistent past cannot lead to a dead end in the future.

65 This means that we do not necessarily have to destroy the past to get to the future. In particular it is not necessary to kill people to sort out our human problems. This is our first glimpse of the possibility of peace. In the next lectures we will build on this foundation to determine more closely the conditions which guarantee peace.

Conclusion

66 We fight because there is not enough to go around. One approach to life is that it is only possible to get more by taking it from somebody else. This is often true, but it is not necessarily true.

67 Our universe in infinite and creative. What I hope to show is that is possible in principle to deploy our resources to make certain that the needs of every person are met. There will then be no need to use violence to deprive one another of the necessities of life.

68 Mathematics is the science of symbols. I have taken the view that everything in the universe is a symbol. Symbols have a duality. They are at once a thing and a space. Mathematically the problem of peace is the same as creating enough space for every thing to exist without having to take space from another.

69 We have now come from the assumption that the universe is consistent to the nation of time. Next we will see how space and time are related and then broaden that idea to see how we can, in time, create peaceful living space for everyone.

Originally broadcast on 2BOB Radio, Taree, NSW on 9 July 1987

Books

Click on an "Amazon" link in the booklist at the foot of the page to buy the book, see more details or search for similar items

Related sites:

Copyright: You may copy this material freely provided only that you quote fairly and provide a link (or reference) to your source.