Book of Proof
Richard Hammack
Virginia Commonwealth University
Richard Hammack (publisher)
Department of Mathematics & Applied Mathematics
P.O. Box 842014
Virginia Commonwealth University
Richmond, Virginia, 23284
Book of Proof
Edition 2.2
© 2013 by Richard Hammack
This work is licensed under the Creative Commons Attribution-No Derivative Works 3.0
License
Typeset in 11pt TEX Gyre Schola using PDFLATEX
To my students
Contents
Preface
vii
Introduction
viii
I
Fundamentals
1. Sets
3
1.1. Introduction to Sets
3
1.2. The Cartesian Product
8
1.3. Subsets
11
1.4. Power Sets
14
1.5. Union, Intersection, Difference
17
1.6. Complement
19
1.7. Venn Diagrams
21
1.8. Indexed Sets
24
1.9. Sets that Are Number Systems
29
1.10. Russell’s Paradox
31
2. Logic
33
2.1. Statements
34
2.2. And, Or, Not
38
2.3. Conditional Statements
41
2.4. Biconditional Statements
44
2.5. Truth Tables for Statements
46
2.6. Logical Equivalence
49
2.7. Quantifiers
51
2.8. More on Conditional Statements
54
2.9. Translating English to Symbolic Logic
55
2.10. Negating Statements
57
2.11. Logical Inference
61
2.12. An Important Note
62
3. Counting
63
3.1. Counting Lists
63
3.2. Factorials
70
3.3. Counting Subsets
73
3.4. Pascal’s Triangle and the Binomial Theorem
78
3.5. Inclusion-Exclusion
81
v
II
How to Prove Conditional Statements
4. Direct Proof
87
4.1. Theorems
87
4.2. Definitions
89
4.3. Direct Proof
92
4.4. Using Cases
98
4.5. Treating Similar Cases
99
5. Contrapositive Proof
102
5.1. Contrapositive Proof
102
5.2. Congruence of Integers
105
5.3. Mathematical Writing
107
6. Proof by Contradiction
111
6.1. Proving Statements with Contradiction
112
6.2. Proving Conditional Statements by Contradiction
115
6.3. Combining Techniques
116
6.4. Some Words of Advice
117
III
More on Proof
7. Proving Non-Conditional Statements
121
7.1. If-and-Only-If Proof
121
7.2. Equivalent Statements
123
7.3. Existence Proofs; Existence and Uniqueness Proofs
124
7.4. Constructive Versus Non-Constructive Proofs
128
8. Proofs Involving Sets
131
8.1. How to Prove a ∈ A
131
8.2. How to Prove A ⊆ B
133
8.3. How to Prove A = B
136
8.4. Examples: Perfect Numbers
139
9. Disproof
146
9.1. Counterexamples
148
9.2. Disproving Existence Statements
150
9.3. Disproof by Contradiction
152
10. Mathematical Induction
154
10.1. Proof by Strong Induction
161
10.2. Proof by Smallest Counterexample
165
10.3. Fibonacci Numbers
167
vi
IV
Relations, Functions and Cardinality
11. Relations
175
11.1. Properties of Relations
179
11.2. Equivalence Relations
184
11.3. Equivalence Classes and Partitions
188
11.4. The Integers Modulo n
191
11.5. Relations Between Sets
194
12. Functions
196
12.1. Functions
196
12.2. Injective and Surjective Functions
201
12.3. The Pigeonhole Principle
205
12.4. Composition
208
12.5. Inverse Functions
211
12.6. Image and Preimage
214
13. Cardinality of Sets
217
13.1. Sets with Equal Cardinalities
217
13.2. Countable and Uncountable Sets
223
13.3. Comparing Cardinalities
228
13.4. The Cantor-Bernstein-Schröeder Theorem
232
Conclusion
239
Solutions
240
Index
301
Preface
n writing this book I have been motivated by the desire to create a
I high-quality textbook that costs almost nothing.
The book is available on my web page for free, and the paperback
version (produced through an on-demand press) costs considerably less
than comparable traditional textbooks. Any revisions or new editions
will be issued solely for the purpose of correcting mistakes and clarifying
exposition. New exercises may be added, but the existing ones will not be
unnecessarily changed or renumbered.
This text is an expansion and refinement of lecture notes I developed
while teaching proofs courses over the past fourteen years at Virginia
Commonwealth University (a large state university) and Randolph-Macon
College (a small liberal arts college).
I found the needs of these two
audiences to be nearly identical, and I wrote this book for them. But I am
mindful of a larger audience. I believe this book is suitable for almost any
undergraduate mathematics program.
This second edition incorporates many minor corrections and additions
that were suggested by readers around the world. In addition, several
new examples and exercises have been added, and a section on the Cantor-
Bernstein-Schröeder theorem has been added to Chapter 13.
Richard Hammack
Richmond, Virginia
May 25, 2013
Introduction
his is a book about how to prove theorems.
TUntil 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.
ix
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 information
about mathematical structures and to uncover further structures. All
subsequent chapters will 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 conse-
quences of the proof techniques introduced in Chapters 4 through 6.
PART IV
Relations, Functions and Cardinality
• Chapter 11: Relations
• Chapter 12: Functions
• Chapter 13: 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 combinatorics, abstract
algebra, theory of computation, analysis and topology.
x
Introduction
To the instructor. The book is designed for a three credit course. Here
is a possible timetable for a fourteen-week semester.
Week
Monday
Wednesday
Friday
1
Section 1.1
Section 1.2
Sections 1.3, 1.4
2
Sections 1.5, 1.6, 1.7
Section 1.8
Sections 1.9∗, 2.1
3
Section 2.2
Sections 2.3, 2.4
Sections 2.5, 2.6
4
Section 2.7
Sections 2.8∗, 2.9
Sections 2.10, 2.11∗, 2.12∗
5
Sections 3.1, 3.2
Section 3.3
Sections 3.4, 3.5∗
6
EXAM
Sections 4.1, 4.2, 4.3
Sections 4.3, 4.4, 4.5∗
7
Sections 5.1, 5.2, 5.3∗
Section 6.1
Sections 6.2 6.3∗
8
Sections 7.1, 7.2∗, 7.3
Sections 8.1, 8.2
Section 8.3
9
Section 8.4
Sections 9.1, 9.2, 9.3∗
Section 10.0
10
Sections 10.0, 10.3∗
Sections 10.1, 10.2
EXAM
11
Sections 11.0, 11.1
Sections 11.2, 11.3
Sections 11.4, 11.5
12
Section 12.1
Section 12.2
Section 12.2
13
Sections 12.3, 12.4∗
Section 12.5
Sections 12.5, 12.6∗
14
Section 13.1
Section 13.2
Sections 13.3, 13.4∗
Sections marked with ∗ may require only the briefest mention in class, or
may be best left for the students to digest on their own. Some instructors
may prefer to omit Chapter 3.
Acknowledgments. I thank my students in VCU’s MATH 300 courses
for offering feedback as they read the first edition of this book. Thanks
especially to Cory Colbert and Lauren Pace for rooting out typographical
mistakes and inconsistencies. I am especially indebted to Cory for reading
early drafts of each chapter and catching numerous mistakes before I
posted the final draft on my web page.
Cory also created the index,
suggested some interesting exercises, and wrote some solutions. Thanks
to Andy Lewis and Sean Cox for suggesting many improvements while
teaching from the book. I am indebted to Lon Mitchell, whose expertise
with typesetting and on-demand publishing made the print version of this
book a reality.
And thanks to countless readers all over the world who contacted me
concerning errors and omissions. Because of you, this is a better book.
Part I
Fundamentals
CHAPTER
1
Sets
ll of mathematics can be described with sets. This becomes more and
A moreapparentthedeeperintomathematicsyougo. Itwillbeapparent
in most of your upper level courses, and certainly in this course. The
theory of sets is a language that is perfectly suited to describing and
explaining all types of mathematical structures.
1.1 Introduction to Sets
A set is a collection of things. The things in the collection are called
elements of the set. We are mainly concerned
with sets whose elements
are mathematical entities, such as numbers, points, functions, etc.
A set is often expressed by listing its elements between commas, en-
©
closed by braces. For example, the collection 2, 4, 6, 8ª is a set which has
four elements, the numbers 2, 4, 6 and 8. Some sets have infinitely many
elements. For example, consider the collection of all integers,
© ...,−4,−3,−2,−1,0,1,2,3,4,...ª.
Here the dots indicate a pattern of numbers that continues forever in both
the positive and negative directions. A set is called an infinite set if it
has infinitely many elements; otherwise it is called a finite set.
Two sets are equal if they contain exactly the same elements. Thus
©2,4,6,8ª = ©4,2,8,6ª because even though they are listed in a different
©
order, the elements are identical; but 2, 4, 6, 8ª 6= ©2, 4, 6, 7ª. Also
© ... − 4,−3,−2,−1,0,1,2,3,4...ª = ©0,−1,1,−2,2,−3,3,−4,4,...ª.
We often let uppercase letters stand for sets. In discussing the set
©2,4,6,8ª we might declare A = ©2,4,6,8ª and then use A to stand for
©2,4,6,8ª. To express that 2 is an element of the set A, we write 2 ∈ A, and
read this as “2 is an element of A,” or “2 is in A,” or just “2 in A.” We also
have 4 ∈ A, 6 ∈ A and 8 ∈ A, but 5 ∉ A. We read this last expression as “5 is
not an element of A,” or “5 not in A.” Expressions like 6,2 ∈ A or 2,4,8 ∈ A
are used to indicate that several things are in a set.
4
Sets
Some sets are so significant and prevalent that we reserve special
symbols for them. The set of natural numbers (i.e., the positive whole
numbers) is denoted by N, that is,
N = ©1,2,3,4,5,6,7,...ª.
The set of integers
Z = ©...,−3,−2,−1,0,1,2,3,4,...ª
is another fundamental set. The symbol R stands for the set of all real
numbers, a set that is undoubtedly familiar to you from calculus. Other
special sets will be listed later in this section.
Sets need not have just numbers as elements. The set B = ©T, Fª consists
of two letters, perhaps representing the values “true” and “false.” The set
C = ©a, e, i, o, uª consists of the lowercase vowels in the English alphabet.
The set D = ©(0, 0), (1, 0), (0, 1), (1, 1)ª has as elements the four corner points
of a square on the x- y coordinate plane. Thus (0, 0) ∈ D, (1, 0) ∈ D, etc., but
(1, 2) ∉ D (for instance). It is even possible for a set to have other sets
as elements. Consider E = ©1, ©2, 3ª, ©2, 4ªª, which has three elements: the
©
©
©
number 1, the set 2, 3ª and the set 2, 4ª. Thus 1 ∈ E and 2, 3ª ∈ E and
Book of Proof Page 1