Peter J. Eccles - An Introduction to Mathematical Reasoning : Numbers, Sets and Functions

An Introduction to
Mathematical Reasoning

CAMBRIDGE UNIVERSITY PRESS

Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, So Paulo, Delhi, Mexico City

Cambridge University Press
The Edinburgh Building, Cambridge, CB2 8RU, UK

Published in the United States of America by Cambridge University Press, New York

www.cambridge.org

Information on this title: www.cambridge.org/9780521597180

Cambridge University Press 2007

This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press.

First published 1997

14th printing 2012

Printed and bound by CPI Group (UK) Ltd, Croydon CR0 4YY

A catalogue record of this publication is available from the British Library

Library of Congress Cataloging in Publication data

Eccles, Peter J., 1945

An introduction to mathematical reasoning: lectures on numbers, sets, and functions / Peter J. Eccles.

p. cm.

Includes bibliographical references and index.

ISBN 0 521 59269 0 hardback ISBN 0 521 59718 8 paperback
1. Proof theory. I. Title.

QA9.54.E23 1997

511.3dc21 97-11977 CIP

ISBN 978-0-521-59269-7 hardback

ISBN 978-0-521-59718-0 paperback

Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Information regarding prices, travel timetables and other factual information given in this work are correct at the time of first printing but Cambridge Universtiy Press does not guarantee the accuracy of such information thereafter.

I too will something make

And joy in the making;

Altho tomorrow it seem

Like the empty words of a dream

Remembered on waking.

Robert Bridges, Shorter poems.

In loving memory of
Elizabeth Baron and John Baron
(Auntie Lizzie and Uncle Jack)
and those Woodside Bank summers

Contents

Preface

This book is based on lectures given at the Victoria University of Manchester to first year Honours Mathematics students including those taking joint or combined degrees. In common with most other British mathematics departments, the Manchester mathematics department has thoroughly reviewed its curriculum in recent years in the attempt to meet more adequately the needs of students who have experienced the effects of the great changes in the teaching of mathematics in schools, as well as the increased numbers of mature students and students from non-standard backgrounds.

It was clear to us at the University of Manchester that we should completely rethink and broaden our curriculum, including material which we had previously expected students to know on entry to the course but also including introductory material on combinatorics, computer skills and numerical mathematics, as well as encouraging the development of problem solving skills.

A key ingredient of this new University of Manchester curriculum is a module on Mathematical Reasoning whose purpose is to introduce the basic ideas of mathematical proof and to develop skills in writing mathematics, helping to bridge the gap between school and university mathematics. This book is based on this course module. The ability to write correct and clear mathematics is a skill which has to be acquired by observing experienced practitioners at work in lectures and tutorials, by learning to appreciate the details of mathematical exposition in books, and by a great deal of practice. It is a skill readily transferable to many other areas and its acquisition is likely to be one of the main benefits of a mathematics degree course for most students who may well make no further use of most of the specific mathematical content of the course!

There is no absolutely correct way of writing out a given proof. For example, it is necessary to take into account who the intended reader is. But, whoever the reader is, the proof should be expressed as clearly as possible and to achieve this the writer needs to understand the logic of the proof. Writing a proof is not separate from discovering the proof in the way that writing up a scientific experiment is separate from carrying out the experiment or performing a piece of music is separate from composing it. Attempts to write out a proof are an important part of the discovery process. Alison Leonard has written in a totally different context:

Not only are human ideas conveyed by language, they are actually formed by the language available to us.

So it is in mathematics, where we find a parallel development of mathematical ideas and mathematical language.

This is reflected in this book. The emphasis is on helping the reader to understand and construct proofs and to learn to write clear and concise mathematics. This can only be achieved by exploring some particular mathematical topics and the contexts chosen are set theory, combinatorics and number theory. These topics

provide good examples to illustrate a range of basic methods of proof, in particular proof by induction and proof by contradiction,

include some fundamental ideas which are part of the standard tool kit of any mathematician, such as functions and inverses, the binomial theorem, the Euclidean algorithm, the pigeonhole principle, the fundamental theorem of arithmetic, and congruence,

build on ideas met in early schooling illustrating ways in which familiar ideas can be formulated rigorously, for example counting or the greatest common divisor,

include some of the all time great classic proofs, for example the Euclidean proofs of the irrationality of root 2 and the infinity of primes, but also ideas from throughout mathematical history so that there is an opportunity to present mathematics as a continually developing subject.

Roughly speaking, the first three parts of the book are about the basic language of mathematics and the final three parts are about number theory, illustrating how the ideas of the earlier parts are applied to some significant mathematics. The reader may find that the later parts contain some more straightforward material than the early parts simply because there is material on problem solving techniques which can then be practised on specific numerical examples. The topics selected for these later parts, the Euclidean algorithm, modular arithmetic and prime numbers, include material from the whole of mathematical history from classical Greek times to the present day.

I would encourage the reader in working through the first three parts not to expect to understand everything at first. when more familiarity with the language of sets and functions has been acquired. This material on counting provides good practice in using the language of sets and functions in a very familiar context and also illustrates how a familiar process may be made mathematically precise and how this then enables the process to be extended to a less familiar context, counting infinite sets.

The book is divided into twenty four chapters and grew out of a series of twenty four lectures. However, there is far more material in most chapters than could reasonably be covered in a single lecture. A lecture course based on this book would need to be selective covering either a subset of the chapters or, more likely, a subset of the material in most or all of the chapters as the authors lecture courses have done.