The Structure of Proof: With Logic and Set Theory - Hardcover

Michael O'Leary

Hardcover

ISBN 10: 0130190772 ISBN 13: 9780130190772

Publisher: Prentice Hall, 2002

Synopsis

Rather than teach mathematics and the structure of proofs simultaneously, this book first introduces logic as the foundation of proofs and then demonstrates how logic applies to mathematical topics. This method ensures that the reader gains a firm understanding of how logic interacts with mathematics and empowers them to solve more complex problems. Topics include: Propositional Logic; Predicates and Proofs; Set Theory; Mathematical Induction; Number Theory; Relations and Functions; Ring Theory; Topology.

About this title

Excerpt. © Reprinted by permission. All rights reserved.

There are many approaches that one can take with regard to a course dedicated to teaching proof writing. Some prefer to teach the mathematics and the structure of the proofs simultaneously. Others choose to teach the methods of proof and then apply those methods to various topics. This is the strategy of this text. Here we boldly jump into a discussion of logic and examine some details with the belief that if the details are not understood well, then the application of those details will suffer later. Moreover, it is the understanding of how logic interacts with mathematics that empowers the student to have the courage and confidence to tackle greater problems in courses such as Abstract Algebra or Topology. How we accomplish this is outlined below.

TEXT OUTLINE

This text is designed for a one semester course on the fundamentals of proof writing for students with a modest calculus background. The text is divided into three parts: Logical Foundations, Main Topics, and Coming Attractions.

Part I: Logical Foundations. Since it is a requirement for any proof, the text begins with an introduction to mathematical logic. This part begins by studying sentences with and without variables and concludes by writing basic paragraph-style proofs.

1. Propositional Logic. In this chapter we translate propositions using logical symbols and translate the symbols into English. Connectives and truth tables are covered, and formal two-column proofs are introduced. These proofs require students to carefully follow the rules of logic and serve as a model for paragraph proofs.
2. Predicates and Proofs. Here we cover basic sets, quantification, and negations of quantifiers. Two-column proofs are written using propositional forms with quantifiers. Strategies that are covered include Direct and Indirect Proof, Biconditional Proof, and Proof by Cases. A transition to writing paragraph-style proofs is included throughout.

Part II: Main Topics. The logic covered in the first part can be viewed as an advanced organizer for writing proofs. This is best seen in the first application of Part II: set theory. This is a natural first choice, for set theory is just one step from logic. Sets are found throughout the part as we study induction, well-ordered sets, congruence classes, relations, equivalence classes, and functions.

3. Set Theory. The basic set operations as well as inclusion and equality are covered. Two sections are devoted to families of sets and operations with them.
4. Mathematical Induction. Various forms of mathematical induction are studied. Applications include combinatorics, recursion, and the Well-Ordering Principle. Under recursion we look at the Fibonacci sequence and (just for fun!) the golden ratio makes an appearance. (This is the inspiration for the cover graphic.)
5. Number Theory. We take a look at the axioms of number theory and discuss topics such as divisibility, greatest common divisors, primes, and congruences.
6. Relations and Functions. As a prelude to our look at functions, relations are examined. The main example is the equivalence relation. Our look at functions includes the notions of well-defined, domain, range, one-to-one, onto, image, pre-image, and cardinality.

Part III: Coming Attractions. The topics seen in this last part will become familiar to the student of mathematics. Even so, logic and sets are not forgotten. We see these subjects at work when we study rings and then move from the discrete to the continuous and study topology.

7. Ring Theory. The study of ring theory is viewed as a generalization of the study of the integers. We encounter integral domains, fields, subrings, ideals, factors, homomorphisms, and polynomials.
8. Topology. The text closes with a look at the various spaces and subsets that are important to topology. Topics include metric spaces, normed spaces, open and closed sets, isometries, and limits.

As this overview suggests, the text contains more topics than can be covered during a semester. This provides greater flexibility for the instructor, and it gives the student a one-stop reference on the basics of undergraduate mathematics and the proof structures needed for success. This will benefit mathematics students as they take their upper level courses in algebra and analysis. It will also benefit mathematics education students who must teach many of the fundamental concepts.

COURSE STRUCTURES

Notes concerning the dependencies:

1. Section 2.4 introduces two-column proofs with quantifiers and covers universal and existential paragraph proofs. This section can be used without the two-column proofs.
2. Section 2.6 covers various proof methods, the most important of which is proof of biconditionals. If time warrants, this section can be skipped, and the methods introduced as needed.
3. Section 4.2 serves to provide applications of mathematical induction to topics in combinatorics. This section is not referenced elsewhere in the text.
4. Section 4.4 includes the Well-Ordering Principle, which is used in the proofs of the Division Algorithm (5.2.2), Theorem 5.2.6, the fact that every ideal of 7L is principal in Section 7.2, and the Polynomial Division Algorithm (7.5.3). If Section 4.4 is skipped, these results can be used without working through their proofs.
5. Section 5.1 covers the number theory axioms. Although they are mentioned occasionally throughout chapter 5, this section can be omitted.
6. A few examples in Chapters 6 and 7 use congruence classes.
7. Section 6.2 is referenced in Section 7.3 when it is noted that the set of cosets forms a partition for a ring.
8. Families of sets make occasional appearances in Chapters 6 and 7 but, they are more crucial to Sections 8.2 and 8.3.
9. Section 6.7 on cardinalities can be safely omitted.

The outline of the text was designed with two course strategies in mind:

1. A course which has Parts I and II as its focus. This provides the student with a good introduction to mathematical logic with applications. The goal should be to cover most or all of Part I and choose desired topics from Part II. These topics should include the chapters on set theory (3) and mathematical induction (4). Topics from Part III can be used if time permits or as projects for advanced students.
2. A course which has Parts III and III as its focus. This may be appropriate for a class with students who are already strong in logic. Here, Part I can serve as a reference. The goal would be to cover most of Part II and selected topics from Part III.

EXERCISES

Of course, exercises play a crucial role in the text. Each section concludes with a set of problems to solve. These Exercises range from basic tests of understanding to the practice of writing proofs using the topics just discussed. Certain exercises have solutions given in the back. Each chapter in Parts II and III also concludes with an exercise set. These Chapter Exercises are intended to be questions that reflect a higher level of difficulty than the section exercises, combine topics from the entire chapter or possibly earlier in the text, or introduce new ideas inspired by the topics in the chapter.

SOLUTIONS

Solutions are provided to selected exercises indicated by boldface. If only a part of an exercise has a solution, then the letter of the part is in boldface, else the exercise number is in boldface. The solutions take the form of complete answers, partial solutions, or hints.

DEFINITIONS, THEOREMS, AND PROOFS

The layout of the text is designed to emphasize proof writing. Main definitions and theorems are set apart with lines from the rest of the text. This includes the proofs of theorems which are given in detail. The proofs are within the theorem area and indented. The idea is to allow the student to quickly focus on the result and its demonstration. Furthermore, the theorems and main definitions are numbered sequentially by section so that they can be found easily.

EXAMPLES

Examples are used extensively throughout the text. These include computations or short results that illustrate a theorem or, in some cases, are theorems themselves. Key examples are denoted by the word Example and are indented from the rest of the text.

DIAGRAMS

Diagrams are used when appropriate. These not only display traditional topics such as function and relations, but they also serve to illustrate the more "abstract" notions of logic. The diagrams are often completely boxed as figures.

HISTORICAL NOTES

When a mathematician is noted in the text, usually with regard to a famous theorem, a footnote is included giving a brief description of the mathematician including dates and cities of birth and death.

APPENDICES

There are three appendices that serve as references for the student. The first one, Logic Summary, provides a listing of the logic results cited in Part I. The next appendix, Summation Notation, provides a quick reference for the sigma summation notation. These ideas are used with the generalized set operations, mathematical induction, and polynomials. The last appendix, the Greek Alphabet, lists all upper and lowercase Greek letters and their names.

INSTRUCTOR'S MANUAL

An instructor's solution manual is available. To receive a copy, contact the mathematics editor at Prentice Hall.

TECHNICAL NOTES

This document was typeset by the author using LATEX. The PSTricks macro package was used for the diagrams. Other packages include: amsfonts, amsmath, amssymb, eucal, fancyheadings, graphics, ifthen, longtable, mathpi, mathtime, multicol, multind, times, and ulem. The document was prepared using MiKTeX 1.20 and compiled to PostScript using DVIPS 5.86.

A...

Edition details

• Publisher: Prentice Hall
• Publication date: 2002
• ISBN 10: 0130190772
• ISBN 13: 9780130190772
• Binding: Hardcover
• Language: English
• Edition number: 1
• Number of pages: 418