ALICE IN NUMBERLAND Alice in Numberland A Students' Guide to the Enjoyment of Higher Mathematics John Baylis Rod Haggarty M MACMILLAN EDUCATION © John Baylis and Rod Haggarty 1988 AII rights reserved. No reproduction, copy or transmission of this publication may be made without written permission. No paragraph of this publication may be reproduced, copied or transmitted save with written permission or in accordance with the provisions of the Copyright Act 1956 (as amended), or under the terms of any licence permitting limited copying issued by the Copyright Licensing Agency, 7 Ridgmount Street, London WCIE 7AE. Any person who does any unauthorised act in relation to this publication may be liable to criminal prosecution and civil claims for damages. First published 1988 Published by MACMILLAN EDUCATION LTD Houndmills, Basingstoke, Hampshire RG21 2XS and London Companies and representatives throughout the world British Library Cataloguing in Publication Data Baylis, John Alice in numberland: a students' guide to the enjoyment of higher mathematics. l. Mathematics-1961- 1. Title Il. Haggarty, Rod 510 QA37.2 ISBN 978-0-333-44242-5 ISBN 978-1-349-09532-2 (eBook) DOI 10.1007/978-1-349-09532-2 To Daniel, Gwen, Siân and Sarah CONTENTS Introduction vii 1 Alicein Logiland-in which We meet Alice,Tweedledee and Tweedledum, and Logic 2 Unique factorisation-in which trivial arithmetic reveals a glimpse of hidden depths 14 3 Numbers-in which we abandon logic to achieve understanding, then use logic to deepen understanding 21 4 The real numbers-in which we find holes in the number line and pay the price for repairs 36 5 A variety of versions and uses of induction-in which another triviality plays the lead 52 6 Permutations-in which ALICE is transformed 72 7 Nests-in which the rationals give birth to the reals and the scene is set for arithmetic in IR 89 8 Axioms for IR-in which we invent Arithmetic, Order our numbers and Complete our description of the reals 98 9 Some infinite surprises-in which some wild sets are tamed, and some nearly escape 111 v CONTENTS 10 Sequences and series-in which wediscover very odd behaviour in even the smallest infinite set 141 11 Graphs and continuity-in which we arrange a marriage between Intuition and Rigour 161 Suggestionsfor further reading 177 Hints and solutions to selected exercises 180 Index 203 vi INTRODUCTION Failure to read this can damage your understanding 'It saddens me that educated people don't even know that my subject exists.' Paul R. Halmos What isour purpose in writing this book? Quite simply, to help students of mathematics enjoy their work. It seems to us that some students are good at mathematics and just get on with it, others tolerate it for its promised usefulness, but few actively enjoy it except in the rather trivial sense of preferring success to frustration. We have set out quite deliberately to write an entertaining book whose content is serious mathematics. The professional mathematician will be familiar with the idea that entertainment and serious intent are not incom patible: the problem for us is to ensure that our readers will enjoy the entertainment but not miss the mathematical point,which iswhy wesuggest that you regard this introduction as compulsory reading! None of the light-hearted sections are there just for entertainment;they are all meant to illuminate important mathematics. Now that we have alerted you to this, perhaps you willforgive us ifweoccasionally 'explain the point ofthejoke'. Ifyou don't need the explanation, so much the better. What wedo assume ofour readers isthat they already have some interest in and commitment to mathematics as either students or teachers,and that they have some feeling that its pursuit could be enjoyable. Our domain is pure mathematicsat the general levelofsixth-form and early-undergraduate work, and the path we intend to take through this domain is deliberately not direct. It is winding, it branches at many points and it is often self-intersecting.It would bepossible to plan such arouteinwhichthegeneral scenery and specificlandmarksare the fascinatingapplicationsofthe subject, but we have chosen a different route based on showing mathematics as interestingin its own right. Actually,'interesting' is rather too bland a word to express the feelings we hope this book will foster; 'excitement' and 'exhilaration' would be more accurate. People find it hard to believe that mathematicianscan feelthe same sort ofemotions and satisfactionsfor their subject as those with poetic, musical or even sporting inclinations can feel for theirs. Nevertheless it is true, and this has been a factor to consider in planning the route. Another major thread running throughout the book is the idea of proof. vii INTRODUCTION It isfair to say that thecriteria for and methods ofproofmake mathematics unique among all academic disciplines-even the physical sciences. Sadly, proofis an aspect of mathematical education which is often neglected, and the effect of this neglect can be severe. It means that we sell a subject to prospective studentsunderfalsepretences,and whentheyfindthat university mathematicsisverylargely about proofand that theydon't likeit,they have no Trade Descriptions Act to protect them from a fairly miserable three years. There may be a complementary, equally sad effect-that of some potential students never embarking upon a mathematics degree precisely because no one ever demonstrated to them that the search for proof was a pleasure and not a chore of mathematical life,though, for obvious reasons, evidence for this is harder to obtain! To appreciate proof, students must be properly prepared, at sixth-form leveland even before-otherwise a subject such as first-year analysis willappear to be all about proving obvious, not veryexciting facts by perversely difficultmethods.What, then, isan obvious fact,and what do wegain by proving it? Chapter2 goes some way towards providing an answer. At the other extreme, there are some unbelievable (yet true) statements about such basics as numbers and graphs, and we plan to highlight these too. Profundity hidden in the obvious and shock and wonder generated by thetotallyunexpectedprovidethesatisfactionsand excitementofmathematics, and it is natural that those who have experienced them should feel some missionary zeal in spreading the word to others,especially as so many have a view of mathematics as 'sums, only harder'. Some who are 'good at mathematics'sometimes try to tellothersthatthesubject iseasy.Such people are not mathematicians; they are those who are satisfied with solving problems they find easy anyway! Real satisfaction, whether in marathon running, mountaineering, mathematics or music, comes from accepting the challengeofhard problems,withsomeexerciseofjudgementtoavoidselecting too many unrealistically difficult ones! But in mathematics, solving problems is not sufficient.Ifevery problem required theinventionofatotally newtechnique,itwould becomeimpossibly difficultrather thanjust difficult,and satisfaction would rapidly diminish as the feelingthat the subject had no intrinsic unity increased. For this reason unity is another important theme. To take account of it, a decision had to be made about exactly which proof techniques to include, and the answer had to bethose proofs based on principles which,although verysimple,have profound consequences in a variety of different parts of mathematics. We have, in general, avoided one-off tricks except where they are so neat that they cry out for inclusion. Finally,although thebookhas,wehope,what computingcolleagueswould callareader-friendlystyle,thisisbynomeansincompatible withmathematical rigour, and weintend to doa lot ofserious mathematicsaswellas talk about it! Some ofthe questions weask (suchas 'What isa real number?' or 'What counts as a proof?') turn out to be profound,and the hard work they entail viii INTRODUCTION isshared between deciding what the significance ofthe question isand what it would mean to answer it, and doing the detailed working through to achieve the answer. At various points there are gaps indicated thus [m,n] to be filled by the reader, and hints are provided in the appendix. Ends of proofs are signalled by the Halmos tombstone symbol, D, and particularly important results and definitions are enclosed by a box. The book does not have to be read in the order in which it is written. Dependingon the knowledge and interestsofthe reader,there are convenient places to change the route, and these, too,are signposted. It isimportant to point out that this isnot a systematic textbook on any particular branch of mathematics, but our hope is that its overall effect will be to provide motivationto tackle more formal texts,ability to understandand enjoy them, and a healthy critical attitude which will demand close attention both to rigour and to a sound intuitive base. 'The purpose of rigour is to legitimate the conquests of intuition' (Jacques Hadamand, 1865-1962)-and to reveal its not-too-infrequent blunders, weshould perhaps add! We extend our thanks to Macmillan Education's former mathematics editor, Peter Oates, for his help and patience; to Cathy Crewe, Angela Fullerton and Diane Hollowayfor transformingillegiblescrawl;and to each otherformutualsupport.Asforremainingerrors,I blame himand heblames me. Nottingham and Abingdon, 1987 J.B. R.H. ix 1 Alice in Logiland-in which we meet Alice, Tweedledee and Tweedledum, and Logic ... 'Contrariwise', continued Tweedledee, 'if it was so, it might be; and if it were so, it would be; but as it isn't, it ain't. That's logic.' Lewis Carroll 1.1 LOGIC In Alicethrough the Looking-glass Alicemeets Tweedledee and Tweedledum in the forest. The brothers look so much alike that Alice cannot tell them apart. In our version of the story one of the brothers tells lieson Mondays, Tuesdaysand Wednesdays but tellsthe truth on the otherdays ofthe week. The other brother lies on Thursdays, Fridays and Saturdays but is truthful on the remainingdaysoftheweek.One day Alicemeets the two inthe forest, and the following conversation takes place: FIRST BROTHER: I am Tweedledum. SECOND BROTHER: I am Tweedledee. ALICE: Ah, so it's Sunday.