Book of Proof

Introduction

This is a book about how to prove theorems. Until this point in your education, mathematics has probably been presented as a primarily computational discipline. You have learned to solve equations, compute derivatives and integrals, multiply matrices and find determinants; and you have seen how these things can answer practical questions about the real world. In this setting your primary goal in using mathematics has been to compute answers.

But there is another side of mathematics that is more theoretical than computational. Here the primary goal is to understand mathematical structures, to prove mathematical statements, and even to invent or discover new mathematical theorems and theories. The mathematical techniques and procedures that you have learned and used up until now are founded on this theoretical side of mathematics. For example, in computing the area under a curve, you use the fundamental theorem of calculus. It is because this theorem is true that your answer is correct. However, in learning calculus you were probably far more concerned with how that theorem could be applied than in understanding why it is true. But how do we know it is true? How can we convince ourselves or others of its validity? Questions of this nature belong to the theoretical realm of mathematics. This book is an introduction to that realm.

This book will initiate you into an esoteric world. You will learn and apply the methods of thought that mathematicians use to verify theorems, explore mathematical truth and create new mathematical theories. This will prepare you for advanced mathematics courses, for you will be better able to understand proofs, write your own proofs and think critically and inquisitively about mathematics.

The book is organized into four parts, as outlined below.

PART I Fundamentals

• Chapter 1: Sets
• Chapter 2: Logic
• Chapter 3: Counting

Chapters 1 and 2 lay out the language and conventions used in all advanced mathematics. Sets are fundamental because every mathematical structure, object, or entity can be described as a set. Logic is fundamental because it allows us to understand the meanings of statements, to deduce facts about mathematical structures and to uncover further structures. All subsequent chapters build on these first two chapters. Chapter 3 is included partly because its topics are central to many branches of mathematics, but also because it is a source of many examples and exercises that occur throughout the book. (However, the course instructor may choose to omit Chapter 3.)

PART II Proving Conditional Statements

Chapter 4: Direct Proof

Chapter 5: Contrapositive Proof

Chapter 6: Proof by Contradiction

Chapters 4 through 6 are concerned with three main techniques used for proving theorems that have the “conditional” form “If P, then Q.” 

PART III More on Proof

• Chapter 7: Proving Non-Conditional Statements
• Chapter 8: Proofs Involving Sets
• Chapter 9: Disproof
• Chapter 10: Mathematical Induction

These chapters deal with useful variations, embellishments and consequences of the proof techniques introduced in Chapters 4 through 6.

PART IV Relations, Functions and Cardinality

• Chapter 11: Relations
• Chapter 12: Functions
• Chapter 13: Proofs in Calculus
• Chapter 14: Cardinality of Sets

These final chapters are mainly concerned with the idea of functions, which are central to all of mathematics. Upon mastering this material you will be ready for advanced mathematics courses such as abstract algebra, analysis, topology, combinatorics and theory of computation.