Wohlgemuth - Introduction to proof in abstract mathematics

Introduction to Proof in Abstract Mathematics

Andrew Wohlgemuth

University of Maine

Dover Publications, Inc.
Mineola, New York

Copyright

Copyright 1990, 2011 by Andrew Wohlgemuth
All rights reserved.

Bibliographical Note

This Dover edition, first published in 2011, is an unabridged republication of the work originally published in 1990 by Saunders College Publishing, Philadelphia. The author has provided a new Introduction for this edition.

Library of Congress Cataloging-in-Publication Data

Wohlgemuth, Andrew.

Introduction to proof in abstract mathematics / Andrew Wohlgemuth. Dover ed.

p. cm.

Originally published: Philadelphia : Saunders College Pub., c1990.

Includes index.

eISBN-13: 978-0-486-14168-8

1. Proof theory. I. Title.

QA9.54.W64 2011
511.3'6dc22

20010043415

Manufactured in the United States by Courier Corporation
47854802 2014
www.doverpublications.com

Introduction to the Dover Edition

The most effective thing that I have been able to do over the years for students learning to do proofs has been to make things more explicit. The ultimate end of a process of making things explicit is, of course, a formal systemwhich this text contains. Some people have thought that it makes proof too easy. My own view is that it does not trivialize anything important; it merely exposes the truly trivial for what it is. It shrinks it to its proper size, rather than allowing it to be an insurmountable hurdle for the average student.

The system in this text is based on a number of formal inference rules that model what a mathematician would do naturally to prove certain sorts of statements. Although the rules resemble those of formal logic, they were developed solely to help students struggling with proofwithout any input from formal logic. The rules make explicit the logic used implicitly by mathematicians. After experience is gained, the explicit use of the formal rules is replaced by implicit reference. Thus, in our bottom-up approach, the explicit precedes the implicit. The initial, formal step-by-step format (which allows for the explicit reference to the rules) is replaced by a narrative formatwhere only critical things need to be mentioned. Thus the student is led up to the sort of narrative proofs traditionally found in textbooks. At every stage in the process, the student is always aware of what is and what is not a proofand has specific guidance in the form of a step discovery procedure that leads to a proof outline. The inference rules, and the general method, have been used in two of my texts (available online) intended for students different from the intended readers of this text:

(1) Outlining Proofs in Calculus has been used as a supplement in a third-semester calculus course, to take the mystery out of proofs that a student will have seen in the calculus sequence.

(2) Deductive MathematicsAn Introduction to Proof and Discovery for Mathematics Education has been used in courses for elementary education majors and mathematics specialists.

Andrew Wohlgemuth
August, 2010

Preface

This text is for a course with the primary purpose of teaching students to do mathematical proofs. Proof is taught syntactically. A student with the ability to write computer programs can learn to do straightforward proofs using the method of this text. Our approach leads to proofs of routine problems and, more importantly, to the identification of exactly what is needed in proofs requiring creative insights.

The first aim of the text is to convey the idea of proof in such a way that the student will know what constitutes an acceptable proof. This is accomplished with the use of very strict inference rules that define the precise syntax for an argument. A proof is a sequence of steps that follow from previous steps in ways specifically allowed by the inference rules. In the process of proof abbreviation continues as the mathematics becomes more complex. The development of the idea of proof starts with proofs made up of numbered steps with explicit inference rules and ends with paragraph proofs. An acceptable proof at any stage in this process is by definition an argument that one could, if necessary, rewrite in terms of a previous stage, that is, without the conventions and shortcuts.

The second aim of the text is to develop the students ability to do proofs. First, a distinction is drawn between formal mathematical statements and statements made in ordinary English. The former statements make up what is called our language. It is these language statements that appear as steps in proofs and for which precise rules of inference are given. Language statements are printed in boldface type. Statements in ordinary English are considered to be in our metalanguage and may contain language statements. The primary distinction between metalanguage and language is that, in the former, interpretation of statements (based on context, education, and so forth) is essential. The workings of language, on the other hand, are designed to be mechanical and independent of any interpretation. The language/metalanguage distinction serves to clarify and smooth the transition from beginning, formal proofs to proofs in narrative style. It begins to atrophy naturally in . Presently almost all mathematics students will have had experience in computer programming, in which they have become comfortable operating on at least two language levelsin, say, the operating system and a programming language. The language/metalanguage distinction takes advantage of this.

Language statements are categorized by their form: for example, if , then or and . For each form, two inference rules are given, one for proving and one for using statements of that form. The inference rules are designed to do two jobs at once. First, they form the basis for training in the logic of the arguments generally used in mathematics. Second, they serve to guide the development of a proof. Previous steps needed to establish a given step in a proof are dictated by the inference rule for proving statements having the form of the given step. Inference rules and theorems are introduced in a sequence that ensures that early in the course there will be only one possible logical proof of a theorem. The discovery of this proof is accomplished by a routine process fitting the typical students previous orientation toward mathematics and thus easing the transition from computational to deductive mathematics. Henry Kissinger put the matter simply:

The absence of alternatives clears the mind marvelously.

Theorems in the text are given in metalanguage and contain language statements. The first task in developing a proof is to decide which language statements are to be assumed for the sake of proof (the hypotheses) and which one is to be proved (the conclusion). Although there is no routine procedure for doing this, students have no trouble with it.

Our approach is a compromise between the formal, which is precise but unwieldy, and the informal, which may, especially for beginning students, be ambiguous. A completely formal approach would involve stating theorems in our language. This approach would necessitate providing too many definitions and rules of inference before presenting the first theorem for proof by students. Our approach enables students to build on each proof idea as it is introduced. Understanding of standard informal mathematical style, which we have called metalanguage, is conditioned by a gradual transition from a formal foundation. Our gradual transition contrasts with the traditional juxtaposition of the formal and informal in which an introductory section from classical logic is followed abruptly by narrative style involving language that has not been so precisely defined.