[PDF] MATHEMATICS Algebra, geometry, combinatorics

6180_6Chapter7new.pdf

MATHEMATICS

Algebra, geometry, combinatorics

Dr Mark V Lawson

October 24, 2014

ii

Contents

1 The nature of mathematics 1

1.1 What are algebra, geometry and combinatorics? . . . . . . . .

1

1.1.1 Algebra . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1.2 Geometry . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.3 Combinatorics . . . . . . . . . . . . . . . . . . . . . . .

7

1.2 The scope of mathematics . . . . . . . . . . . . . . . . . . . .

8

1.3 Pure versus applied mathematics . . . . . . . . . . . . . . . .

9

1.4 The antiquity of mathematics . . . . . . . . . . . . . . . . . .

11

1.5 The modernity of mathematics . . . . . . . . . . . . . . . . .

12

1.6 The legacy of the Greeks . . . . . . . . . . . . . . . . . . . . .

14

1.7 The legacy of the Romans . . . . . . . . . . . . . . . . . . . .

15

1.8 What they didn't tell you in school . . . . . . . . . . . . . . .

15

1.9 Further reading and links . . . . . . . . . . . . . . . . . . . . .

16

2 Proofs 19

2.1 How do we know what we think is true is true? . . . . . . . .

20

2.2 Three fundamental assumptions of logic . . . . . . . . . . . .

22

2.3 Examples of proofs . . . . . . . . . . . . . . . . . . . . . . . .

23

2.3.1 Proof 1 . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.3.2 Proof 2 . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2.3.3 Proof 3 . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.3.4 Proof 4 . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

2.3.5 Proof 5 . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

2.4 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

2.5 Mathematics and the real world . . . . . . . . . . . . . . . . .

41

2.6 Proving something false . . . . . . . . . . . . . . . . . . . . .

41

2.7 Key points . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

2.8 Mathematical creativity . . . . . . . . . . . . . . . . . . . . .

43
i iiCONTENTS

2.9 Set theory: the language of mathematics . . . . . . . . . . . .

43

2.10 Proof by induction . . . . . . . . . . . . . . . . . . . . . . . .

52

3 High-school algebra revisited 57

3.1 The rules of the game . . . . . . . . . . . . . . . . . . . . . . .

57

3.1.1 The axioms . . . . . . . . . . . . . . . . . . . . . . . .

57

3.1.2 Indices . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

3.1.3 Sigma notation . . . . . . . . . . . . . . . . . . . . . .

66

3.1.4 Innite sums . . . . . . . . . . . . . . . . . . . . . . .

68

3.2 Solving quadratic equations . . . . . . . . . . . . . . . . . . .

70

3.3 Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

3.4 The real numbers . . . . . . . . . . . . . . . . . . . . . . . . .

77

4 Number theory 81

4.1 The remainder theorem . . . . . . . . . . . . . . . . . . . . . .

81

4.2 Greatest common divisors . . . . . . . . . . . . . . . . . . . .

91

4.3 The fundamental theorem of arithmetic . . . . . . . . . . . . .

97

4.4 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . .

108

4.4.1 Congruences . . . . . . . . . . . . . . . . . . . . . . . .

109

4.4.2 Wilson's theorem . . . . . . . . . . . . . . . . . . . . .

112

4.5 Continued fractions . . . . . . . . . . . . . . . . . . . . . . . .

113

4.5.1 Fractions of fractions . . . . . . . . . . . . . . . . . . .

113

4.5.2 Rabbits and pentagons . . . . . . . . . . . . . . . . . .

116

5 Complex numbers 123

5.1 Complex number arithmetic . . . . . . . . . . . . . . . . . . .

123

5.2 The fundamental theorem of algebra . . . . . . . . . . . . . .

131

5.2.1 The remainder theorem . . . . . . . . . . . . . . . . . .

132

5.2.2 Roots of polynomials . . . . . . . . . . . . . . . . . . .

134

5.2.3 The fundamental theorem of algebra . . . . . . . . . .

136

5.3 Complex number geometry . . . . . . . . . . . . . . . . . . . .

141

5.3.1 sin and cos . . . . . . . . . . . . . . . . . . . . . . . .

141

5.3.2 The complex plane . . . . . . . . . . . . . . . . . . . .

141

5.3.3 Arbitrary roots of complex numbers . . . . . . . . . . .

145

5.3.4 Euler's formula . . . . . . . . . . . . . . . . . . . . . .

148

5.4 Making sense of complex numbers . . . . . . . . . . . . . . . .

150

5.5 Radical solutions . . . . . . . . . . . . . . . . . . . . . . . . .

151

5.5.1 Cubic equations . . . . . . . . . . . . . . . . . . . . . .

151

CONTENTSiii

5.5.2 Quartic equations . . . . . . . . . . . . . . . . . . . . .

154

5.5.3 Symmetries and particles . . . . . . . . . . . . . . . . .

156

5.6 Gaussian integers and factorizing primes . . . . . . . . . . . .

157

6 Rational functions 159

6.1 Numerical partial fractions . . . . . . . . . . . . . . . . . . . .

159

6.2 Analogies . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

162

6.3 Partial fractions . . . . . . . . . . . . . . . . . . . . . . . . . .

163

6.4 Integrating rational functions . . . . . . . . . . . . . . . . . .

167

7 Matrices I: linear equations 171

7.1 Matrix arithmetic . . . . . . . . . . . . . . . . . . . . . . . . .

171

7.1.1 Basic matrix denitions . . . . . . . . . . . . . . . . .

171

7.1.2 Addition, subtraction, scalar multiplication and the

transpose . . . . . . . . . . . . . . . . . . . . . . . . . 173

7.1.3 Matrix multiplication . . . . . . . . . . . . . . . . . . .

175

7.1.4 Special matrices . . . . . . . . . . . . . . . . . . . . . .

179

7.1.5 Linear equations . . . . . . . . . . . . . . . . . . . . .

181

7.1.6 Conics and quadrics . . . . . . . . . . . . . . . . . . .

182

7.1.7 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . .

183

7.2 Matrix algebra . . . . . . . . . . . . . . . . . . . . . . . . . .

186

7.2.1 Properties of matrix addition . . . . . . . . . . . . . .

186

7.2.2 Properties of matrix multiplication . . . . . . . . . . .

187

7.2.3 Properties of scalar multiplication . . . . . . . . . . . .

188

7.2.4 Properties of the transpose . . . . . . . . . . . . . . . .

189

7.2.5 Some proofs . . . . . . . . . . . . . . . . . . . . . . . .

189

7.3 Solving systems of linear equations . . . . . . . . . . . . . . .

195

7.3.1 Some theory . . . . . . . . . . . . . . . . . . . . . . . .

196

7.3.2 Gaussian elimination . . . . . . . . . . . . . . . . . . .

1 98

7.4 Blankinship's algorithm . . . . . . . . . . . . . . . . . . . . .

206

8 Matrices II: inverses 209

8.1 What is an inverse? . . . . . . . . . . . . . . . . . . . . . . . .

209

8.2 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . .

213

8.3 When is a matrix invertible? . . . . . . . . . . . . . . . . . . .

217

8.4 Computing inverses . . . . . . . . . . . . . . . . . . . . . . . .

223

8.5 The Cayley-Hamilton theorem . . . . . . . . . . . . . . . . . .

227

8.6 Complex numbers via matrices . . . . . . . . . . . . . . . . . .

230
ivCONTENTS

9 Vectors 231

9.1 Vector algebra . . . . . . . . . . . . . . . . . . . . . . . . . . .

232

9.1.1 Addition and scalar multiplication of vectors . . . . . .

232

9.1.2 Inner, scalar or dot products . . . . . . . . . . . . . . .

238

9.1.3 Vector or cross products . . . . . . . . . . . . . . . . .

240

9.1.4 Scalar triple products . . . . . . . . . . . . . . . . . . .

243

9.2 Vector arithmetic . . . . . . . . . . . . . . . . . . . . . . . . .

245

9.2.1i's,j's andk's . . . . . . . . . . . . . . . . . . . . . . .245

9.3 Geometry with vectors . . . . . . . . . . . . . . . . . . . . . .

249

9.3.1 Position vectors . . . . . . . . . . . . . . . . . . . . . .

249

9.3.2 Linear combinations . . . . . . . . . . . . . . . . . . .

250

9.3.3 Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . .

251

9.3.4 Planes . . . . . . . . . . . . . . . . . . . . . . . . . . .

255

9.3.5 Determinants . . . . . . . . . . . . . . . . . . . . . . .

258

9.4 Summary of vectors . . . . . . . . . . . . . . . . . . . . . . . .

263

9.5 *Two vector proofs* . . . . . . . . . . . . . . . . . . . . . . .

266

9.6 Quaternions . . . . . . . . . . . . . . . . . . . . . . . . . . . .

268

Chapter 1

The nature of mathematics

This chapter is a guide to the mathematics described in this book.

1.1 What are algebra, geometry and combi-

natorics?

1.1.1 Algebra

Algebra started as the study of equations. The simplest kinds of equations are ones like

3x1 = 0

where there is only one unknownxand that unknown occurs to the power

1. This means we havexalone and not, say,x1000. It is easy to solve this

specic equation. Add 1 to both sides to get 3x= 1 and then divide both sides by 3 to get x=13 : This is the solution to my original equation and, to make sure, wecheckour answer by calculating 3
13 1 1

2CHAPTER 1. THE NATURE OF MATHEMATICS

and observing that we really do get 0 as required. Even this simple example raises an important point: to carry out these calculations, I had to know whatrulesthe numbers and symbols obeyed. You probably applied these rules unconsciously, but in this book it will be important to know explicitly what they are. The method used for the specic example above can be applied to any equation of the form ax+b= 0 as long asa6= 0. Herea;bare specic numbers, probably real numbers, and xis the real number I am trying to nd. This equation is the most general example of alinear equation in one unknown.

Ifxoccurs to the power 2 then we get

ax

2+bx+c= 0

wherea6= 0. This is an example of aquadratic equation in one unknown. You will have learnt a formula to solve such equations. But there is no reason to stop at 2. Ifxoccurs to the power 3 we get acubic equation in one unknown ax

3+bx2+cx+d= 0

wherea6= 0. Solving such equations is much harder than solving quadratics but there is also an algebraic formula for the roots. But there is no reason to stop at cubics. We could look at equations in whichxoccurs to the power 4, quartics, and once again there is a formula for nding the roots. The highest power ofxthat occurs in such an equation is called itsdegree. These results might lead you to expect that there are always algebraic formulae for nding the roots of any polynomial equation whatever its degree. There aren't. For equations of degree 5, thequintics, and more, there are no algebraic formulae which enable you to solve the equations. I don't mean that no formulae have yet been discovered, I mean that someone has proved that such a formula is impossible, that someone being the young French mathematician Evariste Galois (1811{1832), the James Dean of mathematics. Galois's work meant the end of the view that algebra was about nding formulae to solve equations. We shall not study Galois's work in this book but it has had a huge impact on algebra. It is one of the reasons why the algebra you study later in your university careers will look very dierent from the algebra you studied at school. In fact, one of my goals in writing this book is to help you navigate this transition.

1.1. WHAT ARE ALGEBRA, GEOMETRY AND COMBINATORICS?3

I have talked about solving equations where there is one unknown but there is no reason to stop there. We can also study equations where there are any nite number of unknowns and those unknowns occur to any powers. The best place to start is where we have any number of unknowns but each unknown can occur only to the rst power and no products of unknowns are allowed. This means we are studyinglinear equationslike x+ 2y+ 3z= 4: Our goal is to nd all the values ofx,yandzthat satisfy this equation. Thus the solutions are ordered triples (x;y;z). For example, both (0;2;0) and (2;1;0) are solutions whereas (1;1;1) is not a solution. It is unusual to have just one linear equation to solve. Usually we have two or more such as x+ 2y+ 3z= 4 andx+y+z= 0: We then need to ndallthe triples (x;y;z) that satisfybothequations simultaneously. In fact, as you should check, all the triples (4;42;) whereis any number satisfy both equations. For this reason, we often speak aboutsimultaneous linear equations. It turns out that solving systems of linear equations never becomes dicult however many unknowns there are. The modern way of studying systems of linear equations uses matrix theory. That leaves studying equations where there are at least 2 unknowns and where there are no constraints on the powers of the unknowns and the extent to which they may be multiplied together. This is much more complicated. If you only allow squares such asx2or products of at most two unknowns, such asxy, then there are relatively simple methods for solving them. But, even here, strange things happen. For example, the solutions to x

2+y2= 1

can be written (x;y) = (sin;cos). If you allow cubes or products of more than two unknowns then you enter the world of subjects like algebraic ge- ometry and even connect with current research. In this book, I shall introduce you to the theory of polynomial equations and also to the theory of linear equations. I shall also show you how to solve equations that look like this ax

2+bxy+cy2+dx+ey+f= 0:

4CHAPTER 1. THE NATURE OF MATHEMATICS

So far, I have been talking about the algebra of numbers. But I shall also introduce you to the algebra of matrices, and the algebra of vectors, and the algebra of subsets of a set, amongst others. In fact, I think the rst shock on encountering university mathematics can be summed up in the following statement. There is not one algebra, but many dierent algebras, each de- signed for dierent purposes. These dierent algebras are governed by dierent sets of rules. For this reason, it becomes crucial in university mathematics to make those rules explicit. In this book, the algebra you studied at school I often callhigh- school algebraso we know what we are talking about. In my description of solving equations, I have left to one side something that probably seemed obvious: the nature of the solutions. These solutions are of course numbers but what do we mean by `numbers'? You might think that a number is a number but in mathematics this concept turns out to be much more interesting than it might rst appear. The everyday idea of a number is essentially that of a real number. Informally, these are the numbers that can be expressed as positive or negative decimals, with possibly an innite number of digits after the decimal place such as = 3
14159265358::: where the dots indicate that this can be continued forever. Whilst such numbers are sucient to solve linear equations in one unknown, they are not enough to solve quadratics, cubics, quartics etc. These require the in- troduction of complex numbers which involve such apparent ineabilities as the square root of minus one. Because such numbers don't occur in everyday life, there is a temptation to view them as somehow articial or of purely theoretical interest. This is wrong with a capital w. All numbers are arti- cial, in that they are artefacts of our imaginations that help us to understand the world. Although you can see examples of two things you cannot see the number two. It is an idea, an abstraction. As for being of only theoretical interest, it is worth noting that quantum mechanics, the theory that explains the behaviour of atoms and their constituents, uses complex numbers in an essential way. In fact, for mathematicians the word `number' usually means `complex number' and mathematics is unthinkable without them.

1.1. WHAT ARE ALGEBRA, GEOMETRY AND COMBINATORICS?5

But this is not the end of our excavations of what we mean by the word `number'. There are occasions when we want to restrict the solutions: we might want whole number solutions or solutions as fractions. It turns out that the usual high-school methods for solving equations don't work in these cases. For example, consider the equation

2x+ 4y= 3:

To nd the real or complex solutions, we letxbe any real or complex value and then we can solve the equation to work out the corresponding value of y. But suppose that we are only interested in whole number solutions? In fact, there are none. You can see why by noting that the lefthand side of the equation is exactly divisible by 2, whereas the righthand side isn't. When we are interested in solving equations, of whatever type, by means of whole numbers or fractions we say that we are studyingDiophantine equations. The name comes from Diophantus of Alexandria who ourished around 250 CE, and who studied such equations in his bookArithmetica. It is ironic that solving Diophantine equations is often much harder than solving equations using real or complex numbers.

1.1.2 Geometry

If algebra is about manipulating symbols, then geometry is about pictures. The Ancient Greeks developed geometry to a very high level. Some of their achievements are recorded in Euclid's book theElementswhich I shall have more to say about later. It developed the whole of what became known as Euclidean geometryon the basis of a few rules known asaxioms. This geom- etry gives every impression of being a faithful mathematical version of the geometry of actual space and for that reason you might expect that, unlike algebra, there is only one geometry and that's that. In fact, it was discovered in the nineteenth century that there are other mathematical geometries such as spherical geometry and hyperbolic geometry. In the twentieth century, it became apparent that even the space we inhabit was much more complex than it appeared. First came the four dimensional geometry of special rela- tivity and then the curved space-time of general relativity. Modern particle physics suggests that there may be many more dimensions in real space than we can see. So, in fact, we have the following.

6CHAPTER 1. THE NATURE OF MATHEMATICS

There is not one geometry, but many dierent geometries, each designed for dierent purposes. In this book, I will only talk about three-dimensional Euclidean geometry, but this is the gateway to all these other geometries. This, however, is not the end of the story. In fact, any book about algebra must alsobe about geometry. The two are indivisible but it was not always like that. Unlike geometry which began with a sort of Big Bang in Ancient Greece, algebra crystallized much more slowly over time and in dierent places. There is even some algebra, disguised, in the Elements. In the 17th century, Rene Descartes discovered the rst connection between algebra and geometry which will be completely familiar to you. For example,x2+y2= 1 is analgebraicequation, but it also describes somethinggeometric: a circle of unit radius centred on the origin. This connection between algebra and geometry will play an important role in our study of linear equations and vectors. But it is just a beginning. If you are studying an algebra look for an accompanying geometry, and if you are studying a geometry nd a companion algebra. This is quite a fancy way of saying things, but it boils down to the fact that manipulating symbols is often helped by drawing pictures, and sometimes the pictures are to complex so it is helpful to replace them with symbols. It's not a one-way street. I want to give you some idea of why the connection between algebra and geometry is so signicant. Let me start with a problem that looks completely algebraic. Problem: nd all whole numbersa;b;cthat satisfy the equation a

2+b2=c2. I'll write solutions that satisfy this equation as (a;b;c). Such

numbers are calledPythagorean triples. Thus (0;0;0) is a solution and so is (3;4;5), and I can put in minus signs since when squared they disappear so (3;4;5) is a solution. In addition, if (a;b;c) is a solution so is (a;b;c) whereis any whole number. I shall now show that this problem is equivalent to one in geometry. Suppose rst thata2+b2=c2. We exclude the case wherec= 0 since thena= 0 andb= 0. We may therefore divide both sides byc2and get ac  2+bc  2 = 1:

1.1. WHAT ARE ALGEBRA, GEOMETRY AND COMBINATORICS?7

Recall that arational numberis a real number that can be written in the form uv whereuandvare whole numbers andv6= 0. It follows that (x;y) =ac ;bc  is arational pointon the unit circle; that is, a point with rational co-ordinates.

On the other hand, if

(x;y) =mn ;pq  is a rational point on the unit circle then (mq)2(nq)2+(np)2(nq)2= 1: Thus (mq;pn;nq) is a Pythagorean triple. We may therefore interpret our algebraic question as a geometric one: to nd all Pythagorean triples, nd all those points on the unit circle with centre the origin whosexandyco- ordinates are both rational. In fact, this can be used to get a very nice solution to the original algebraic problem as we shall show later.

1.1.3 Combinatorics

The term `combinatorics' may not be familiar though the sorts of questions it deals with are. Combinatorics is the branch of mathematics that deals with arrangements and the counting of arrangements. The fact that it deals in counting makes it sound like this should be an easy subject. In fact, it is often very dicult. For example, counting lies behind probability theory, a subject that can often defy intuition. Let me give you a simple example. In a class of, say, 25 students, how likely do you think it is that two students will share the same birthday? By this I mean, the same date and month, though not year. Unless you've seen this problem before, I think the instinct is to say `not very'. This is because we imagine in our mind's eye those 25 students to be arranged across 365 days without any pair of students landing on the same date. In fact the answer, which you can calculate using the methods of this book, is just over a half. In other words, there is the same chance of two students sharing the same birthday as there is of tossing a coin and getting heads. This little problem is often known as thebirthday paradox. It is a good example of where maths can be used to correct our faulty intuition. But

8CHAPTER 1. THE NATURE OF MATHEMATICS

this is really a counting problem. To get the right answers to such problems, you need to think about what you are counting in the right way.

1.2 The scope of mathematics

The most common replies to the question `what is mathematics?' addressed to a non-mathematician are usually the depressing `arithmetic' or `accoun- tancy'. Asked what they remember about school maths and they might be able to dredge up some more-or-less arcane words with challenging spellings: hypotenuse, isosceles, parallelogram. It either sounds a bit boring or a bit weird, but in any event is so obviously completely removed from real life that it can safely be ignored.

Mathematics, therefore, has an image problem.

I think part of the reason for this is the kind of maths that is taught in schools and the way it is taught. School mathematics suers by being based on the narrow syllabuses proscribed by examining boards under political direction. As a result, it is more by luck than design if anyone at school gets an idea of what maths is actually about. In addition, teaching too often means teaching to the exam, which means working through past exam papers and learning tricks 1. Let me begin by showing you just how vast a subject mathematics really is. The ocial Mathematics Subject Classication currently divides math- ematics into 64 broad areas in any one of which a mathematician could work their entire professional life. You can see what they are in the box. By the way, the missing numbers are deliberate and not because I cannot count.Mathematics Subject Classication 2010 (adapted)

00. General 01. History and biography 03. Mathematical logic

and foundations 05. Combinatorics 06. Order theory 08. Gen- eral algebraic systems 11. Number theory 12. Field theory 13. Commutative rings 14. Algebraic geometry 15. Linear and multi- linear algebra 16. Associative rings 17. Non-associative rings 18. Category theory 19. K-theory 20. Group theory and generaliza-1 I sayteachingand notteachers. My criticism is directed at policy not those who are forced to carry out that policy often under enormous pressures.

1.3. PURE VERSUS APPLIED MATHEMATICS9tions 22. Topological groups 26. Real functions 28. Measure

and integration 30. Complex functions 31. Potential theory 32. Several complex variables 33. Special functions 34. Ordinary dif- ferential equations 35. Partial dierential equations 37. Dynamical systems 39. Dierence equations 40. Sequences, series, summa- bility 41. Approximations and expansions 42. Harmonic analysis

43. Abstract harmonic analysis 44. Integral transforms 45. Integral

equations 46. Functional analysis 47. Operator theory 49. Calcu- lus of variations 51. Geometry 52. Convex geometry and discrete geometry 53. Dierential geometry 54. General topology 55. Algebraic topology 57. Manifolds 58. Global analysis 60. Proba- bility theory 62. Statistics 65. Numerical analysis 68. Computer science 70. Mechanics 74. Mechanics of deformable solids 76. Fluid mechanics 78. Optics 80. Classical thermodynamics 81. Quantum theory 82. Statistical mechanics 83. Relativity 85. As- tronomy and astrophysics 86. Geophysics 90. Operations research

91. Game theory 92. Biology 93. Systems theory 94. Information

and communication 97. Mathematics education Each of these broad areas is then subdivided into a large number of smaller areas, any one of which could be the subject of a PhD thesis. This is a little overwhelming, so to make it more manageable it can be summarized,very roughly, into the following ten areas:

Algebra Number theory

Calculus and analysis Probability and statistics

Combinatorics Dierential equations

Geometry and topology Mathematical physics

Logic Computing

Most undergraduate courses will t under one of these headings. But it is important to remember that mathematics is one subject | dividing it up into smaller areas is done for convenience only. When solving a problem any and all of the above areas might be needed.

1.3 Pure versus applied mathematics

Sometimes a distinction is drawn between pure and applied mathematics. Pure maths is supposed to be maths done for its own sake with no thought to

10CHAPTER 1. THE NATURE OF MATHEMATICS

applications, whereas applied maths is maths used to solve some, presumably practical, problem. I think there is often an implicit moralistic undertone to this distinction with pure maths being viewed as perhaps rather self-indulgent and decorative, and applied maths as socially responsible grown-up maths that pays its way. Politicians prefer applied maths because they think it will make money. Evidence for this distinction is the following quote from the English mathematician G. H. Hardy (1877{1947) that is often used to prove the point: \I have never done anything `useful'. No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least dierence to the amenity of the world." Hardy was a truly great mathematician and a decent human being. As his dates show, he was of the generation that witnessed the First World War where science and technology were applied to the business of wholesale slaughter. His views on maths are therefore a not unnatural reaction on the part of someone who taught young people who then went to war never to return. Maths for him was perhaps a sanctuary

2. In reality, the terms

pure and applied are extremely fuzzy. A mathematician might start work on solving a real-life problem and then be led to develop new pure mathematics, or start in pure maths and develop an application. Calculus, for example, developed mainly out of the need to solve problems in physics and then was applied to pure maths. Complex numbers couldn't have been more pure, introduced to provide the missing roots to polynomial equations, but are now the basis of quantum mechanics. In reality, there is just one mathematics.The Banach-Tarski Paradox The glory of mathematics is often to be found in its sheer weirdness. For a universe founded on logic, it can lead to some pretty confounding conclusions. For example, a solid the size of a pea may be cut into a nite number of pieces which may then be reassembled in such a way as to form another solid the size of the sun. This is known as the Banach- Tarski Paradox (1924). There's no trickery involved here and no sleight of hand. This is clearly pure maths | give me a real pea and whatever I do it will remain resolutely pea-sized | but the ideas it uses involve2 There was a similar reaction at the end of the Second World War amongst physicists who turned instead to biology as an alternative to building weapons.

1.4. THE ANTIQUITY OF MATHEMATICS11such fundamental and seemingly straightforward notions as length, area

and volume that have important applications in applied maths.

1.4 The antiquity of mathematics

The history of chemistry or astronomy is not hugely relevant, however inter- esting it may be, to modern theories of chemistry or astronomy. A few hun- dred years ago, chemistry was alchemy and astronomy was astrology: modern chemists are not searching for the philosopher's stone and astronomers don't caste horoscopes. Alchemists and astrologers are often the forbears they would prefer to forget.

3Maths is dierent, since what was mathematically

true hundreds of years ago remains true today. Here is a famous example. Plimpton 322 is a small clay tablet kept in the George A. Plimpton Collection at Columbia University dating to about 1,800 BCE. Impressed on the tablet are a number of columns of numbers written in cuneiform. The numbers are written not in base 10 but in base 60, the base that still lies behind the way we tell the time and measure angles. The meaning and purpose of this clay tablet is much disputed. But the second and third columns consist of the following numbers, where I have given the usual corrected numbers. I have given the rst seven lines of the table | there are fteen in the original.BC

1119169

233674825

346016649

41270918541

56597

6319481

722913541

If you calculateC2B2you will get a perfect squareD2. Thus (B;D;C) is a Pythagorean triple. How such large Pythagorean triples were computed is a mystery. This antiquity, combined with the fact that maths is a cumulative subject, meaning that you have to learnXbefore you can learnY, has the unfortunate3 I am exaggerating a little here for rhetorical purposes. In fact, much ne work was carried out under the guise of alchemy and astrology.

12CHAPTER 1. THE NATURE OF MATHEMATICS

eect that most of the mathematics you learnt at school was invented before

1800. Here is a very rough chronology.

BCECE

2000 Solving quadratics1550 Solving cubics and quartics

400 Existence of irrational numbers1590 Logarithms

300 Euclidean geometry1630 Analytic geometry

200 Conics1675 Calculus

1700 Probability

1795 Complex numbers

Only matrices (1850) and vectors (1880) were introduced more recently. How- ever, if you think of all the developments in physics since 1800 such as black holes, the big bang theory, parallel universes, quantum then you might sus- pect that there have also been big developments in mathematics. There have, but you would be forgiven for not knowing about them because they are not promoted in the media or taught in school. I should add that like any other eld of human endeavour, it is of course true that mathematical ideas go in and out of fashion, but crucially they don't become wrong with time.

1.5 The modernity of mathematics

The fact that what's taught in schools doesn't seem to change much from generation to generation leads to one of the biggest misconceptions about mathematics: that it has already all been discovered. To try and bring you up to date, I am going to say a little about three mathematicians and their work: Alan Turing (1912{1954), Sir Andrew Wiles (b. 1953), and Terence Tao (b. 1975). I have chosen them to illustrate some additional points I want to make about maths.

Alan Turing

Alan Turing is the only mathematician I know who has had a West End play written about his life: the 1986 playBreaking the codeby Hugh White- more. Turing is best known as one of the leading members of Bletchley Park during the Second World War, for his role in the British development of computers during and after the War, and for the ultimately tragic nature of

1.5. THE MODERNITY OF MATHEMATICS13

his early death. Here I want to return to Turing the mathematician. As a graduate student, he wrote a paper in 1936 entitledOn computable numbers with an application to the Entscheidungsproblem, where the long German word meansdecision problemand refers to a specic question in mathemat- ical logic. It was as a result of solving this problem that Turing was led to formulate a precise mathematical blueprint for a computer now calledTur- ing machinesin his honour. This is the most extreme example I know of a problem in pure maths leading to new applied maths | in fact, it led to the whole eld of computer science and the information age we now inhabit. Amongst computer scientists, Turing is regarded as the father of computer science. So, mathematicians invented the modern world.

Andrew Wiles

Mathematicians operate on a completely dierent timescale from everyone else. I have already talked about Pythagorean triples, those whole numbers (x;y;z) that satisfy the equationx2+y2=z2. Here's an idle thought. What happens if we try to nd whole number solutions tox3+y3=z3orx4+y4=z4 or more generallyxn+yn=znwheren3. Let's exclude the trivial case where some of the numbersx,yorzare 0. So, here is the question: forn3 nd all whole number solutions toxn+yn=znwherexyz6= 0. Back in the

17th century, Pierre de Fermat (1601?{1665) wrote in the margin of a book,

theArithmeticaof Diophantus, that he had found a proof thatthere were no such solutionsbut that sadly there wasn't enough room for him to record it. This became known asFermat's Last Theorem. In fact, since Fermat's supposed proof was never found, it was really a conjecture. More to the point, it is highly unlikely that he ever had a proof since in the subsequent centuries many attempts were made to prove this result, all in vain, although substantial progress was made. This problem became one of mathematics' many Mount Everests: the peak that everyone wanted to scale. Finally, on Monday 19th September, 1994, sitting at his desk, Andrew Wiles, building on over three centuries of work, and haunted by his premature announcement of his success the previous year, had a moment of inspiration as the following quote from theDaily Telegraphdated 3rd May 1997 reveals \Suddenly, totally unexpectedly, I had this incredible revelation. It was so indescribably beautiful, it was so simple and so elegant." As a result Fermat's Conjecture really is a theorem, but the proof required travelling through what can only be described as mathematical hyperspace.

14CHAPTER 1. THE NATURE OF MATHEMATICS

Wiles's reaction to his discovery is also a glimpse of the profound intellectual excitement that engages the emotions as well as the intellect when doing mathematics 4.

Terence Tao

Tao won the 2006 Field's medal. This is a mathematical honour compa- rable with a Nobel Prize though with the added twist that you have to be under 40 to get one. You can read his thoughts at his blog, as well as use it to nd all manner of interesting things. So, what sorts of things does he do? Here is one example that is remarkably easy to explain though the proof is formidable. You know what primes are and, in any event, we shall talk about them later. They can be regarded as the atoms of numbers and their prop- erties have inspired hard questions and deep results. One of the things that interests mathematicians is the sorts of patterns that can be found in primes. Anarithmetic progressionis a sequence of numbers of the forma+dkwhere aanddare xed numbers. Consider the arithmetic progression 3 + 2k. Ob- serve that for the consecutive values ofk= 0;1;2, the numbers 3;5;7 which arise are all prime. But whenk= 3 we get 9 which is not prime. Our little example is an instance of an arithmetic progression with 3 terms all prime. Here is one with 10 terms 199 + 210kwherek= 0;1;:::;9. In 2004, Tao and his colleague Ben Green proved that there were arithmetic progressions of arbitrary length all of whose terms are prime. In other words, for any numbernthere is an arithmetic progression so that the rstnterms are all prime.

1.6 The legacy of the Greeks

The word `mathematics' is Greek. In fact, many mathematical terms are Greek: lemma, theorem, hypotenuse, orthogonal, polygon, to name just a few. The Greek alphabet is used as a standard part of mathematical nota- tion. The very concept of a mathematical proof is a Greek idea. All of this re ects the fact that Ancient Greece is the single most important historical in uence on the development and content of mathematics. By Ancient Greek4 There is a BBC documentary directed by Simon Singh about Andrew Wiles made for the BBC's Horizon series. It is an exemplary example of how to portray complex mathematics in an accessible way and cannot be too highly recommend.

1.7. THE LEGACY OF THE ROMANS15

mathematics, I mean the mathematics developed in the wider Greek world around the Mediterranean in the thousand or more years between roughly

600 BCE and and 600 CE. It begins with the work of semi-mythical gures,

such as Thales of Miletus and Pythagoras of Samos, and is developed in the books of such mathematicians as Euclid, Archimedes, Apollonius of Perga, Diophantus and Pappus. Of all the Ancient Greek mathematicians the great- est was Archimedes. His work is sophisticated mathematics of the highest order. In particular, he developed methods that are close to those of integral calculus and used them to calculate areas and volumes of complicated curved shapes.

1.7 The legacy of the Romans

For all their aqueducts, roads, baths and maintenance of public order, it has been said of the Romans that their only contribution to mathematics was when Cicero rediscovered the grave of Archimedes and had it restored 5.

1.8 What they didn't tell you in school

This book is written to help you make the transition from school maths to university maths. You might well still be in school, or you might have left school fty years ago, it doesn't matter. Maths as taught in school and the maths taught at university are very dierent, but the failure to understand those dierences can cause problems. To be successful in university mathe- matics you have to think in new ways. University Mathematics is not just School Mathematics with harder sums and fancier notation, it is dierent, fundamentally dierent, from what you did at school. In much of school mathematics, you learn methods for solving spe- cic problems. Often, you just learn formulae. A method for solving a problem that requires little thought in its appli- cation is called analgorithm. Computer programs are the supreme examples of algorithms, and it is certainly true that nding algorithms for solving spe- cic problems is an important part of mathematics, but it is by no means the5 George Simmons,Calculus Gems, McGraw-Hill, Inc., New York, 1992, page 38.

16CHAPTER 1. THE NATURE OF MATHEMATICS

only part. Problems do not come neatly labelled with the methods needed for their solution. A new problem might be solvable using old methods or it might require you to adapt those methods. On the other hand, you may have to invent completely new methods to solve it. Such new methods re- quire new ideas. In fact, what you might not have appreciated from school mathematics is the important role played in mathematics byideas. An idea is a tool to help you think. Mathematics at school is often taught without reasons being given for why the methods work. This isthefundamental dierence between school mathematics and uni- versity mathematics. A reason why something works is called a proof. I shall say a lot more about proofs in Chapter 2.The Millennium Problems Mathematics is dicult but intellectually rewarding. Just how hard can be gauged by the following. The Millennium Problems is a list of seven outstanding problems posed by the Clay Institute in the year 2000. A correct solution to any one of them carries a one million dollar prize. To date, only one has been solved, the Poincare conjecture, by Grigori Perelman in 2010, who declined to take the prize money. The point is that no one oers a million dollars for something that is trivial. You can read more about these problems at http://www.claymath.org/millennium-problems

1.9 Further reading and links

There is a wealth of material about mathematics available on the Web and I would encourage exploration. Here, I will point out some books and links that develop the themes of this chapter. A book that is in tune with the goals of this chapter is P. Davis, R. Hersh, E. A. Marchisotto,The mathematical experience, Birkhauser, 2012.

1.9. FURTHER READING AND LINKS17

It's one of those books that you can dip into and you will learn something interesting but, most importantly, it will expand your understanding of what mathematics is, as it did mine. A good source book for the history of mathematics, and again something that can be dipped into, is C. B. Boyer, U. C. Merzbach,A history of mathematics, Jossey Bass, 3rd

Edition, 2011.

The books above are about maths rather than doing maths. Let me now turn to some books that do maths in a readable way. There is a plethora of popular maths books now available, and if you pick up any books byIan Stewart | though if the book appears to be rather more about volcanoes than is seemly in a maths book, you haveIainStewart | and Peter Higgins then you will nd something interesting. Sir (William) Timothy Gowers won a Field's Medal in 1998 and so can be assumed to know what he is talking about. T. Gowers,Mathematics: A Very Short Introduction, Oxford University

Press, 2002

It is worth checking out his homepage for some interesting links. He also has his own blog which is worth checking out. I think the Web is serving to humanize mathematicians: their ivory towers all have wi-. A classic book of this type is R. Courant, H. Robbins,What is mathematics, OUP, 1996. This is also an introduction to university-level maths, and it has in uenced my thinking on the subject. If you have never looked into Euclid's book theElements, then I would recommend you do

6. There is an online version that you can access via David

E. Joyce's website at Clark University. A handsome printed version, edited by Dana Densmore, has been published by Green Lion Press, Santa Fe, New

Mexico.6

Whenever I refer to Euclid, it will always be to this book. It consists of thirteen chapters, themselves called `books', which are numbered in the Roman fashion I{XIII.

18CHAPTER 1. THE NATURE OF MATHEMATICS

Finally, let me mention the books of Martin Gardner. For a quarter of a century, he wrote a monthly column on recreational mathematics for the Scientic Americanwhich inspired amateurs and professionals alike. I would start with

M. Gardner,Hexa

exagons, probability paradoxes, and the Tower of Hanoi: Martin Gardner's rst book of mathematical puzzles and games, CUP, 2002 and follow your interests.

Chapter 2

Proofs

Part of the argument sketch, Monty Python

M = Man looking for an argument

A = Arguer

M: An argument isn't just contradiction.

A: It can be.

M: No it can't. An argument is a connected series of statements intended to establish a proposition.

A: No it isn't.

M: Yes it is! It's not just contradiction.

A: Look, if I argue with you, I must take up a contrary position.

M: Yes, but that's not just saying `No it isn't.'

A: Yes it is!

M: No it isn't!

A: Yes it is!

M: Argument is an intellectual process. Contradiction is just the automatic gainsaying of any statement the other person makes. (short pause) A: No it isn't.The most fundamental dierence between school and university mathe- matics lies in proofs. At school, you were probably told mathematical facts and given recipes that solved particular kinds of problems. But the chances 19

20CHAPTER 2. PROOFS

are, you were not given any reasons to back up those facts or explanation as to why those recipes worked. University and professional mathematics is dierent. Reasons and explanations are essential and are called proofs. They are the essence of mathematics. Mathematical truth, and the notion of proof that supports it, is so dierent from what we encounter in everyday life that

I shall need to begin by setting the scene.

2.1 How do we know what we think is true is

true? Human beings usually believe something rst for emotional reasons, and then look for the evidence to back it up. The pitfalls of this are obvious. We shall therefore be interested in reasons that do not involve emotion. To be concrete, how would you verify the following claim: Mount Everest is between 8 and 9 km high?

The appeal to authority

In the past, claims such as this would be resolved by consulting an en- cyclopedia or atlas whereas today, of course, we would simply go online. If you do this, you will nd that a height of about 8.8 km is quoted. For most purposes this would settle things. But it's important to understand what this entails. We are, in eect, taking someone's word for it. Weassumethat whoever posted this information knows what they are talking about. What we are doing, therefore, is appealing to authority. Most of what we take to be true is based on such appeals to authority: parents, teachers, politicians, religiosi etc tell us things that they claim to be true and more often than not we believe them. There's a small element of laziness involved on our part, but it is so convenient. The pitfalls of this are also obvious.

The appeal to experiment

But where did the gure of 8.8km come from? It wasn't just plucked from the sky. The height of Mount Everest was rst measured as part of the great survey of India undertaken in the nineteenth century. This consisted of a team of expert surveyers who not only employed extremely precise instru- ments that were used to take multiple measurements but who also tried to

2.1. HOW DO WE KNOW WHAT WE THINK IS TRUE IS TRUE?21

minimize the eect of factors in uencing the accuracy of their measurements such as temperature and, amazingly, variations in gravity. Making measure- ments and taking great pains over those measurements together with esti- mations of the error bounds is such an important part of science that science itself would be impossible without it. Let's call this the appeal to experiment. This brings me to how we know statements are true in mathematics. The essential point is the following: Neither of the above methods for ascertaining truth plays any role whatsoever in determining mathematical truth. This is so important, I am going to say it again in a dierent way: Results are not true in maths because I say so or because someone important said they were true a long time ago. Results are not true in mathematics because I have carried out exper- iments and I always get the same answer. Results are not true in maths `just because they are'. How then can we determine whether something in mathematics is true? Results are true in mathsonlybecause they have beenprovedto be true. Aproofshows that a result is true. A proof is something thatyou yourselfcan follow and at the end you willseethe truth of what has been proved. A result that has been proved to be true is called atheorem. The appeal to authority and the appeal to experiment are both fallible. The appeal to proof is never fallible. The only truths we know for certain are mathematical truths. This is heady stu. So what, then, is a proof? The remainder of this chapter is devoted to an introductory answer to this question.

22CHAPTER 2. PROOFS

2.2 Three fundamental assumptions of logic

In order to understand how mathematical proofs work, there are three sim- ple, but fundamental, assumptions you have to understand. I. Mathematics only deals in statements that are capable of being either true or false. Mathematics does not deal in statements which are `sometimes true' or `mostly false'. There are no approximations to the truth in mathematics and no grey areas. Either a statement is true or a statement is false, though we might not know which. This is quite dierent from everyday life, where we often say things which contain a grain of truth or where we say things for rhetorical reasons which we don't entirely mean. Mathematics also doesn't deal in statements that are neither true nor false like exclamations such as `Out damned spot!' or with questions such as `To be or not to be?'. II. If a statement is true then its negation is false, and if a statement is false then its negation is true. In natural languages, negating a sentence is achieved in dierent ways. In English, the negation of `It is raining' is `It is not raining'. In French, the negation of `Il pleut' is obtained by wrapping the verb in `ne ...pas' to get `It ne pleut pas'. To avoid grammatical idiosyncracies, we can use the formal phrase `it is not the case that' and place it in front of any sentence to negate it. So, `It is not the case that it is raining' is the negation of `It is raining'. In some languages, and French is one of them, adding negatives is used for emphasis. This used to be the case in older forms of English and is often the case in informal English. In formal English, we are taught that two negatives make a positive which is actually the rule taken from mathematics above where it is true. In fact, negating negatives in natural languages is more complex than this. For example, if your partner says they are `not un- happy' then this isn't quite the same as being `happy' and maybe you need to talk.

III. Mathematics is free of contradictions.

2.3. EXAMPLES OF PROOFS23

Acontradictionis where both a statement and its negation are true. This is impossible by (II) above. This assumption will play a vital role in proofs as we shall see later.

2.3 Examples of proofs

Armed with the three assumptions above, I am going to take you through ve proofs of ve results, three of them being major theorems. This will enable me to show you examples of proofs but will also illustrate important issues about how proofs, and mathematics, work. Although proofs can be long or short, hard or easy they all tend to follow the same script. First, there will be a statement of what is going to be proved. This usually has the form: if a bunch of things are assumed true then something else is also true. If the things assumed true are lumped together asA, forassumptions, and the thing to be proved true is labelled C, forconclusion, then a statement to be proved usually has the shape `ifA thenC' or `AimpliesC' or, in notation, `A)C'. The proof itself should be thought of as a (rational) argument between two protagonists whom we shall callAliceandBob. We assume that Alice wants to proveC. She can use any of the assumptionsA, any previously proved theorems, the rules of logic, which I shall describe as we meet them, and denitions. Bob's role is to act like an attorney and to demand that Alice justify each claim she makes. Thus Alice cannot just make assertions without justifying them, and she is limited in the sorts of things that count as justications. At the end of this, Alice can say something like ` ...and soCis proved' and Bob will be forced to agree.

2.3.1 Proof 1

We shall prove the following statement.

The square of an even number is even, and the square of an odd number is odd. In fact, this is really two statements `Ifnis an even number thenn2is even' and `Ifnis an odd number thenn2is odd.' Before we can prove them, we

24CHAPTER 2. PROOFS

need to understand what they are actually saying. The termsoddandeven are only used of whole numbers such as

0;1;2;3;4;:::

These numbers are called thenatural numbersand they are the rst kinds of numbers we learn about as children. Thus we are being asked to prove a statement about natural numbers. The terms `odd' and `even' might seem obvious, but we need to be clear about how they are used in maths. By denition, a natural numbernisevenif it is exactly divisible by 2, otherwise it is said to beodd. In maths, we usually just saydivisiblerather thanexactly divisible. This denition of divisibility only makes sense when talking about whole numbers. For fractions, for example, it is pointless since one fraction will always divide another fraction. Notice that 0 is an even number because

0 = 20. In other words, 0 is exactly divisible by 2. However, remember,

you cannotdivide by0 but you can certainlydivide into0. You might have been told that a number is even if its last digit is one of the digits 0;2;4;6;8. In fact, this is a consequence of our denition rather than a denition itself. I shall ask you to prove this result in the exercises. I shall say no more about the denition of even. What about the denition of odd? A number isodd if it is not even. This is not a very useful denition since a number is odd if it fails to be even. We want a more positive characterization. So we shall describe a better one. If you attempt to divide a number by 2 then there are two possibilities: either it goes exactly, in which case the number is even, or it goes so many times plus a remainder of 1, in which case the number is odd. It follows that a better way of dening an odd numbernis one that can be writtenn= 2m+ 1 for some natural numberm. So, the even numbers are those natural numbers that are divisible by 2, thus the numbers of the form

2nfor somen, and the odd numbers are those that leave the remainder 1

when divided by 2, thus the numbers of the form 2n+ 1 for somen. Every number is either odd or even but not both. There is a moral to be drawn from what I have just done, and I shall state it boldly because of its importance. It may seem obvious but experi- ence shows that it is, in fact, not. Every time you are asked to prove a statement, you must ensure that you understand what that statement is saying. This means, in particular, checking that you understand what all the words in

2.3. EXAMPLES OF PROOFS25

the statement mean. The next point is that we are making a claim aboutalleven numbers. If you pick a few even numbers at random and square them then you will nd in every case that the result is even but this does not prove our claim. Even if you checked a trillion even numbers and squared them and the results were all even it wouldn't prove the claim. Maths, remember, is not an experimental science. There are plenty of examples in maths of statements that look true and are true for umpteen cases but are in fact bunkum. This means that, in eect, we have to prove an innite number of state- ments: 0

2is even, and 22is even, and 42is even ...I cannot therefore prove

my claim by picking a specic even number, like 12, and checking that its square is even. This simply veries one of the innitely many statements above. As a result, the starting point for my proof cannot be a specic even number. It has to be a general even number. We are now in a position to prove our claims. First, we prove that the square of an even number is even. 1. Le tnbe an even number. This is the assumption that gets the ball rolling. Notice thatnis not a specic even number. We want to prove something for all even numbers so we cannot argue with a specic one. 2. T henn= 2mfor some natural numberm. Here we are using the denition of what it means to be an even number. 3. S quareb othsides of the e quationin (2) to get n2= 4m2. To do this correctly, you need to follow the rules of high-school algebra. 4. No wrewrite this equation as n2= 2(2m2). This uses more basic high- school algebra. 5. S ince2 m2is a natural number, it follows thatn2is even using our denition of an even number. This proves our claim. Second, we prove that the square of an odd number is odd. I'll provide less commentary than in the previous case. 1.

Le tnbe an odd number.

2.

By denition n= 2m+ 1 for some natural numberm.

26CHAPTER 2. PROOFS

3. S quareb othsides of the equation i n(2) to ge tn2= 4m2+ 4m+ 1. 4. No wrewrite the equation in (3) as n2= 2(2m2+ 2m) + 1. 5. S ince2 m2+2mis a natural number, it follows thatn2is odd using our denition of an odd number. This proves our claim. We have therefore proved our two claims. I admit that they are not exciting but just bear with me.

2.3.2 Proof 2

We shall prove the following statement.

If the square of a number is even then that number is even, and if the square of a number is odd then that number is odd. In fact, this is really two statements `Ifn2is even thennis even' and `Ifn2 is odd thennis odd'. At rst reading, you might think that I am simply repeating what I proved above. But in Proof 1, I proved `ifnis even thenn2is even' whereas now I want to prove `ifn2is even thennis even'. Our assumptions in each case are dierent and our conclusions in each case are dierent. It is therefore important to distinguish betweenA)Band B)A. The statementB)Ais called theconverseof the statement A)B. Experience shows that people are prone to swapping assumptions and conclusions without being aware of it.

We prove the rst claim.

1.

S upposethat n2is even.

2. No wit is v erytempting to try and use the de nitionof ev enhere, just as we did in Proof 1, and writen2= 2mfor some natural numberm. But this turns out to be a dead-end. Just like playing a game such as chess, not every possible move is a good one. Choosing the right move comes with experience and sometimes just plain trial-and-error.

2.3. EXAMPLES OF PROOFS27

3. S ow emak ea dieren tmo ve.W ekno wthat nis either odd or even.

Our goal is to prove that it must be even.

4. C ouldnbe odd? The answer is no, because as we showed in Proof 1, ifnis odd then, as we showed above,n2is odd. 5.

T hereforenis not odd.

6. Bu ta n umberthat is not o ddm ustb eev en.It follo wsthat nis even. We use a similar strategy to prove the second claim. The proofs here were more subtle, and less direct, than in our rst ex- ample and they employed the following important strategy:if there are two possibilities exactly one of which is true; we rule out one of those possibilities and so deduce that the other possibility must be true. 1 Here is a concrete example. There are two politicians, Alice and Bob. One of them always lies and the other always tells the truth. Suppose you ask Bob the question: is it true that 2 + 2 = 5? If he replies `yes' then you know Bob is lying. Without further ado, you can deduce that Alice is that paragon of politicians and always tells the truth. IfA)BandB)Athen we say thatAif, and only, ifBorAiB orA,B. The use of the wordiis peculiar to mathematical English. If we combine Proofs 1 and 2, we have proved the following two statements for all natural numbersn: `nis even if, and only if,n2is even' and `nis odd if, and only if,n2is odd'. It is important to remember that the statement `Aif, and only, ifB' is in facttwostatements in one. It means (1)`AimpliesB'and(2)`Bimplies A'. So, to prove the statement`Aif and only ifB'we have to prove TWO statements: we have to prove`AimpliesB'and we have to prove`Bimplies A'. The results of this example were trickier to prove than the previous ones, but not much more exciting. However, we have now laid the foundations for a truly remarkable result.1 This might be called theSherlock Holmes method. \How often have I said to you that when you have eliminated the impossible, whatever remains, however improbable, must be the truth?" The Sign of Four, 1890.

28CHAPTER 2. PROOFS

2.3.3 Proof 3

We shall now prove our rst real theorem.

p2cannot be written as an exact fraction.

If you square each of the fractions in turn

32
;75 ;1712 ;4129 ;::: you will nd that you get closer and closer to 2 and so each of these numbers is an approximation to the square root of 2. This raises the question: is it possible to nd a fraction xy whose square isexactly 2?In fact, it isn't but that isn't proved just because my attempts above failed. Maybe, I just haven't looked hard enough. So, I have to prove that it is impossible. To prove thatp2 is not an exact fraction, I am actually going to begin by trying to show you that it is. 1.

S upposethat

p2 = xy wherexandyare positive whole numbers where y6= 0. 2.

W ema yassume that

xy is a fraction in its lowest terms so that the only natural number that divides bothxandyis 1. Keep your eye on this assumption because it will come back to sting us later. 3. S quareb othsides of the equation i n(2) to ge t2 = x2y 2. 4.

Mu ltiplyb othsides of the equation in (3) b yy2.

5.

W etherefore get the equation 2 y2=x2.

6. S ince2 divides the lefthan dsideof this equation, it m ustdivide the righthandside. This means thatx2is even. 7.

W eno wuse Pro of2 to deduce that xis even.

8. W ema ytherefore write x= 2ufor some natural numberu. 9. S ubstitutethis v aluefor xwe have found in (5) to get 2y2= 4u2. 10. D ivideb othsides of the equation in (9) b y2 to get y2= 2u2.

2.3. EXAMPLES OF PROOFS29

11. S incethe righ thand-sideof the equation in (10) is ev enso is the left- handside. Thusy2is even. 12. S incey2is even, it follows by Proof 2, thatyis even. 13. If (1) is true then w eare led to the follo wingt woc onclusions.F rom(2), we have thatthe only natural number to divide bothxandyis 1. From (7) and (12),2 divides bothxandy. This is a contradiction. Thus (1) cannot be true. Hencep2 cannot be written as an exact fraction. This result is phenomenal. It says that no matter how much money you

spend on a computer it will never be able to calculate the exact value ofp2, just a very, very good approximation. We now make a very important

denition. A real number that is not rational is calledirrational. We have therefore proved thatp2 is irrational.

2.3.4 Proof 4

We now prove our second real theorem.

The sum of the angles in a triangle add up to180. This is a famous result that everyone knows. You might have learnt about it at school by drawing lots of triangles and measuring their angles but as I said above, maths is not an experimental science and so this enterprize proves nothing. The proof I give is very old and occurs in Euclid's book the Elements: specically, Book I, Proposition 32. Draw a triangle and call its three angles,and respectively. 

Our goal is to prove that

++ = 180: In fact, we shall show that the three angles add up to a straight line which is the same thing. Draw a line through the pointPparallel to the base of the triangle.

30CHAPTER 2. PROOFS

P Then extend the two sides of the triangle that meet at the pointPas shown.  0 0

0As a result, we get three angles that I have called0,0and

0. I now make

the following claims 0=because the angles are opposite each other in a pair of inter- secting straight line. 0=because these two angles are formed from a straight line cutting two parallel lines.  0= for the same reason as above.

But since0and0and

0add up to give a straigh

Politique de confidentialité -Privacy policy