Building Proofs

A Practical Guide

This book introduces students to the art and craft of writing proofs, beginning with the basics of writing proofs and logic, and continuing on with more in-depth issues and examples of creating proofs in different parts of mathematics, as well as introducing proofs-of-correctness for algorithms. The creation of proofs is covered for theorems in both discrete and continuous mathematics, and in difficulty ranging from elementary to beginning graduate level.

Just beyond the standard introductory courses on calculus, theorems and proofs become central to mathematics. Students often find this emphasis difficult and new. This book is a guide to understanding and creating proofs. It explains the standard “moves” in mathematical proofs: direct computation, expanding definitions, proof by contradiction, proof by induction, as well as choosing notation and strategies.

Contents:

• Getting Started:

  • A First Example
  • The Starting Line: Definitions and Axioms
  • Matching and Dummy Variables
  • Proof by Contradiction
  • "If and Only If"
  • Drawing Pictures
  • Notation
  • More Examples of Proofs*
  • Exercises

• Logic and Other Formalities:

  • Propositional Calculus
  • Expressions, Predicates, and Quantifiers
  • Rules of Inference
  • Axioms of Equality and Inequality
  • Dealing with Sets
  • Proof by Induction
  • Proofs and Algorithms
  • Exercises

• Discrete and Continuous:

  • Inequalities
  • Some Proofs in Number Theory
  • Calculate the Same Thing in Two Different Ways
  • Abstraction and Algebra
  • Swapping Sums, Swapping Integrals
  • Emphasizing the Important
  • Graphs and Networks
  • Real Numbers and Convergence
  • Approximating or Building "Bad" Things with "Nice" Things
  • Exercises

• More Advanced Proof-Making:

  • Counterexamples and Proofs
  • Dealing with the Infinite
  • Bootstrapping
  • Impredicative Definitions
  • Diagonal Proofs
  • Using Duality
  • Optimizing
  • Generating Functions
  • Exercises

• Building Theories:

  • Choosing Definitions
  • What Am I Modeling?
  • Converting One Kind of Mathematics into Another
  • What is an Interesting Question?
  • Exercises

Readership: Undergraduates and graduates who study mathematical proofs, teachers, and high school students and general readers interested in mathematical proofs.
Key Features:

• This book does not require students to master discrete structures or set theory before starting to understand proofs or how to write them
• Consistent with being a practical guide, the book starts with a proof, and explains how it works
• Writing proofs is discussed for both discrete and continuous mathematics, including linear algebra, calculus, graph (or network) theory, number theory, and analysis
• Strategies for basic and more advanced proof writing are explained: when to use proof by contradiction, proof by induction, unpacking definitions, and so on
• Later chapters discuss more advanced issues that can be useful for more advanced undergraduate students and beginning graduate students
• The book can be used as a textbook for a course of writing proofs, or as a supplement for courses involving proof writing, or as a self-study guide