Daniel J. Velleman - How to Prove It: A Structured Approach

Daniel J. Velleman

Department of Mathematics and Statistics

Amherst College

Department of Mathematics and Statistics

University of Vermont

University Printing House, Cambridge CB2 8BS, United Kingdom

One Liberty Plaza, 20th Floor, New York, NY 10006, USA

477 Williamstown Road, Port Melbourne, VIC 3207, Australia

314321, 3rd Floor, Plot 3, Splendor Forum, Jasola District Centre, New Delhi 110025, India

79 Anson Road, #0604/06, Singapore 079906

Cambridge University Press is part of the University of Cambridge.

It furthers the Universitys mission by disseminating knowledge in the pursuit of education, learning, and research at the highest international levels of excellence.

www.cambridge.org

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

DOI: 10.1017/9781108539890

Daniel J. Velleman 2019

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 1994

Second edition 2006

Third edition 2019

Printed in the United Kingdom by TJ International Ltd, Padstow Cornwall

A catalogue record for this publication is available from the British Library.

Library of Congress Cataloging-in-Publication Data

Names: Velleman, Daniel J., author.

Title: How to prove it : a structured approach / Daniel J. Velleman (Amherst College, Massachusetts).

Description: Third edition. | Cambridge ; New York, NY : Cambridge University Press, [2019] | Includes index.

Identifiers: LCCN 2019013488| ISBN 9781108424189 (hardback : alk. paper) | ISBN 9781108439534 (pbk. : alk. paper)

Subjects: LCSH: Logic, Symbolic and mathematicalTextbooks. | MathematicsTextbooks. | Proof theoryTextbooks.

Classification: LCC QA9.V38 2019 | DDC 511.3dc23

LC record available at https://lccn.loc.gov/2019013488

ISBN 978-1-108-42418-9 Hardback

ISBN 978-1-108-43953-4 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.

To Shelley

Students of mathematics and computer science often have trouble the first time theyre asked to work seriously with mathematical proofs, because they dont know the rules of the game. What is expected of you if you are asked to prove something? What distinguishes a correct proof from an incorrect one? This book is intended to help students learn the answers to these questions by spelling out the underlying principles involved in the construction of proofs.

Many students get their first exposure to mathematical proofs in a high school course on geometry. Unfortunately, students in high school geometry are usually taught to think of a proof as a numbered list of statements and reasons, a view of proofs that is too restrictive to be very useful. There is a parallel with computer science here that can be instructive. Early programming languages encouraged a similar restrictive view of computer programs as numbered lists of instructions. Now computer scientists have moved away from such languages and teach programming by using languages that encourage an approach called structured programming. The discussion of proofs in this book is inspired by the belief that many of the considerations that have led computer scientists to embrace the structured approach to programming apply to proof writing as well. You might say that this book teaches structured proving.

In structured programming, a computer program is constructed, not by listing instructions one after another, but by combining certain basic structures such as the if-else construct and do-while loop of the Java programming language. These structures are combined, not only by listing them one after another, but also by nesting one within another. For example, a program constructed by nesting an if-else construct within a do-while loop would look like this:

do

if [condition]

[List of instructions goes here.]

else

[Alternative list of instructions goes here.]

while [condition]

The indenting in this program outline is not absolutely necessary, but it is a convenient method often used in computer science to display the underlying structure of a program.

Mathematical proofs are also constructed by combining certain basic proof structures. For example, a proof of a statement of the form if P then Q often uses what might be called the suppose-until structure: we suppose that P is true until we are able to reach the conclusion that Q is true, at which point we retract this supposition and conclude that the statement if P then Q is true. Another example is the for arbitrary x prove structure: to prove a statement of the form for all x, P(x), we declarexto be an arbitrary object and then prove P (x). Once we reach the conclusion that P(x) is true we retract the declaration of x as arbitrary and conclude that the statement for all x, P(x) is true. Furthermore, to prove more complex statements these structures are often combined, not only by listing one after another, but also by nesting one within another. For example, to prove a statement of the form for all x, if P(x) then Q(x) we would probably nest a suppose-until structure within a for arbitrary x prove structure, getting a proof of this form:

Let x be arbitrary.

Suppose P(x) is true.

[Proof of Q(x) goes here.]

Thus, if P(x) then Q(x).

Thus, for all x, if P(x) then Q(x).

As before, we have used indenting to make the underlying structure of the proof clear.

Of course, mathematicians dont ordinarily write their proofs in this indented form. Our aim in this book is to teach students to write proofs in ordinary paragraphs, just as mathematicians do, and not in the indented form. Nevertheless, our approach is based on the belief that if students are to succeed at writing such proofs, they must understand the underlying structure that proofs have. They must learn, for example, that sentences like Let x be arbitrary and Suppose P are not isolated steps in proofs, but are used to introduce the for arbitrary x prove and suppose-until proof structures. It is not uncommon for beginning students to use these sentences inappropriately in other ways. Such mistakes are analogous to the programming error of using a do with no matching while.

Note that in our examples, the choice of proof structure is guided by the logical form of the statement being proven. For this reason, the book begins with elementary logic to familiarize students with the various forms that mathematical statements take.. These chapters also present the basics of set theory, because it is an important subject that is used in the rest of the book (and throughout mathematics), and also because it serves to illustrate many of the points of logic discussed in these chapters.