BookOfProof bomba

BookOfProof bomba

(Parte 1 de 4)

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 To my students


Preface vii Introduction viii

I Fundamentals

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

I How to Prove Conditional Statements

4. Direct Proof 87

5.1. Contrapositive Proof 102 5.2. Congruence of Integers 105 5.3. Mathematical Writing 107

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

I 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.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

IV Relations, Functions and Cardinality

1.1. Properties of Relations 179 1.2. Equivalence Relations 184 1.3. Equivalence Classes and Partitions 188 1.4. The Integers Modulo n 191 1.5. Relations Between Sets 194

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


In writing this book I have been motivated by the desire to create a 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


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 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 I 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 I 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 1: 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

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


All of mathematics can be described with sets. This becomes more and more apparent the deeper into mathematics you go. It will be apparent 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.

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,{

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{

We often let uppercase letters stand for sets. In discussing the set{ and then use A to stand for{

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,

The set of integers

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.

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

]} of three two-by-two matrices.

There is a special set that, although small, plays a big role. The empty set is the set {} that has no elements. We denote it as ;, so ;={} .

empty set is the only set whose cardinality is zero.

Be careful in writing the empty set. Don’t write {;} when you mean ;.

These sets can’t be equal because ; contains nothing while {;} contains one thing, namely the empty set. If this is confusing, think of a set as a

numbers. The empty set ;={} is an empty box. By contrast, {;} is a box with an empty box inside it. Obviously, there’s a difference: An empty box is not the same as a box with an empty box inside it. Thus ;6={;} . (You

Introduction to Sets 5

This box analogy can help us think about sets. The set F ={;,{;},{{;}}} may look strange but it is really very simple. Think of it as a box containing three things: an empty box, a box containing an empty box, and a box containing a box containing an empty box. Thus |F|=3. The set G ={ N,Z is a box containing two boxes, the box of natural numbers and the box of integers. Thus |G|=2.

A special notation called set-builder notation is used to describe sets that are too big or complex to list between braces. Consider the infinite

this set is written as

We read the first brace as “the set of all things of form,” and the colon as

“such that.” So the expression E ={ 2n: n∈Z} is read as “E equals the set of all things of form 2n, such that n is an element of Z.” The idea is that E consists of all possible values of 2n, where n takes on all values in Z. In general, a set X written with set-builder notation has the syntax

where the elements of X are understood to be all values of “expression” that are specified by “rule.” For example, the set E above is the set of all values the expression 2n that satisfy the rule n ∈ Z. There can be many ways to express the same set. For example, E = { 2n : n ∈ Z} ={

writing it is

read “E is the set of all n in Z such that n is even.” Some writers use a bar instead of a colon; for example, E ={n∈Z| n is even} . We use the colon.

Example 1.1 Here are some further illustrations of set-builder notation.

6 Sets

These last three examples highlight a conflict of notation that we must always be alert to. The expression |X| means absolute value if X is a number and cardinality if X is a set. The distinction should always be clear from is a number (not a set), and thus the bars in |x| must mean absolute value,

We close this section with a summary of special sets. These are sets or types of sets that come up so often that they are given special names and symbols.

• The real numbers: R (the set of all real numbers on the number line)

Notice that Q is the set of all numbers that can be expressed as a fraction of two integers. You are surely aware that Q6=R, as p2∉Q but p2∈R.

Following are some other special sets that you will recall from your study of calculus. Given two numbers a,b ∈ R with a < b, we can form various intervals on the number line.

Remember that these are intervals on the number line, so they have infinitely many elements. The set (0.1,0.2) contains infinitely many numbers, even though the end points may be close together. It is an unfortunate notational accident that (a,b) can denote both an interval on the line and a point on the plane. The difference is usually clear from context. In the next section we will see still another meaning of (a,b).

Introduction to Sets 7

Exercises for Section 1.1 A. Write each of the following sets by listing their elements between braces.

B. Write each of the following sets in set-builder notation.

8 Sets

1.2 The Cartesian Product

Given two sets A and B, it is possible to “multiply” them to produce a new set denoted as A×B. This operation is called the Cartesian product. To understand it, we must first understand the idea of an ordered pair.

Definition 1.1 An ordered pair is a list (x,y) of two things x and y, enclosed in parentheses and separated by a comma.

For example, (2,4) is an ordered pair, as is (4,2). These ordered pairs are different because even though they have the same things in them, the order is different. We write (2,4)6=(4,2). Right away you can see that ordered pairs can be used to describe points on the plane, as was done in calculus, but they are not limited to just that. The things in an ordered pair don’t have to be numbers. You can have ordered pairs of letters, such

of ordered pairs like ((2,4),(4,2)). The following are also ordered pairs:

ordered pair. Now we are ready to define the Cartesian product.

Definition 1.2 The Cartesian product of two sets A and B is another

Thus A×B is a set of ordered pairs of elements from A and B. For

Figure 1.1 shows how to make a schematic diagram of A×B. Line up the elements of A horizontally and line up the elements of B vertically, as if A and B form an x- and y-axis. Then fill in the ordered pairs so that each element (x,y) is in the column headed by x and the row headed by y.

Figure 1.1. A diagram of a Cartesian product

The Cartesian Product 9

a visual thinker, you may wish to draw a diagram similar to Figure 1.1. The rectangular array of such diagrams give us the following general fact.

(Parte 1 de 4)