Book of Proof Third Edition
Richard by Richmond, of Proof
Edition 3.2
© 2018 by
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivative 4.0 International License
Typeset in 11pt TEX Gyre Schola using PDFLATEX
Cover by R. Hammack. The cover diagrams are based on a geometric construction that renders a correct perspective view of an object (here an octagonal column) from its floor plan. The method was invented by Piero della Francesca 1415–1492, a Renaissance painter and mathematician.
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 12 1.4. Power Sets 15 1.5. Union, Intersection, Difference 18 1.6. Complement 20 1.7. 22 1.8. Indexed Sets 25 1.9. Sets That Are Number Systems 30 1.10. Russell’s Paradox 32
2. Logic 34
2.1. Statements 35 2.2. And, Or, Not 39 2.3. Conditional Statements 42 2.4. Biconditional Statements 46 2.5. Truth Tables for Statements 48 2.6. Logical Equivalence 50 2.7. Quantifiers 53 2.8. More on Conditional Statements 56 2.9. Translating English to Symbolic Logic 57 2.10. Negating Statements 59 2.11. Logical Inference 63 2.12. An Important Note 64
3. Counting 65
3.1. Lists 65 3.2. The Multiplication Principle 67 3.3. The Addition and Subtraction Principles 74 3.4. Factorials and Permutations 78 3.5. Counting Subsets 85 3.6. Pascal’s Triangle and the Binomial Theorem 90 3.7. The Inclusion-Exclusion Principle 93 3.8. Counting Multisets 96 3.9. The Division and Pigeonhole Principles 104 3.10. Combinatorial Proof 108
II
How to Prove Conditional Statements
4. Direct Proof 113
4.1. Theorems 113 4.2. Definitions 115 4.3. Direct Proof 118 4.4. Using Cases 124 4.5. Treating Similar Cases 125
5. Contrapositive Proof 128
5.1. Contrapositive Proof 128 5.2. Congruence of Integers 131 5.3. Mathematical Writing 133
6. Proof by Contradiction 137
6.1. Proving Statements with Contradiction 138 6.2. Proving Conditional Statements by Contradiction 141 6.3. Combining Techniques 142 6.4. Some Words of Advice 143
More on Proof
7. Proving Non-Conditional Statements 147
7.1. If-and-Only-If Proof 147 7.2. Equivalent Statements 149 7.3. Existence Proofs; Existence and Uniqueness Proofs 150 7.4. Constructive Versus Non-Constructive Proofs 154
8. Proofs Involving Sets 157
8.1. How to Prove a ∈ A 157 8.2. How to Prove A ⊆ B 159 8.3. How to Prove A = B 162 8.4. Examples: Perfect Numbers 165
9. Disproof 172
9.1. Counterexamples 174 9.2. Disproving Existence Statements 176 9.3. Disproof by Contradiction 178
10. Mathematical Induction 180
10.1. Proof by Induction 182 10.2. Proof by Strong Induction 187 10.3. Proof by Smallest Counterexample 191 10.4. The Fundamental Theorem of Arithmetic 192 10.5. Fibonacci Numbers 193
III
v
vi
IV
Relations, Functions and Cardinality
11. Relations 201
11.1. Relations 201 11.2. Properties of Relations 205 11.3. Equivalence Relations 210 11.4. Equivalence Classes and Partitions 215 11.5. The Integers Modulo n 218 11.6. Relations Between Sets 221
12. Functions 223
12.1. Functions 223 12.2. Injective and Surjective Functions 228 12.3. The Pigeonhole Principle Revisited 233 12.4. Composition 235 12.5. Inverse Functions 238 12.6. Image and Preimage 242
13. Proofs in Calculus 244
13.1. The Triangle Inequality 245 13.2. Definition of a Limit 246 13.3. Limits That Do Not Exist 249 13.4. Limit Laws 251 13.5. Continuity and Derivatives 256 13.6. Limits at Infinity 258 13.7. Sequences 261 13.8. Series 265
14. Cardinality of Sets 269
14.1. Sets with Equal Cardinalities 269
14.2. Countable and Uncountable Sets 275
14.3. Comparing Cardinalities 280
14.4. The Cantor-Bernstein-Schröder Theorem 284
Conclusion Solutions
291 292
Preface to the Third Edition
My goal in writing this book has been to create a very inexpensive high-quality textbook. The book can be downloaded from my web page in PDF format for free, and the print version costs considerably less than comparable traditional textbooks.
In this third edition, Chapter 3 (on counting) has been expanded, and a new chapter on calculus proofs has been added. New examples and exercises have been added throughout. My decisions regarding revisions have been guided by both the Amazon reviews and emails from readers, and I am grateful for all comments.
I have taken pains to ensure that the third edition is compatible with the second. Exercises have not been reordered, although some have been edited for clarity and some new ones have been appended. (The one exception is that Chapter 3’s reorganization shifted some exercises.) The chapter sequencing is identical between editions, with one exception: The final chapter on cardinality has become Chapter 14 in order to make way for the new Chapter 13 on calculus proofs. There has been a slight renumbering of the sections within chapters 10 and 11, but the numbering of the exercises within the sections is unchanged.
This core of this book is an expansion and refinement of lecture notes I developed while teaching proofs courses over the past 18 years at University (a large state university) and Randolph- (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.
Lawrenceville, 14, 2018
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 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: 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.
ix
Free PDF version
x Introduction
The chapters are organized as in the following dependency tree. The left-hand column forms the core of the book; each chapter in this column uses material from all chapters above it. Chapters 3 and 13 may be omitted without loss of continuity. But the material in Chapter 3 is a great source of exercises, and the reader who omits it should ignore the later exercises that draw from it. Chapter 10, on induction, can also be omitted with no break in continuity. However, induction is a topic that most proof courses will include.
Dependency Tree
Chapter 2 Logic
Chapter 3 Counting
Book of Proof
Chapter 1 Sets
Chapter 4 Direct Proof
Chapter 5 Contrapositive Proof
Chapter 6
Proof by Contradiction
Chapter 7 Non-Conditional Proof
Chapter 8
Proofs Involving Sets
Chapter 9 Disproof
Chapter 10 Mathematical Induction
Chapter 11 Relations
Chapter 12 Functions
Chapter 13
Proofs in Calculus
Chapter 14 Cardinality of Sets
§10.1 used in §3.5 and §3.6 used in some exercises.
two exercises
Ignore them if Chapter 3 is omitted.
To the instructor. The book is designed for a three or four credit course. A course emphasizing discrete mathematics could cover chapters 1–12. A course that is more of a preparation for analysis could cover all but Chapter 3. The following timetable (for a fourteen-week semester) is a hybrid of these two options. Sections marked with ∗ may require only the briefest mention in class, or may be best left for the students to digest on their own.
xi
Week Monday
1 Section 1.1
2 Sections 1.5, 1.6, 1.7
3 Section 2.2
4 Section 2.7
5 Sections 3.1, 3.2, 3.3
6 EXAM
7 Sections 5.1, 5.2, 5.3∗
8 Sections 7.1, 7.2∗ , 7.3, 7.4
9 Section 8.4
10 Sections 10.1, 10.4∗
11 Sections 11.1, 11.2
12 Section 12.1
13 Sections 12.3, 12.4∗
14 Section 14.1
Wednesday
Section 1.2
Section 1.8
Sections 2.3, 2.4 Sections 2.8∗, 2.9 Section 3.4, 3.5 Sections 4.1, 4.2, 4.3 Section 6.1
Sections 8.1, 8.2 Sections 9.1, 9.2, 9.3∗ Sections 10.2, 10.3 Sections 11.3, 11.4 Section 12.2
Section 12.5
Section 14.2
Friday
Sections 1.3, 1.4
Sections 1.9∗ , 2.1 Sections 2.5, 2.6
Sections 2.10, 2.11∗, 2.12∗ Sections 3.5, 3.6
Sections 4.3, 4.4, 4.5∗ Sections 6.2 6.3∗ Section 8.3
Section 10.1
EXAM
Sections 11.5, 11.6 Section 12.2 Sections 12.5, 12.6∗ Sections 14.3, 14.4∗
The entire book could be covered in a 4-credit course, or in a 3-credit course pitched to a more mature audience.
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 and for rooting out typographical and logical mistakes. Cory proofed early drafts of each chapter before I posted them to my web page, created the index, suggested some interesting exercises and wrote some solutions. Thanks to , , and for suggesting improvements while teaching from the book, and to for proofing the entire third edition. caught further typos and inconsistencies while painstakingly translating the book into Turkish. I am indebted to , 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.
Free PDF version
Part I Fundamentals
Sets
CHAPTER 1
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.
1.1 Introduction to Sets
A set is a collection of things. The things 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, enclosed 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 ̸= 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 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
N = 1,2,3,4,5,6,7,….
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.
Setsneednothavejustnumbersaselements. ThesetB=T,Fconsists 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 2,4∈E. But note that 2∉E, 3∉E and 4∉E.
ConsiderthesetM=0 0,1 0,1 0ofthreetwo-by-twomatrices. We 000111
have0 0∈M,but1 1∉M. Letterscanserveassymbolsdenotingaset’s 00 01
elements: If a = 0 0 , b = 1 0 and c = 1 0 , then M = a, b, c. 000111
If X is a finite set, its cardinality or size is the number of elements it has, and this number is denoted as |X|. Thus for the sets above, |A| = 4, |B|=2, |C|=5, |D|=4, |E|=3 and |M|=3.
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 = . Whenever you see the symbol , it stands for . Observe that || = 0. The 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 box with things in it, so, for example, 2,4,6,8 is a “box” containing four 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 ̸= . (You might also note || = 0 and = 1 as additional evidence that ̸= .)
Book of Proof
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 set of even integers E = …,−6,−4,−2,0,2,4,6,…. In set-builder notation this set is written as
E=2n:n∈Z.
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 reads 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
X = expression : rule,
where the elements of X are understood to be all values of “expression” that are specified by “rule.” For example, above E is the set of all values of the expression 2n that satisfy the rule n ∈ Z. There can be many ways to express thesameset. Forexample,E=2n:n∈Z=n:nisaneveninteger= n:n=2k,k∈Z. Another common way of writing it is
E = n ∈ Z : n is even,
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.
1. n : n is a prime number = 2,3,5,7,11,13,17,…
2. n ∈ N : n is prime = 2,3,5,7,11,13,17,…
3. n2 : n ∈ Z = 0,1,4,9,16,25,…
4. x∈R:x2−2=0=2,−2
5. x∈Z:x2−2=0=
6. x∈Z:|x|<4=−3,−2,−1,0,1,2,3
7. 2x:x∈Z,|x|<4=−6,−4,−2,0,2,4,6
8. x∈Z:|2x|<4=−1,0,1
Free PDF version
6 Sets
Items 6–8 above 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 context. Consider x ∈ Z : |x| < 4 in Example 1.1 (6) above. Here x ∈ Z, so x is a number (not a set), and thus the bars in |x| must mean absolute value, not cardinality. On the other hand, suppose A = 1, 2, 3, 4, 5, 6, 7 and B = X ∈ A : |X| < 3. The elements of A are sets (not numbers), so the |X| in the expression for B must mean cardinality. Therefore B = 1, 2, 7.
Example1.2 Describetheset A=7a+3b : a,b∈Z.
Solution: This set contains all numbers of form 7a + 3b, where a and b are integers. Each such number 7a + 3b is an integer, so A contains only integers. But which integers? If n is any integer, then n = 7n + 3(−2n), so n = 7a + 3b where a = n and b = −2n. Therefore n ∈ A. We’ve now shown that A contains only integers, and also that every integer is an element of A. Consequently A = Z.
We close this section with a summary of special sets. These are sets that are so common that they are given special names and symbols.
• The empty set: =
• The natural numbers: N = 1,2,3,4,5,...
• The integers: Z = ...,−3,−2,−1,0,1,2,3,4,5,...
• The rational numbers: Q=x : x= mn , where m,n∈Z and n̸=0
• The real numbers: R
We visualize the set R of real numbers is as an infinitely long number line.
−4 −3 −2 −1 0 1 2 3 4
Notice that Q is the set of all numbers in R that can be expressed as a
fraction of two integers. You may be aware that Q̸=R, as 2∉Q but 2∈R. (If not, this point will be addressed in Chapter 6.)
In calculus you encountered intervals on the number line. Like R, these too are infinite sets of numbers. Any two numbers a, b ∈ R with a < b give rise to various intervals. Graphically, they are represented by a darkened segment on the number line between a and b. A solid circle at an endpoint indicates that that number is included in the interval. A hollow circle indicates a point that is not included in the interval.
Book of Proof
Introduction to Sets
7
• Closedinterval: [a,b]=x∈R:a≤x≤b
• Openinterval: (a,b)=x∈R:a
49. (x,x+y):x∈R,y∈Z
50. (x,x2):x∈R,y∈N y
51. (x,y)∈R2 : (y−x)(y+x)=0 52. (x,y)∈R2 : (y−x2)(y+x2)=0
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.
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) ̸= (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 as (l, m), ordered pairs of sets such as 2,5,3,2, even ordered pairs of ordered pairs like (2,4),(4,2). The following are also ordered pairs: 2,1,2,3, R,(0,0). Any list of two things enclosed by parentheses is an ordered pair. Now we are ready to define the Cartesian product.
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.
Definition 1.2 The Cartesian product of two sets A and B is another set, denoted as A×B and defined as A×B=(a,b):a∈ A,b∈B.
Book of Proof
The Cartesian Product 9 Thus A × B is a set of ordered pairs of elements from A and B. For
example, if A = k, l, m and B = q, r, then A×B=(k,q),(k,r),(l,q),(l,r),(m,q),(m,r).
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.
B A×B r (k,r) (l,r) (m,r)
q
Figure 1.1. A diagram of a Cartesian product
For another example, 0,1×2,1 = (0,2),(0,1),(1,2),(1,1). If you are 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.
Fact 1.1 If A and B are finite sets, then |A×B|=|A|·|B|.
Example1.3 LetA= , , , , , bethesetconsistingofthesixfaces of a dice. The Cartesian product A × A is diagramed below. By Fact 1.1 (or by simple counting), |A×A|=6·6=36. We might think of A×A as the set of possible outcomes in rolling a dice two times in a row. Each element of the product is an ordered pair of form result of 1st roll, result of 2nd roll. Such constructions are useful in the study of probability.
A A×A (,)(,)(,)(,)(,)(,)
(,)(,)(,)(,)(,)(,) (,)(,)(,)(,)(,)(,) (,)(,)(,)(,)(,)(,) (,)(,)(,)(,)(,)(,) (,)(,)(,)(,)(,)(,)
A
(k, q) (l, q) (m, q) klm
A
Free PDF version
10 Sets
ThesetR×R=(x,y):x,y∈Rshouldbeveryfamiliar. Itcanbeviewed as the set of points on the Cartesian plane, as drawn in Figure 1.2(a). The set R × N = (x, y) : x ∈ R, y ∈ N can be regarded as all of the points on the plane whose second coordinate is a natural number. This is illustrated in Figure 1.2(b), which shows that R × N looks like infinitely many horizontal lines at integer heights above the x-axis. The set N×N is the set of all points on the plane whose coordinates are both natural numbers. It looks like a grid of dots in the first quadrant, as illustrated in Figure 1.2(c).
yyy
xxx
R×N N×N (a) (b) (c)
Figure 1.2. Drawings of some Cartesian products
It is even possible for one factor of a Cartesian product to be a Cartesian product itself, as in R × (N × Z) = (x, ( y, z)) : x ∈ R, ( y, z) ∈ N × Z.
We can also define Cartesian products of three or more sets by moving beyond ordered pairs. An ordered triple is a list (x, y, z). The Cartesian product of the three sets R, N and Z is R × N × Z = (x, y, z) : x ∈ R, y ∈ N, z ∈ Z. Of course there is no reason to stop with ordered triples. In general,
A1×A2×···×An=(x1,x2,…,xn):xi∈Ai foreachi=1,2,…,n.
Be mindful of parentheses. There is a slight difference between R×(N×Z) and R × N × Z. The first is a Cartesian product of two sets; its elements are ordered pairs (x,(y,z)). The second is a Cartesian product of three sets; its elements are ordered triples (x, y, z). To be sure, in many situations there is no harm in blurring the distinction between expressions like (x,(y,z)) and (x, y, z), but for now we regard them as different.
For any set A and positive integer n, the Cartesian power An is An = A×A×···×A=(x1,x2,…,xn) : x1,x2,…,xn ∈ A.
In this way, R2 is the familiar Cartesian plane and R3 is three-dimensional space. You can visualize how, if R2 is the plane, then Z2 = (m, n) : m, n ∈ Z is a grid of points on the plane. Likewise, as R3 is 3-dimensional space, Z3 =(m,n,p):m,n,p∈Z is a grid of points in space.
R×R
Book of Proof
The Cartesian Product 11
In other courses you may encounter sets that are very similar to Rn, but yet have slightly different shades of meaning. Consider, for example, the set of all two-by-three matrices with entries from R:
M=u v w : u,v,w,x,y,z∈R. xyz
This is not really all that different from the set
R6 =(u,v,w,x,y,z) : u,v,w,x,y,z∈R.
The elements of these sets are merely certain arrangements of six real numbers. Despite their similarity, we maintain that M ̸= R6, for two-by- three matrices are not the same things as sequences of six numbers.
Example 1.4 Represent the two sides of a coin by the set S = h,t . The possible outcomes of tossing the coin seven times in a row can be described with the Cartesian power S7. A typical element of S7 looks like
(h,h,t,h,t,t,t),
meaning a head was tossed first, then another head, then a tail, then a head followed by three tails. Note that S7 = 27 = 128, so there are 128 possible outcomes. If this is not clear, then it will be explained fully in Chapter 3.
Exercises for Section 1.2
A. Write out the indicated sets by listing their elements between braces.
1. SupposeA=1,2,3,4andB=a,c. (a) A×B (c) A×A
(b) B×A (d) B×B
2. SupposeA=π,e,0andB=0,1.
(a) A×B (c) A×A (b) B×A (d) B×B
3. x∈R:x2 =2×a,c,e
4. n∈Z:2