Math 13 An Introduction to Abstract Mathematics
Neil Donaldson and Alessandra Pantano
With contributions from:
Michael Hehmann, Christopher Davis, Liam Hardiman, and Ari Rosenfield
March 10, 2024
A
B
C
Contents
Preface: What is Math 13 and who is it for? ii
1 Introduction: What is a Proof? 1
2 Logic and the Language of Proofs 6
2.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Propositional Functions & Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Methods of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Further Proofs & Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Divisibility and the Euclidean Algorithm 32
3.1 Divisors, Remainders and Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Greatest Common Divisors and the Euclidean Algorithm . . . . . . . . . . . . . . . . . 38
4 Sets and Functions 43
4.1 Set Notation and Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Unions, Intersections and Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Introduction to Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5 Mathematical Induction and Well-ordering 60
5.1 Iterative Processes & Proof by Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2 Well-ordering and the Principle of Mathematical Induction . . . . . . . . . . . . . . . . 67
5.3 Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6 Set Theory, Part II 77
6.1 Cartesian Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 Power Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.3 Indexed Collections of Sets: Union and Intersection Revisited . . . . . . . . . . . . . . 85
7 Relations and Partitions 92
7.1 Binary Relations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.2 Functions revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.3 Equivalence Relations & Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.4 Well-definition, Rings and Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
8 Cardinality and Infinite Sets 111
8.1 Cantor’s Notion of Cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
8.2 Uncountable Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
i
Preface: What is Math 13 and who is it for?
Math 13 was created by the late Howard Tucker as a traditional discrete mathematics course; the
number 13 was chosen as a joke! It eventually evolved to become the key transition class in the
undergraduate program, introducing students to abstraction and proof, and serving as the primary
pre-requisite for upper-division courses such as abstract algebra, analysis, linear algebra & number
theory.
The typical student is simultaneously working through lower-division calculus and linear algebra.
Knowledge of such material is unnecessary and students are encouraged to take the class early so as
to ease the transition from algorithmic to abstract mathematics and so that a proof-mentality may be
brought to other lower-division classes.
This text evolved from course notes dating back to 2008. Math 13 is something of a hydra due to
the niche it occupies in UCI’s program: part proof-writing, part discrete mathematics, and part intro-
duction to specific upper-division topics. Logic is covered only at a basic level so that mathematical
proofs may be engaged with quickly. Set theory is spread through the text; the intent is for dry
‘grammar topics to be absorbed via engagement with more accessible and fun ideas. By the end of
the course, interested students should be prepared for a formal study of logic and set theory at the
upper-division level.
Learning Outcomes
1. Developing the skills necessary to read and practice abstract mathematics.
2. Understanding the concept of proof and becoming acquainted with multiple proof techniques.
3. Learning what sort of questions mathematicians ask and what excites them.
4. Introducing upper-division mathematics by providing a taste of what is covered in several
courses. For instance:
Number Theory & Abstract Algebra How can we perform arithmetic with remainders? Can you
figure out what on which day of the week you were born?
Geometry and Topology How can we visualize and work with objects such as the M
¨
obius strip?
How can we use sequences of sets to produce objects (fractals) that appear similar at all
scales?
To Infinity and Beyond! Why are some infinities greater than others?
Useful Texts The following texts are recommended if you want more exercises and material. The
first two are available free online, while the remainder were previous textbooks for Math 13.
Book of Proof, Richard Hammack
Mathematical Reasoning, Ted Sundstrom
Mathematical Proofs: A Transition to Advanced Mathematics, Chartrand/Polimeni/Zhang
The Elements of Advanced Mathematics, Steven G. Krantz
Foundations of Higher Mathematics, Peter Fletcher and C. Wayne Patty
ii
1 Introduction: What is a Proof?
The essential concept in higher-level mathematics is that of proof. A basic dictionary entry might
cover two meanings:
1. A test or trial of an assertion.
2. An argument that establishes the validity (truth) of an assertion.
In science and the wider culture, the first meaning predominates: a defendant was proved guilty
in court; a skin cream is clinically proven to make you look younger; an experiment proves that the
gravitational constant is 9.81ms
2
. A common mistake is to assume that a proved assertion is actually
true. Two juries might disagree as to whether a defendant is guilty, and for many crimes the truth is
uncertain hence the more nuanced legal expression proved beyond reasonable doubt.
In mathematics we use the second meaning: a proof establishes the incontrovertible truth of some
assertion. To see what we mean, consider a simple claim (mathematicians use the word theorem).
Theorem 1.1. The sum of any pair of even integers is even.
Hopefully you believe this statement. But how do we prove it? We can test it by verifying examples
(4 + 6 = 10 is even, (8) + 30 = 22 is even, etc.), but we cannot expect to verify all pairs this way.
For a mathematical proof, we somehow need to test all possible examples simultaneously. To do this,
it is essential that we have a clear idea of what is meant by an even integer.
Definition 1.2. An integer is even if it may be written in the form 2k where k is an integer.
Proof. Let x and y be even. Then x = 2k and y = 2l for some integers k and l. But then
x + y = 2k + 2l = 2(k + l) ()
is even.
The box indicates that we’ve finished our argument. Traditionally the letters Q.E.D. were used, an
acronym for the Latin quod erat demonstrandum (which is what was to be demonstrated).
Consider how the proof depends crucially on the definition.
The theorem did not mention any variables, though these were essential to the proof. The vari-
ables k and l come for free once you write the definition of evenness! This is very common; a proof
is often little more than rearranged definitions.
According to the definition, 2k and 2l together represent all possible pairs of even integers. It is
essential that k and l be different symbols, otherwise all you would be proving is that twice an
even number is even!
The calculation () is the easy bit; without the surrounding sentences and the direct reference
to the definition of evenness, the calculation means nothing.
There is some sleight of hand here; a mathematical proof establishes truth only by reference to one
or more definitions. In this case, the definition and theorem also depend on the meanings of integer
and sum, but we haven’t rigorously defined either since to do so would take us too far afield. In any
context, some concepts will be considered too basic to merit definition.
1
Theorems & Conjectures
Theorems are true mathematical statements that we can prove. Some are important enough to be
named (the Pythagorean theorem, the fundamental theorem of calculus, the rank–nullity theorem,
etc.), but most are simple statements such as Theorem 1.1.
In practice we are often confronted with conjectures: statements we suspect to be true, but which
we don’t (yet) know how to prove. Much of the fun and messy creativity of mathematics lies in
formulating and attempting to prove (or disprove) conjectures.
A conjecture is the mathematician’s equivalent to the scientist’s hypothesis: a statement one would
like to be true. The difference in approach takes us right back to the dual meaning of proof. The
scientist tests their hypothesis using the scientific method, conducting experiments which attempt
(and hopefully fail!) to show that the hypothesis is incorrect. The mathematician tries to prove that a
conjecture is undeniably true by relying on logic. The job of a mathematical researcher is to formulate
conjectures, prove them, and publish the resulting theorems. Creativity lies as much in the formu-
lation as in the proof. Attempting to formulate your own conjectures is an essential part of learning
mathematics; many will likely be false, but you’ll learn a lot in the process!
Here are two conjectures to give us a taste of this process.
Conjecture 1.3. If n is any odd integer, then n
2
1 is a multiple of 8.
Conjecture 1.4. If n is any positive integer, then n
2
+ n + 41 is prime.
1
How can we decide if these conjectures are true or false? To get a feel for things, we start by comput-
ing with several small integers n. In practice, this process is likely what lead to the formulation of the
conjectures in the first place!
n 1 3 5 7 9 11 13
n
2
1 0 8 24 48 80 120 168
n 1 2 3 4 5 6 7
n
2
+ n + 41 43 47 53 61 71 83 97
Since 0, 8, 24, 48, 80, 120 and 168 are all multiples of 8, and 43, 47, 53, 61, 71, 83 and 97 are all prime,
both conjectures appear to be true. Would you bet $100 that this is indeed the case? Is n
2
1 a multiple
of 8 for every odd integer n? Is n
2
+ n + 41 prime for every positive integer n? Establishing whether
each conjecture is true or false requires one of the following:
Prove it by showing it must be true in all cases, or,
Disprove it by finding at least one instance in which the statement is false.
Let us start with Conjecture 1.3. If n is an odd integer, then, by definition, we may write n = 2k + 1
for some integer k. Now compute the object of interest:
n
2
1 = (2k + 1)
2
1 = (4k
2
+ 4k + 1) 1 = 4k
2
+ 4k = 4k(k + 1)
We need to investigate whether this is always a multiple of 8. Since k is an integer, n
2
1 is plainly a
multiple of 4, so everything comes down to deciding whether k(k + 1) is always even. Do we believe
1
A positive integer is prime if it cannot be written as the product of two integers, both greater than one.
2
this? We return to testing some small values of k:
k 2 1 0 1 2 3 4
k
2
+ k 2 0 0 2 6 12 20
Once again, the claim seems to be true for small values of k, but how do we know it is true for all k?
Again, the only way is to prove or disprove it. Observe that k(k + 1) is the product of two consecutive
integers. This is great, because for any two consecutive integers, one is even and the other odd, so
their product must be even. Conjecture 1.3 is indeed a theorem!
Everything so far has been investigative. Scratch work is an essential part of the process, but it isn’t
something we should expect a reader to have to fight their way through. We therefore offer a formal
proof. This is the final result of our deliberations; investigate, spot a pattern, conjecture, prove, and
finally present our work in as clean and convincing a manner as we can.
Theorem 1.5. If n is any odd integer, then n
2
1 is a multiple of 8.
Proof. Let n be any odd integer. By definition, we may write n = 2k + 1 for some integer k. Then
n
2
1 = (2k + 1)
2
1 = (4k
2
+ 4k + 1) 1 = 4k
2
+ 4k = 4k(k + 1)
We distinguish two cases. If k is even, then k(k + 1) is even and so 4k(k + 1) is divisible by 8.
If k is odd, then k + 1 is even. Therefore k(k + 1) is again even and 4k(k + 1) divisible by 8.
In both cases n
2
1 = 4k(k + 1) is divisible by 8.
All that work, just for five lines of clean argument! But wasn’t it fun?
When constructing elementary proofs it is common to feel unsure over how much detail to supply.
We plainly relied on the definition of oddness, but we also used the fact that a product is even when-
ever either factor is even; does this need a proof? Since the purpose of a proof is to convince the
reader, the appropriateness of an argument will depend on context and your audience: if you are
trying to convince a middle-school student, maybe you should justify this step more fully, though
the cost would be a longer argument that might be harder to grasp in its totality. A perfect proof that
is best for all situations is unlikely to exist! A good rule is to imagine you are writing for another
mathematician at the same level as yourself—if a fellow student believes your argument, that’s a
good sign of its validity.
Now consider Conjecture 1.4. The question is whether n
2
+ n + 41 is prime for every positive integer
n. When n 7 the answer is yes, but examples do not make a proof! To investigate further, return
to the definition of prime (Footnote 1): is there a positive integer n for which is n
2
+ n + 41 can be
factored as a product of two integers, both at least 2? A straightforward answer is staring us in the
face! When n = 41 such a factorization certainly exists:
n
2
+ n + 41 = 41
2
+ 41 + 41 = 41(41 + 1 + 1) = 41 ·43
We call n = 41 a counterexample; it shows that there is at least one integer n for which n
2
+ n + 41 is
not prime. Conjecture 1.4 is therefore false (it has been disproved).
3
Planning and Writing Proofs
Your main responsibility in this course is the construction of proofs. Their sheer variety means that,
unlike in elementary calculus, you cannot simply practice computing tens of similar problems until
the process becomes automatic. So how do you learn to write proofs?
The first step is to read other arguments. Don’t just accept them, make sure you believe them: check
the calculations, verify claims, rewrite the argument in your own words adding any clarification you
think necessary.
As you read others’ arguments, the question will often arise: how did they ever come up with this? As
our work on Theorem 1.5 shows, the source of a proof is often less magical than it appears; usually
the author experimented until they found something that worked. Most of that experimentation gets
hidden in the final proof which should be as clean and easy to read as possible. Imagine it as a concert
performance after lots of private practice; no-one wants to hear wrong notes at the Carnegie Hall!
In order to bridge the gap, we recommend splitting the proof-writing process into several steps.
Interpret Make sense of the statement. What is it saying? Can you rephrase in a way that is clearer
to you? What are you assuming? The most important part of this step is identifying the logical
structure of the statement. We’ll discuss this at length in the next chapter.
Brainstorm Convince yourself that the statement is true. First, look up the relevant definitions. Next,
think of some instances where the conditions of the statement are met. Try out some examples,
and ask yourself what makes the claim work in those instances. Examples can be crucial for
building intuition about why the claim is true and can sometimes suggest a proof strategy.
Review other theorems that relate to these definitions. Do you know any theorems that relate
your assumptions to the conclusion? Have you seen a proof of a similar statement before?
Sketch Build the skeleton of your proof. Think again about what you are assuming and what you
are are you trying to prove. As we’ll see in the next chapter, it is often straightforward to write
down reasonable first and last steps (the bread slices of a proof-sandwich). Try to connect these
with informal arguments. If you get stuck, try a different approach.
This step is often the longest in the proof-writing process. It is also where you will be doing
most of your calculations. You can be as messy as you want because no-one ever has to see
it! Once you’ve learned a variety of different proof methods, this is a good stage at which to
experiment with different approaches.
Prove Once you have a suitable sketch, it’s time to prove the statement to the world. Translate your
sketch into a linear story, written in complete sentences. Carefully word your explanations and
avoid shorthand, though well-understood mathematical symbols like = are encouraged. The
result should be a clear, formal proof like you’d find in a mathematics textbook. Although you
are providing a mathematical argument, your proof should read like prose.
Review Finally, review your proof. Assume the reader is meeting the problem for the first time and
has not seen your sketch. Read your proof with skepticism; consider its readability and flow.
Get read of unnecessary claims and revise the wording if necessary. Read your proof out loud.
If you’re adding extra words that aren’t written down, include them in the proof. Finally, share
your work with others. Do they understand it without any additional input from you?
4
Conjectures: True or False?
Higher-level mathematics is all about the important links between proofs, definitions, theorems and
conjectures. We prove theorems (and solve homework problems) because they make us use, and aid
our understanding of, definitions. We state definitions to help us formulate conjectures and prove
theorems. One does not know mathematics, one does it. Mathematics is a practice; an art as much as it
is a science.
With this in mind, do your best to prove or disprove the following conjectures. Don’t worry if you’re
currently unsure as to the meanings of some of the terms or notation: ask! It will all be covered
formally soon enough. At the end of the course, revisit these problems to realize how much your
proof skills have improved.
1. The sum of any three consecutive integers is even.
2. There exist integers m and n such that 7m + 5n = 4.
3. Every common multiple of 6 and 10 is divisible by 60.
4. There exist integers x and y such that 6x + 9y = 10.
5. For every positive real number x, x +
1
x
is greater than or equal to 2.
6. If x is any real number, then x
2
x.
7. If n is any integer, n
2
+ 5n must be even.
8. If x is any real number, then |x| x.
9. If n is an integer greater than 2, then n
2
1 is not prime.
10. An integer is divisible by 5 when its last digit is 5.
11. If r is a rational number, then there is a non-zero integer n for which rn is an integer.
12. There is a smallest positive real number.
13. For all real numbers x, there exists a real number y for which x < y.
14. There exists a real number x such that, for all real numbers y, x < y.
15. The sets A = {n N : n
2
< 25} and B = {n
2
: n N and n < 5} are equal. Here N denotes
the set of natural numbers.
5
2 Logic and the Language of Proofs
2.1 Propositions
In order to read and construct proofs, we need to start with the language in which they are written:
logic. This is to mathematics what grammar is to English.
Definition 2.1. A proposition or statement is a sentence that is either true or false.
Examples 2.2. 1. 17 24 = 7. 2. 39
2
is an odd integer.
3. The moon is made of cheese. 4. Every cloud has a silver lining.
5. God exists.
For a proposition to make sense, we must agree on the meaning of each concept it contains. When
people argue over propositions, in practice they are often disagreeing about definitions. There are
many concepts of God; we cannot begin to consider whether or not They exist until we agree which
concept is being discussed! This also illustrates that the truth status of a proposition need not be known
at the moment you state it; this is particularly common in mathematics.
2
Truth Tables and Combining Propositions
To develop basic rules and terminology, it is helpful to consider abstract propositions: P, Q, R, . . ..
Given a small number of propositions, all possible combinations of truth states may be easily repre-
sented in tabular format: in a truth table. These are useful for defining new propositions.
Definition 2.3. Let P and Q be propositions. The truth tables below define three new propositions
modeled on the words and, or and not.
The conjunction P Q is read P and Q.”
The disjunction P Q is read P or Q.”
The negation ¬P is read “not P.”
P Q P Q P Q
T T T T
T F F T
F T F T
F F F F
P ¬P
T F
F T
The letters T/F stand for true/false. E.g., the second line of the first table says that if P is true and Q is
false, then the proposition P and Q is false, while P or Q is true.
Example 2.4. Suppose P and Q are the following propositions:
P: “I like purple.” Q: “I like chartreuse.”
We form the new propositions described in the definition:
P Q: “I like purple and chartreuse.” P Q: “I like purple or chartreuse.”
¬P: “I do not like purple.”
It is typical to modify phrasing to aid readability: “Not, I like purple” just sounds weird! Note also
that or is inclusive in logic: if “I like purple or chartreuse” is true, then you might like both!
2
More surprisingly, there are even propositions whose truth state is impossible to determine!
6
Let’s continue by adding a third proposition:
R: “It’s 9am.”
What proposition is represented by the following English sentence?
“I like purple and I like chartreuse or it’s 9am.”
Is it P (Q R) or is it (P Q) R? Without brackets, the sentence is unclear; the moral is that
English is terrible at logic! Indeed, as the truth table shows, the two logical expressions really do
mean different things!
P Q R Q R P (Q R) P Q (P Q) R
T T T T T T T
T T F T T T T
T F T T T F T
T F F F F F F
F T T T F F T
F T F T F F F
F F T T F F T
F F F F F F F
Conditional and Biconditional Connectives
Of critical importance is the ability to have one proposition lead to another.
Definition 2.5. Given propositions P, Q, the conditional (=)
and biconditional () connectives define new propositions as
described in the truth table.
For the proposition P = Q, we call P the hypothesis and Q the
conclusion.
P Q P = Q P Q
T T T T
T F F F
F T T F
F F T T
Connective propositions can be read and written in many different ways:
P = Q P Q
P implies Q P therefore Q P if and only if Q
If P, then Q Q follows from P P iff Q
P only if Q Q if P P and Q are (logically) equivalent
P is sufficient for Q Q is necessary for P P is necessary and sufficient for Q
Example 2.6. The following sentences express, in English, the same conditional P = Q.
If you are born in Rome, then you are Italian.
You are Italian if you are born in Rome.
You are born in Rome only if you are Italian.
Being born in Rome is sufficient for being Italian.
Being Italian is necessary for being born in Rome.
Are you comfortable with what the propositions P and Q are here?
7
Connectives are central to mathematics for many reasons. In particular:
1. The vast majority of theorems we’ll encounter may be written as a connective P = Q. For
instance, revisit Theorem 1.1 and the discussion that follows:
If x and y are even integers, then x + y is even.
Identifying the hypothesis and conclusion is essential if you want to understand a theorem!
2. Simple proofs typically involve chaining a sequence of connectives:
P = P
2
= ··· = P
n
= Q
We’ll revisit these ideas in Section 2.3, and repeatedly throughout the course.
While the biconditional should be easy to remember, it is harder to make sense of the conditional
connective. Short of simply memorizing the truth table, here are two examples that might help.
Examples 2.7. 1. Suppose your professor says, “If the class earns a B average on the midterm, then
I’ll bring doughnuts.” The only situation in which the teacher will have lied is if the class earns
a B average but she fails to provide doughnuts.
2. (F = T really can be true!) Let P be the proposition “7 = 3” and Q be “0 = 0.” Since
multiplication of both sides of an equation by zero is algebraically valid, we see that
7 = 3 = 0 ·7 = 0 ·3 (If 7 = 3, then 0 times 7 equals 0 times 3)
= 0 = 0 (then 0 equals 0)
This argument is perfectly correct: the implication P = Q is true. It (rightly!) makes us uncom-
fortable because the hypothesis is false.
If we instead add 1 to each side of 7 = 3, we’d obtain a example where F = F is true.
Tautologies and Contradictions
Definition 2.8. A tautology is a logical expression that is always true, regardless of what the compo-
nent statements might be.
A contradiction is a logical expression that is always false.
Examples 2.9. 1. P (¬P) is a contradiction.
Regardless of the proposition P, it cannot be true at the same
time as its negation!
P ¬P P (¬P)
T F F
F T F
2.
P (P = Q)
= Q is a tautology.
P Q P = Q P (P = Q)
P (P = Q)
= Q
T T T T T
T F F F T
F T T F T
F F T F T
8
The Converse and Contrapositive
Definition 2.10. The converse of P = Q is the reversed implication Q = P.
The contrapositive of P = Q is the implication ¬Q = ¬P.
It is vital to understand the distinction between these. In general, the truth status of the converse
bears no relation to that of the original, though the contrapositive is much better behaved.
Theorem 2.11. The contrapositive of an implication is logically equivalent to the original.
Proof. Compute the truth table and observe that the third and sixth columns are identical:
3
P Q P = Q ¬Q ¬P ¬Q = ¬P
T T T F F T
T F F T F F
F T T F T T
F F T T T T
Example 2.12. Let P and Q be the following statements:
P: “Claudia is holding a peach.” Q: “Claudia is holding a piece of fruit.”
Since a peach is indeed a piece of fruit, the proposition P = Q is true:
P = Q: “If Claudia is holding a peach, then she is holding a piece of fruit.”
The converse of P = Q is the sentence
Q = P: “If Claudia is holding a piece of fruit, then she is holding a peach.”
This is palpably false: Claudia could be holding an apple! However, in accordance with Theorem
2.11, the contrapositive is true:
¬Q = ¬P: “If Claudia is not holding any fruit, then she is not holding a peach.”
Negating Logical Expressions
Mathematics often requires us to negate propositions. What would you suspect to be the negation of
a conditional P = Q? Is it enough to say P doesn’t imply Q”? But what does this mean?
We again rely on a truth table: to get the last column, recall that
negation simply swaps T and F. Can we write this column in
another way? Since there is only a single T in the final column,
we see that we’ve proved the following.
P Q P = Q ¬(P = Q)
T T T F
T F F T
F T T F
F F T F
Theorem 2.13. ¬(P = Q) is logically equivalent to P ¬Q (“P and not Q”).
3
Otherwise said, (P = Q) (¬Q = ¬P) is a tautology.
9
Example 2.14. Consider the implication
It’s the morning therefore I’ll have coffee.
Hopefully its negation is clear:
It’s the morning and I won’t have coffee.
As in Example 2.7, it might help to think about what it means for the original statement to be false.
Warning! The negation of P = Q is not a conditional. In particular it is neither of the following:
The converse Q = P.
The contrapositive of the converse ¬P = ¬Q.
If you are unsure about this, write down the truth tables and compare.
Our final results in basic logic also involve negations; they are named for Augustus de Morgan, a
famous 19
th
century logician.
Theorem 2.15 (de Morgan’s laws). Let P and Q be propositions.
1. ¬(P Q) is logically equivalent to ¬P ¬Q
2. ¬(P Q) is logically equivalent to ¬P ¬Q
Proof. For the first law, observe that the fourth and seventh columns of the truth table are identical.
P Q P Q ¬(P Q) ¬P ¬Q ¬P ¬Q
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
The second law is an exercise.
Example 2.16. Consider the sentence:
I rode the subway and I had coffee.
To negate this using de Morgan’s first law, we might write:
I didn’t ride the subway or I didn’t have coffee.
Subway Coffee Su and Co
T T T
T F F
F T F
F F F
This feels awkward in English because the negation encompasses three distinct possibilities. Note
how the logical (inclusive) use of or includes the last row of the truth table: the possibility that you
neither rode the subway nor had coffee.
As with Example 2.4, this is another advert for the use of logic: English simply isn’t very helpful for
precisely stating complex logical statements.
10
Aside: Algebraic Logic We can use truth tables to establish other laws of basic logic, for instance:
Double negation ¬(¬P) P
Commutativity P Q Q P P Q Q P
Associativity (P Q) R P (Q R) (P Q) R P (Q R)
Distributivity (P Q) R (P R) (Q R) (P Q) R (P R) (Q R)
To make things more algebraic, we’ve replaced “is logically equivalent to” with a biconditional.
4
Armed with such laws, one can often suitably manipulate logical expressions without laboriously
creating truth tables. This is not the focus of this course, though you might find it fun!
For this course, it is probably not worth memorizing these laws. Your intuitive understanding of and,
or and not mean you’ll likely apply the laws correctly whenever necessary.
Exercises 2.1. A reading quiz and several questions with linked video solutions can be found online.
1. Express each statement in the form, “If . . . , then . . . There are many possible correct answers.
(a) You must eat your dinner if you want to grow.
(b) Being a multiple of 12 is a sufficient condition for a number to be even.
(c) It is necessary for you to pass your exams in order for you to obtain a degree.
(d) A triangle is equilateral only if all its sides have the same length.
2. Suppose x is an even integer and y is an irrational number are true statements, and that
z 3” is a false statement. Which of the following are true?
(Hint: Label each statement and think about each using connectives)
(a) If x is an even integer, then z 3.
(b) If z 3, then y is an irrational number.
(c) If z 3 or x is an even integer, then y is an irrational number.
(d) If y is an irrational number and x is an even integer, then z 3.
3. Orange County is considering two competing transport plans: widening the 405 freeway and
constructing light rail down its median. A local politician is asked, “Would you like to see the
405 widened or would you like to see light rail?” The politician wants to sound positive, but to
avoid being tied to one project. What is their response?
(Hint: Think about how the word ‘OR’ is used in logic)
4. Consider the proposition: “If the integer m is greater than 3, then 2m is not prime.”
(a) Rewrite the proposition using the word ‘necessary.’
(b) Rewrite the proposition using the word ‘sufficient.’
(c) Write the negation, converse and contrapositive of the proposition.
5. Suppose the following sentence is true: “If Amy likes art, then no-one likes history.” What, if
anything, can we conclude if we discover that someone likes history.
4
Stating the laws in this fashion is to assert that each expression is a tautology (Definition 2.8). For instance, to claim
that ¬(¬P) is logically equivalent to P is to assert that ¬(¬P) P is a tautology.
11
6. Construct the truth tables for the propositions P (Q R) and (P Q) R. Are they the same?
7. Use truth tables to establish the following laws of logic:
(a) Double negation: ¬(¬P) P.
(b) Idempotent law: P P P.
(c) Absorption law: P (P Q) P.
(d) Distributive law: (P Q) R (P R) (Q R).
8. (a) Decide whether (P ¬P) = Q is a tautology, a contradiction, or neither.
(b) Explain why ¬P ¬Q is logically equivalent to P = (P ¬Q).
(c) Prove:
(P ¬Q) = F
(P = Q) is a tautology. Here F represents a contradiction.
9. (a) Prove that the expressions (P = Q) (Q = P) and P Q are logically equivalent.
(b) Prove that
(P = Q) (Q = R)
=
P = R
is a tautology.
Why do these make intuitive sense?
10. Use logical algebra (e.g., page 11) to show that
(P Q) ¬P
¬Q is a contradiction.
11. Do there exist propositions P, Q for which both P = Q and its converse are false? Explain.
12. Your friend insists that the negation of the sentence “Mark and Mary have the same height” is
“Mark or Mary do not have the same height.” What is the correct negation? Where did your
friend go wrong?
13. Suppose that the following statements are true:
(a) Every octagon is magical.
(b) If a polygon is not a rectangle, then is it not a square.
(c) A polygon is a square, if it is magical.
Is it true that “Octagons are rectangles”? Explain your answer.
(Hint: try rewriting each of the statements as an implication)
14. The connective (the Quine dagger, NOR) is defined by the truth table:
(a) Prove that P Q is logically equivalent to ¬(P Q).
(b) Find a logical expression built using only P and the connective
which is logically equivalent to ¬P.
P Q P Q
T T F
T F F
F T F
F F T
(c) Find an expression built using only P, Q and which is logically equivalent to P Q.
15. (Just for fun) Augustus de Morgan satisfied his own problem:
I turn(ed) x years of age in the year x
2
.
(a) Given that de Morgan died in 1871, and that he wasn’t the beneficiary of some miraculous
anti-aging treatment, find the year in which he was born.
(b) Suppose you have an acquaintance who satisfies the same problem. When were they born
and how old will they turn this year?
Do your best to give a formal proof of your correctness.
12
2.2 Propositional Functions & Quantifiers
The majority of mathematical propositions are more complicated that those seen in Section 2.1. In
particular, they typically involve variables, for instance
x is an integer greater than 5.”
Definition 2.17. A propositional function is a family of propositions which depend on one or more
variables. The collection of permitted variables is the domain.
If P is a propositional function depending on a single variable x, then for each object a in the domain,
P(a) is a proposition. Typically P(x) is true for some x and false for others.
Example 2.18. Consider the propositional function P(x): x
2
> 4” with domain the real numbers.
Plainly P(1) is false (“1
2
> 4”) and P(6) is true (”6
2
> 4”).
In mathematics, propositional functions are often quantified. English contains various quantifiers (all,
some, many, few, several, etc.), but in mathematics we are primarily concerned with just two.
Definition 2.19. The universal quantifier is read ‘for all’. The existential quantifier is read ‘there
exists.’ Given a propositional function P(x), we define two new quantified propositions:
x, P(x) is true if and only if P(x) is true for every x in its domain.
x, P(x) is true if and only if P(x) is true for at least one x in its domain.
It is common to describe the domain when quantifying propositions by including a descriptor after
the quantifier (bounding the quantifier—see below).
As with connectives, there are many ways to express quantified propositions both mathematically
and in English. The use of symbolic quantifiers involves a trade-off: compact statements can improve
clarity, but they are harder to read for the uninitiated, so consider your audience! While it is your
choice whether to employ symbolic quantifiers in your own writing, it is essential that you know how
to read/recognize them and that you can translate between various incarnations.
Example (2.18 cont.). To gain some practice with bounded quantifiers, we introduce the notation
x R: this means that x is a real number.
x R, x
2
> 4” might be read, “The square of every real number is greater than 4.”
The quantified expression is false since 1
2
> 4 is false: we call x = 1 a counter-example.
x R, x
2
> 4” might be read, “There is a real number whose square is greater than 4.”
The quantified expression is true since 6
2
> 4 (is true): we call x = 6 an example.
Due to their importance, it is worth defining these last concepts formally.
Definition 2.20. An example of x, P(x) is an element x
0
in the domain of P for which P(x
0
) is true.
A counter-example to x, P(x) is an element x
0
in the domain of P for which P(x
0
) is false.
13
Universal Quantifiers and Connectives: Hidden Quantifiers Universally quantified statements
are interchangeable with implications. Given a propositional function Q(x), let P(x) be the proposi-
tion x lies in the domain of Q.” Then
x, Q(x) is logically equivalent to P(x) = Q(x)
Connectives containing variables are therefore assumed to be universal. When written as a connec-
tive, the universal quantifier is typically hidden.
5
Examples 2.21. 1. The universal statement “Every cat is neurotic,” may also be written
If x is a cat, then x is neurotic.
2. Revisiting Example 2.18, we could rewrite x R, x
2
> 4” as a connective
x R = x
2
> 4 (If x is a real number, then x
2
> 4)
3. The following three sentences have identical meaning:
The square of an odd integer is odd. n odd, n
2
is odd. n odd = n
2
odd.
In only one of the sentences is the universal quantifier explicit. For even more variety, the third
sentence can also be viewed as a universal statement about all integers; including the hidden
quantifier in this case results in
n Z, n odd = n
2
odd.
where the symbol Z represents the (set of) integers.
We’ve already seen that disproving a universal statement requires only that we supply a counter-
example. While such might require some effort to find, often the resulting argument is very simple.
By contrast, proving a universal statement is the same as proving a connective, an activity that is
typically much more involved. We therefore largely postpone this to the next section. Regardless, a
simple proof of our oddness claim should be easy to follow.
Proof of Example 2.21.3. If an integer n is odd, then it may be written in the form n = 2k + 1 for some
integer k. But then
n
2
= (2k + 1)
2
= 4k
2
+ 4k + 1 = 2(2k
2
+ 2k) + 1
is plainly also odd.
Similarly, proving an existential statement (by providing an example) is typically more straightforward
than disproving such. To understand this duality, we need to understand how to negate quantified
propositions.
5
By contrast, the existential quantifier is never hidden: it is always explicitly written as a symbol (), or as a phrase in
English (there is, there exists, some, at least one, etc.).
14
Negating Quantified Propositions
To negate a proposition, we consider what it means for it to be false. We already understand what
this means for a universal proposition:
x, P(x) is false if and only if there exists a counter-example.
The negation of a universal statement is existentially quantified:
The negation of P(x) is always true” is P( x) is sometimes false.”
Repeating this with ¬P(x) results in a related observation:
The negation of P(x) is always false” is P(x) is sometimes true.”
Theorem 2.22. For any propositional function P(x):
1. ¬
x, P(x)
is logically equivalent to x, ¬P(x).
2. ¬
x, P(x)
is logically equivalent to x, ¬P(x).
Examples 2.23. 1. “Everyone owns a bicycle,” has negation, “Someone does not own a bicycle.” It
is somewhat ugly, but we could write this symbolically:
¬
people x, x owns a bicycle
a person x such that x does not own a bicycle
2. The quantified proposition
6
x > 0 such that sin x = 4,” has the form x, P(x). Its negation
has the form x, ¬P(x). Explicitly:
x > 0, sin x = 4
Since the sine function satisfies the inequalities 1 sin x 1, the original proposition is false
and its negation true.
Warning! Never negate a quantifier’s bounds: x 0. . . is completely wrong!
3. Be especially careful when negating connectives: after negation, a hidden quantifier x be-
comes explicit.
¬
P(x) = Q(x)
is logically equivalent to x, P(x) ¬Q(x)
(a) (Example 2.21.3) The negation of n odd = n
2
odd”is the (false) claim
n Z with n odd and n
2
even.
(b) (Example 2.18) The negation of the false claim x R = x
2
> 4” is the true assertion
n R for which x
2
4
6
x > 0” indicates that the domain of the proposition “sin x = 4” is the positive real numbers.
15
Multiple Quantifiers
A propositional function can have several variables, each of which may be quantified.
Examples 2.24. 1. The quantified proposition
x > 0, y > 0 such that xy = 4
might be read, “Given any positive number, there is another such that their product is four.”
Hopefully you believe that this is true! Here is a simple argument which comes from viewing
it as an implication, “If x > 0, then y > 0 such that xy = 4.”
Proof. Suppose we are given x > 0. Let y =
4
x
, then xy = 4, as required.
Being clear about domains is critical. Suppose we modify the original proposition:
x R, y R such that xy = 4 (†)
Our proof now fails! The new statement (†) is false: indeed x = 0 provides a counter-example.
Disproof. Let x = 0. Since xy = 0 for any real number y, we cannot have xy = 4.
Alternatively, we could negate (†): following Theorem 2.22, we switch the symbols and
negate the final proposition,
7
¬
x R, y R, xy = 4
x R, y R, xy = 4 (¬())
Our disproof of (†) is really a proof of the negation: we provided the example x = 0, thus demon-
strating the truth of a -statement. Since the negation is true, the original () is false.
2. Order of quantifiers matters! The meaning of a sentence will likely change if we alter the order
of quantification. This might also change the truth state of a proposition.
(a) x R, y R, x
2
< y
Proof. Suppose a real number x is given. Let y = x
2
+ 1, then x
2
< y, as required.
We proved this by viewing it as an implication, “If x R, then y R, x
2
< y.”
(b) y R, x R, x
2
< y
Disproof. We demonstrate the truth of the negation, y, x, x
2
y.”
Suppose a real number y is given. Let x =
p
|
y
|
, then x
2
= y y, as required.
7
Here is an abstract justification for this heuristic. Consider a propositional function P(x): y, Q(x, y),” then
¬
x, y, Q(x, y)
¬
x, P(x)
x, ¬P(x) x, ¬
y, Q(x, y)
x, y, ¬Q(x, y)
16
Putting it all together We finish with two examples you might have seen elsewhere. For this course,
you do not have to know what these statements mean, though you do have to be able to negate them.
Examples 2.25. 1. Vectors x, y, z in the vector space R
3
are linearly independent if
a, b, c R, ax + by + cz = 0 = a = b = c = 0
In a linear algebra course, the expression a, b, c R would often be hidden. The negation of
this statement, what it means for x, y, z to be linearly dependent, is
a, b, c R, not all zero, such that ax + by + cz = 0
2. A function f : R R is said to be continuous at a R if
ϵ > 0, δ > 0 such that |x a| < δ = |f (x) f (a)| < ϵ
The negation, what it means for f to be discontinuous at x = a, is
ϵ > 0 such that δ > 0, x R with |x a| < δ and |f (x) f (a)| ϵ
The original statement contained a hidden quantifier x which became explicit upon negation.
Exercises 2.2. A self-test quiz and several worked questions can be found online.
1. Rewrite each sentence using quantifiers. Then write the negation (use words and quantifiers).
(a) All mathematics exams are hard.
(b) No football players are from San Diego.
(c) There is a odd number that is a perfect square.
2. Let P be the proposition: “Every positive integer is divisible by thirteen.”
(a) Write P using quantifiers.
(b) What is the negation of P?
(c) Is P true or false? Prove your assertion.
3. A friend claims that the sentence x
2
> 0 = x > 0” has negation x
2
> 0 and x 0.” Why
is this incorrect? What is the correct negation?
4. Consider the quantified statement
x, y, z R, (x 3)
2
+ (y 2)
2
+ (z 7)
2
> 0 ()
(a) Express () in words.
(b) Is () true or false? Explain.
(c) Express the negation of () in symbols, and then in words.
(d) Is the negation of () true or false? Explain.
5. Suppose P, Q, R are propositional functions. Compute the negations of the following:
(a) x, y, P(x) Q(y) (b) x, y, z, R(x, y, z)
17
6. Revisit Example 2.24.2. Decide whether each of the following is true or false:
(a) x R, y R, x
2
< y (b) y R, x R, x
2
< y
7. The following are statements about positive real numbers x, y. Which is true? Explain.
(a) x, y such that xy < y
2
(b) x such that y, xy < y
2
8. Which of the following statements are true? Explain.
(a) a married person x such that married people y, x is married to y.
(b) married people x, a married person y such that x is married to y.
9. Prove or disprove the following statements.
(a) For every two points A and B in the plane, there exists a circle on which both A and B lie.
(b) There exists a circle in the plane on which lie any two points A and B.
10. Consider the following proposition (you do not have to know what is meant by a field).
All non-zero elements x in a field F have an inverse: some y F for which xy = 1.
(a) Restate the proposition using quantifiers.
(b) Find the negation of the proposition, again using quantifiers.
11. A function f : R R is said to be decreasing if:
x y = f (x) f (y)
(a) State what it means for f not to be decreasing (where is the hidden quantifier?)
(b) Give an example to show that not decreasing and increasing do not mean the same thing.
12. Consider the proposition:
m, n R, m > n = m
2
> n
2
(a) State the negation of the proposition.
(b) Prove that the original proposition is false.
(c) Suppose you rewrite the proposition:
m, n A, m > n = m
2
> n
2
What is the largest collection (set) of real numbers A for which the proposition is true?
13. (Hard) Let (x
n
) = (x
1
, x
2
, x
3
, . . .) denote a sequence of real numbers.
(x
n
) diverges to means: M > 0, N R such that n > N = x
n
> M
(x
n
) converges to L means: ϵ > 0, N R such that n > N =
|
x
n
L
|
< ϵ
(a) State what it means for a sequence (x
n
) not to diverge to . Beware of the hidden quantifier!
(b) State what it means for a sequence (x
n
) not to converge to L.
(c) State what it means for a sequence (x
n
) not to converge at all.
(d) (Challenge: non-examinable) Use the definitions to prove that the sequence defined by
x
n
= n diverges to , and that the sequence defined by y
n
=
1
n
converges to zero.
18
2.3 Methods of Proof
Everything thus far has been in service to what follows: to provide the language and logical fluency
necessary to understand mathematical arguments and to begin to create your own. One can study
foundational logic much more deeply, but that is not our purpose. The real work begins now.
In mathematics, a Theorem is
8
a justified assertion of the truth of an implication P = Q. A proof,
for there can be many different approaches, is any logical argument which justifies the theorem. The
first step in analyzing or strategizing a proof is to identify the hypothesis P and conclusion Q.
There are four standard methods of proof, though a longer argument might use several.
Direct Assume the hypothesis P and deduce the conclusion Q.
9
This structure should be intuitive,
though it may help to revisit the truth table in Definition 2.5 and the tautology of Example 2.9.2.
Contrapositive Assume ¬Q and deduce ¬P: a direct proof of the contrapositive ¬Q = ¬P. This
approach works because the contrapositive is logically equivalent to P = Q (Theorem 2.11).
Contradiction Assume P and ¬Q, and deduce a contradiction. By Theorem 2.13 and Exercise 2.1.8c,
we see that P = Q is true.
Induction This has a completely different flavor: we will consider it in Chapter 5.
Each method has its advantages and disadvantages: the direct method typically has a simpler logical
flow whereas the contrapositive/contradiction approaches are useful when the negations ¬P, ¬Q
are easier to work with than P, Q themselves. All methods are equally valid, and, as we’ll see shortly,
one can often prove a simple theorem using all three approaches!
As you work through this section, pay special attention to the logical structure—to encourage this,
the mathematical level of this section is very low—and refer to the previous sections if the logical
terminology feels unfamiliar. In particular, re-read Planning and Writing Proofs (page 4).
Direct Proofs
We begin by generalizing Example 2.21.3.
Theorem 2.26. The product of any pair of odd integers is odd.
To make sense of this, we first need to identify the logical structure by writing the theorem in terms
of propositions and connectives. One way is to view the Theorem in the form P( x, y) = Q(x, y):
P(x, y) is x and y are both odd.” This is our assumption, the hypothesis.
Q(x, y) is “The product of x and y is odd.” This is what we wish to demonstrate, the conclusion.
Both propositional functions are statements about integers. The Theorem is universal (“any
pair”), and so contains a (hidden) quantifier x, y Z.
To perform a proof, we also need a clear understanding of the meaning of all necessary terms. To
keep things simple, we’ll take integer and product as understood and be explicit as to the meaning of
oddness.
8
It is sometimes awkward to fit a theorem into this format but it can always be done. Often all that is stated is the
conclusion Q, in which case P would be the assertion “All mathematics we already know/assume to be true.”
9
From now on, to assume a proposition is to suppose its truth. To suppose P is false, we “assume/suppose ¬P.”
19
A direct proof can be viewed as a proof sandwich, whose bread slices are the hypothesis and conclu-
sion (P and Q): write these down as a first step. Next define any useful terms in the hypothesis. All
that remains is to perform a simple calculation!
Proof. Let x and y be odd integers. (state hypothesis P)
There are integers k, l for which x = 2k + 1 and y = 2l + 1. Then, (definition of odd)
xy = (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1 (computation/algebra)
= 2(2kl + k + l) + 1
Since 2kl + k + l is an integer, we conclude that xy is odd. (state conclusion Q)
To make the conclusion absolutely clear, we explicitly wrote xy in the form 2(integer)+1.
Insufficient Generality Before leaving this example, it is worth quickly highlighting the most com-
mon mistakes seen in such arguments.
Fake Proof 1. x = 3 and y = 5 are both odd, hence xy = 15 is odd.
This is an example of the theorem. Since the theorem is universal, a single example is not a proof.
Fake Proof 2. Let x = 2k + 1 and y = 2k + 1 be odd. Then
xy = (2k + 1)(2k + 1) = 2(2k
2
+ 2k) + 1 is odd.
This is still insufficiently general in that it only verifies a special case (x odd = x
2
odd). There
is nothing wrong with trying out examples or sketching incomplete thoughts—indeed both are
encouraged!—but you need to be aware of when your argument isn’t sufficiently general.
For another simple direct proof, consider the sum of two consecutive integers.
Theorem 2.27. The sum of any pair consecutive integers is odd.
The theorem is again a universal claim of the form P(x, y) = Q(x, y) about two integers:
P(x, y) is x, y are consecutive integers.”
Q(x, y) is x + y is odd.”
The trick is to observe that, being consecutive, we may write y in terms of x. The proof sandwich is
still visible, though it would be hard to write down the last sentence without already having settled
on the trick, which is essentially the definition of “consecutive integers.”
Proof. Suppose we are given two consecutive integers. Label the smaller of these x, then the other
x + 1. But then their sum
x + (x + 1) = 2x + 1
is odd.
20
Proof by Contrapositive
Here is another simple result about odd and even integers.
Theorem 2.28. If the sum of two integers is odd, then they have opposite parity.
The theorem is yet another universal statement (x, y Z) of the form P(x, y) = Q(x, y):
P(x, y): x + y is odd.” Q(x, y): x, y have opposite parity.”
Parity means evenness or oddness: the conclusion is that one of x, y is even and the other odd.
Attempting a direct proof results in an immediate difficulty:
Direct Proof? Suppose x + y is odd. Then x + y = 2k + 1 for some integer k. . .
We want to conclude something about x and y individually, but the direct approach lumps them
together in the same algebraic expression.
A contrapositive argument suggests itself because the new hypothesis ¬Q, in treating x and y sepa-
rately, gives us twice as much to start with.
10
¬Q(x, y): x, y have the same parity.” ¬P(x, y): x + y is even.”
The minor remaining difficulty is that “same parity” encompasses two possibilities: x, y are either
both even, or both odd. The proof therefore contains two cases.
Proof. Suppose x and y have the same parity. There are two cases. (state hypothesis ¬Q)
Case 1: Assume x and y are both even.
Write x = 2k and y = 2l, for some integers k, l. (definition of even)
Then x + y = 2(k + l) is even. (computation)
Case 2: Assume x and y are both odd.
Write x = 2k + 1 and y = 2l + 1 for some integers k, l. (definition of odd)
Then x + y = 2(k + l + 1) is even. (computation)
In both cases x + y is even. (state conclusion ¬P)
Again observe the proof sandwich and how the proof depending on little more than the definitions
of even and odd.
When presenting a lengthier argument, consider orienting the reader by starting with the phrase,
“We prove the contrapositive.” In simple cases like the above this is unnecessary, since the logical
structure should be completely clear without such assistance. It is also unnecessary to define and
spell out the propositions P and Q or include any of the bracketed commentary. However, you
should feel free to continue this practice if you think it would aid your explanation, of if you are
nervous about your proof skills.
11
10
Warning! The contrapositive is still a universal statement: x, y Z, ¬Q(x, y) = ¬P(x, y). We are not negating the
whole theorem so do not convert to !
11
. . . and want to guarantee some partial credit!
21
For another example of a contrapositive argument, we extend the first result of this section.
Theorem 2.29. The product of two integers is odd if and only if both integers are odd.
This has the form P Q, which comprises two theorems in one: P = Q and Q = P (see Exercise
2.1.9a). A contrapositive argument for the () direction is again suggested because the right hand
side treats the two integers separately.
Proof. () We prove the contrapositive. Let x, y be integers, at least one of which is even. Suppose,
without loss of generality, that x = 2k is even. Then xy = 2ky is also even.
() This is precisely Theorem 2.26, which we’ve already proved.
Without loss of generality Often abbreviated to WLOG, this phrase is common in mathematics.
Here it saves us from performing the almost identical argument assuming y = 2l is even. WLOG is
stated when a mathematician makes a choice which does not materially affect the argument.
Proof by Contradiction
To introduce contradiction proofs consider another simple result.
12
Example 2.30. Let x be an integer. If 3x + 5 is even, then 5x + 2 is odd.
We could proceed directly according to the following sketch:
3x + 5 even = 3x odd = x odd = 5x odd = 5x + 2 odd ()
This isn’t wrong! You should believe each implication; indeed we’ve proved most of them. However
it would be nice not to rely on so many other results. A similar contrapositive approach (reverse
arrows and negate propositions in () ) would have the same weakness.
The advantage of a contradiction approach is that we have twice as much to work with: the hypoth-
esis (3x + 5 even) and the negation of the conclusion (5x + 2 even).
Proof. Suppose both 3x + 5 and 5x + 2 are even. Then their sum is also even. However,
(3x + 5) + (5x + 2) = 8x + 7 = 2(4x + 3) + 1 (†)
is odd. Contradiction (an integer cannot be both even and odd!).
Remember to mention the word contradiction at the end, so the reader knows what you’ve done.
A nice side-effect of this approach is that it suggests an alternative direct proof.
Direct Proof. For any integer x, (†) says that 3x + 5 and 5x + 2, in summing to an odd
number, have opposite parity.
The last argument in fact proves that 3x + 5 is even if and only if 5x + 2 is odd: the converse of our
claim comes for free! Look back at (): you should believe that all the arrows are reversible.
12
While what follows is a theorem, we’ll typically reserve the word for results that are worth remembering in their own
right. Examples like this are good for practice (change the numbers!), but are not individually very interesting.
22
Such variety is one of the things that makes proving theorems fun! While your choice of proof is
largely a matter of personal taste, remember your audience. The final argument is very slick but
might risk confusing a reader rather than empowering them.
13
Three Proofs of the Same Result We finish this section with three proofs of the same result. All are
based on the same factorization of a polynomial
x
3
+ 2x
2
3x 10 = (x 2)(x
2
+ 4x + 5) = (x 2)
h
(x + 2)
2
+ 1
i
and the well-known fact that ab = 0 a = 0 or b = 0 (see Exercise 14). Since the mathematics is
so simple, pay attention to and compare the logical structures.
Example 2.31. Let x be a real number. Then x
3
+ 2x
2
3x 10 = 0 = x = 2.
Direct Proof. Suppose x
3
+ 2x
2
3x 10 = 0. By factorization, (x 2)[(x + 2)
2
+ 1] = 0,
so at least one of the factors must be zero. Since (x + 2)
2
+ 1 1 > 0, we conclude that
x 2 = 0, from which x = 2.
Contrapositive Proof. Suppose x = 2. Since (x + 2)
2
+ 1 1 > 0, we see that
x
3
+ 2x
2
3x 10 = (x 2)[(x + 2)
2
+ 1] = 0
Contradiction Proof. Suppose x
3
+ 2x
2
3x 10 = 0 and x = 2. Then
0 = x
3
+ 2x
2
3x 10 = (x 2)[(x + 2)
2
+ 1]
Since x = 2, we have x 2 = 0. It follows that (x + 2)
2
+ 1 = 0. However, (x + 2)
2
+ 1 1
for all real numbers x, so we have a contradiction.
Exercises 2.3. A self-test quiz and several worked questions can be found online.
1. Prove or disprove the following conjectures.
(a) There is an even integer which can be expressed as the sum of three even integers.
(b) Every even integer can be expressed as the sum of three even integers.
(c) There is an odd integer which can be expressed as the sum of two odd integers.
(d) Every odd integer can be expressed as the sum of three odd integers.
2. For any given integers a, b, c, if a is even and b is odd, prove that 7a ab + 12c + b
2
+ 4 is odd.
3. Prove that if n is an integer greater than 1, then n! + 2 is even.
(n! = n(n 1)(n 2) ···1 is the factorial of the integer n)
4. (a) Let x Z. Prove that 5x + 3 is even if and only if 7x 2 is odd.
(b) Can you conclude anything about 7x 2 if 5x + 3 is odd?
13
The Hungarian mathematician Paul Erd
˝
os referred to simple, elegant proofs as ‘from the Book,’ as if the Almighty kept
a tome of perfect proofs. As with all matters spiritual, one person’s Book might be very different to another’s. . .
23
5. Consider the following proposition, where x is assumed to be a real number.
x
3
3x
2
2x + 6 = 0 = x = 3
(a) Is the proposition true or false? Justify your answer. Is its converse true?
(b) Repeat part (a) for the proposition x
3
3x
2
2x + 6 = 0 = x = 3.
6. Below is the proof of a result. What result is being proved?
Proof. Assume that x is odd. Then x = 2k + 1 for some integer k. Then
2x
2
3x 4 = 2(2k + 1)
2
3(2k + 1) 4 = 8k
2
+ 2k 5 = 2(4k
2
+ k 3) + 1
Since 4k
2
+ k 3 is an integer, 2x
2
3x 4 is odd.
7. Here is another proof. What is the result this time?
Proof. Assume, without loss of generality, that x = 2a and y = 2b are both even. Then
xy + xz + yz = (2a)(2b) + (2a)z + (2b)z = 2(2ab + az + bz)
Since 2ab + az + bz is an integer, xy + xz + yz is even.
8. Consider the following proof of the fact that (for m an integer) if m
2
is even, then m is even. Can
you re-write the proof so that it doesn’t use contradiction?
Proof. Suppose that m
2
is even and m is odd. Write m = 2k + 1 for some integer k. Then
m
2
= (2k + 1)
2
= 4k
2
+ 4k + 1 = 2(2k
2
+ 2k) + 1
is odd. Contradiction.
9. Here is a ‘proof that every real number x equals zero. Find the mistake.
x = y = x
2
= xy = x
2
y
2
= xy y
2
= (x y)(x + y) = (x y)y
= x + y = y
= x = 0
10. Prove or disprove: An integer n is even if and only if n
3
is even.
11. Let n and m be positive integers. Prove n
2
m is even if and only if n and m are not both odd.
12. Let x and y be integers. Prove x
2
+ y
2
is even if and only if x and y have the same parity.
13. Let n be an integer. Prove n
2
+ n + 58 is even.
14. Suppose a, b R. Prove that ab = 0 a = 0 or b = 0.
15. Numbers of the form
k(k+1)
2
, where k is a positive integer, are called triangular numbers. Prove
that n is the square of an odd number if and only if
n1
8
is triangular.
24
2.4 Further Proofs & Strategies
The arguments in this section are slightly trickier and more representative of typical mathematical
proofs. Some of these results are famous and worth knowing in their own right. We will also intro-
duce lemmas and corollaries, which are used to break up the presentation of complex results.
Proving Universal Statements
Most of the results we’ve seen thus far have been universal statements. As discussed on page 14, any
theorem P(x) = Q(x) is implicitly universal, albeit with the quantifier x being typically hidden.
Revisit Examples 2.24 on multiple quantifiers so see how these fit into our proof framework; here is
another example.
Example 2.32. x 0, y < 0 such that x
3
< y
2
View the claim as an implication x 0 = (y < 0 such that x
3
< y
2
) and prove directly.
Proof. Suppose x 0 is given. Define y =
x
3
1, then y 1 < 0 and
y
2
= x
3
+ 1 + 2
x
3
x
3
+ 1 > x
3
Notice how y, in being existentially quantified after x, is allowed to depend on x. We’ll revisit this
shortly to see what happens when we reverse the quantifiers. Remember that you might need some
scratch work to find a suitable y: you shouldn’t (yet!) expect to create such an argument in one shot.
For a more involved example of a universal result, here is a famous inequality relating the arithmetic
and geometric means of two numbers.
Theorem 2.33 (AM–GM inequality). If x, y are non-negative real numbers, then
x + y
2
xy
with equality if and only if x = y.
If your faith is wavering, first try an example: e.g.,
3+5
2
= 4
15. It should also be clear that
both sides are equal whenever y = x. The logical structure x, y 0, Q(x, y) can be viewed as an
implication P(x, y) = Q(x, y), where P(x, y) is x, y 0.” The real challenge is making sense of
Q(x, y). There are really two separate results here:
1. If x, y 0, then
x+y
2
xy
2. If x, y 0, then
x+y
2
=
xy x = y
Concentrate on the first since it is simpler. The hypothesis (x, y 0) doesn’t give us much to work
with, so it seems sensible to play with the inequality and try to get rid of the ugly square-root:
x + y
2
xy = (x + y)
2
4xy = x
2
2xy + y
2
0 = (x y)
2
0
Now we have something we believe! The question is whether we can reverse the arrows. Only the
first should give you any pause: it is here that we use the non-negativity of x, y.
25
Proof. Suppose x, y 0. Multiply out a trivial inequality:
(x y)
2
0 x
2
2xy + y
2
0 x
2
+ 2xy + y
2
4xy
(x + y)
2
4xy
x + y
2
xy
The square-root is well-defined because x, y 0, and the inequality is preserved since the square-root
function is increasing. For the second result, observe that the final inequality is an equality precisely
when all the inequalities are equalities; this is if and only if x = y.
The scratch work really helped us figure out how and where to apply the hypothesis. Notice also
how the second result came almost for free! Result 1 only need the () in the proof, but the second
result needs them all to be biconditional.
For variety, here is a contradiction proof incorporating the same calculations in a different order.
Contradiction Proof. Let x, y 0 and suppose that
x+y
2
<
xy. Since x + y 0, the second inequality
holds if and only if (x + y)
2
< 4xy. Now multiply out and rearrange:
(x + y)
2
< 4xy x
2
+ 2xy + y
2
< 4xy
x
2
2xy + y
2
< 0
(x y)
2
< 0
Contradiction (squares of real numbers are non-negative). We conclude that
x+y
2
xy.
Now suppose that
x+y
2
=
xy. Following the biconditionals in the above argument, we see that
equality holds if and only if (x y)
2
= 0, from which we recover x = y.
The AM–GM inequality in fact holds for any finite collection of non-negative numbers x
1
, . . . , x
n
:
x
1
+ x
2
+ ···+ x
n
n
n
x
1
x
2
···x
n
with equality if and only if all the x
i
are equal. Proving this is a lot harder (see Exercise 14).
Disproving Existential Statements: Non-existence Proofs
Of the four possible combinations “prove/disprove a universal/existential statement,” we’ve now
tackled three; what remains is to consider how to prove that something does not, or cannot, exist.
Recall our basic rule of negation:
¬
x, Q(x)
x, ¬Q(x)
To show that x, Q(x) is false is therefore to prove a universal statement.
14
As before (page 14), let
P(x) be the proposition x lies in the domain of Q.” We conclude that
¬
x, Q(x)
is logically equivalent to P(x) = ¬Q(x)
14
The notation x, Q(x) is discouraged because it obscures this essential fact.
26
Once viewed as an implication, any of our proof strategies might be applicable. Contradiction and
contrapositive arguments are particularly common however, since the right hand side is already a
negative statement.
Example 2.34. The equation x
17
+ 12x
3
+ 13x + 3 = 0 has no positive (real number) solutions.
Before seeing a proof, consider several ways in which this claim could be presented.
Non-existence (¬(x, Q(x))) There are no x > 0 for which x
17
+ 12x
3
+ 13x + 3 = 0.
Universal (x, ¬Q(x)) For all x > 0, we have x
17
+ 12x
3
+ 13x + 3 = 0.
Direct (P ¬Q) If x > 0, then x
17
+ 12x
3
+ 13x + 3 = 0.
Contrapositive (Q ¬P) If x
17
+ 12x
3
+ 13x + 3 = 0, then x 0.
Contradiction (P Q) x > 0 and x
17
+ 12x
3
+ 13x + 3 = 0 is impossible.
We present two very similar arguments based on the direct and contradiction structures.
Direct proof. Suppose that x > 0. But then x
17
+ 12x
3
+ 13x + 3 > 0 since all terms are
positive. We conclude that x
17
+ 12x
3
+ 13x + 3 = 0.
Contradiction proof. Assume that x > 0 satisfies x
17
+ 12x
3
+ 13x + 3 = 0. Since all terms
on the left hand side are positive, we have a contradiction.
In practice, some version of one of these arguments would likely be given without any additional
commentary. The reader is assumed to be familiar with the underlying logic without it being spelled
out. Our discussion could be considered scratch work.
Subdividing Theorems: Lemmas & Corollaries
Sometimes it is useful to break a proof into pieces, akin to viewing a computer program as a collection
of subroutines that you combine for some greater purpose. Often the intention is to improve the
readability of a difficult/complex argument, but you may also wish to (de-)emphasize the relative
importance of certain results. Mathematics does this by using lemmas and corollaries.
Lemma: A theorem whose importance you want to downplay or which will be used when
proving a more significant result.
Corollary: A theorem which follows quickly once you understand another result, perhaps
as a special case or by modifying the proof in some small way.
Presentation style varies hugely between authors and journals: some reserve theorem only for the
most important results, with everything else presented as a lemma or corollary, while others never
use these terms (or just call everything a proposition!). Regardless, lemmas and corollaries are useful
to have in your toolkit if readability is your goal.
In preparation for our next, much more important, result, here is a simple lemma.
Lemma 2.35. Suppose n is an integer. Then n
2
is even n is even.
At this stage, you should be able to prove this yourself. This is really just a special case of Theorem
2.29: if you’re completely unsure how to start, revisit that result, and the rest of Section 2.3.
27
Irrational Numbers
Since their definition is inherently negative, irrational numbers provide good examples of non-
existence/contradiction arguments. They are also interesting in their own right!
Definition 2.36. A real number x is rational if it may be written in the form x =
m
n
for some integers
m, n. A real number is irrational if no such integers exist.
You likely know of a few irrational numbers (
2, π, e), but how do we prove that a given number is
irrational? Our next result is very famous, with versions dating back at least to Aristotle (c. 340 BCE).
Theorem 2.37.
2 is irrational.
We must disprove the existence claim m, n Z,
2 =
m
n
. As before, consider several restatements:
Non-existence There are no integers m, n for which
2 =
m
n
.
Universal For all integers m, n, we have
2 =
m
n
.
Direct If m, n Z, then
2 =
m
n
.
Contrapositive If
2 =
m
n
, then m, n are not both integers.
Contradiction m, n Z and
2 =
m
n
is impossible.
Can you see the obvious drawbacks of a direct or contrapositive approach? We prove by contradic-
tion, while outsourcing a repeated step to the () direction of Lemma 2.35 to improve readability.
Proof. Suppose that m, n Z and that
2 =
m
n
. Without loss of generality, assume that m, n have no
common factors. Cross-multiply and square:
m
2
= 2n
2
is even = m is even (Lemma 2.35)
whence m = 2k for some integer k. But then
2n
2
= m
2
= 4k
2
= n
2
= 2k
2
is even = n is even (Lemma 2.35)
We see that m and n have a common factor of 2. Contradiction.
The major difficulty lies in the assumption that m, n have no common factors. In the same way that
we can simplify
4
6
=
2
3
, our assumption is without loss of generality because it costs us nothing once we
assume
2 =
m
n
is rational. It is crucial to appreciate that we aren’t contradicting the assumption that
m, n have no common factors, lest our calculation continue forever without resolution!
m
2
= 2n
2
= n
2
= 2k
2
= k
2
= 2l
2
= ···
The irrationality of
3,
3
2, etc., can be proved similarly (π and e are much harder!). Now we have
the theorem, it is easily applied to demonstrate the irrationality of many other numbers.
Example 2.38. Suppose that
2 5
3 = x were rational: m, n Z such that x =
m
n
. Then
75 = (5
3)
2
= (
2 x)
2
= 2 + x
2
2
2x =
2 =
x
2
73
2x
=
m
2
73n
2
2mn
Otherwise said,
2 is rational: contradiction.
28
Non-constructive Existence Proofs
Every existence proof we’ve seen so far has been constructive: we exhibit/construct an explicit example
x for which Q(x) is true. Sometimes, however, this is expecting a bit too much. It is often far easier
to show the existence of something without explicitly stating what it is. We present two famous
examples of this situation.
Theorem 2.39. There are irrational numbers a, b for which a
b
is rational.
Proof. Consider the number x = (
2)
2
. There are two possibilities:
1. x is rational. Let a = b =
2.
2. x is irrational. Let a = x and b =
2 and apply the usual exponential laws to see that
a
b
=
(
2)
2
2
= (
2)
2·
2
= (
2)
2
= 2
In either case, a, b are irrational and a
b
rational.
The proof is very sneaky: it does not provide an explicit example and does not tell us whether (
2)
2
is rational. In fact this number isn’t rational, though demonstrating it is massively harder.
15
We finish with a particularly famous example of a non-constructive existence proof found in Euclid’s
Elements (300 BCE), the most influential textbook of mathematical history. As ever, we need a solid
definition before we try to prove anything.
Definition 2.40. An integer 2 is prime if the only positive integers it is divisible by are itself and 1.
The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, . . . It follows, though it is not completely obvious, that
every integer 2 is either prime or a product of primes (composite). In particular, every integer 2
is divisible by at least one prime. We now state Euclid’s result, and prove it by contradiction.
Theorem 2.41 (Elements, Book IX, Prop. 20). There are infinitely many prime numbers.
Proof. Assume there are exactly n primes p
1
, . . . , p
n
and define the integer
Π := p
1
··· p
n
+ 1
Certainly Π is divisible by some prime p
i
(in our list by assumption!), as is the product p
1
··· p
n
. But
then the difference
1 = Π p
1
··· p
n
is divisible by p
i
, contradicting the fact that p
i
2.
15
If you’re interested, look up the Gelfond–Schneider Theorem (1934), Hilbert’s Seventh Problem, and what they say
about algebraic and transcendental numbers. Such ideas are far beyond the level of this text!
29
Exercises 2.4. A self-test quiz and worked questions can be found online.
1. Prove or disprove:
(a) There exist integers m and n such that 2m 3n = 15.
(b) There exist integers m and n such that 6m 3n = 11.
2. Prove or disprove: There exists a line L in the plane such that, for all points A, B in the plane,
we have that A, B lie on L.
3. Prove: For every positive integer n, the integer n
2
+ n + 3 is odd and greater than or equal to 5.
4. Let p be an odd integer. Prove that the equation x
2
x p = 0 has no integer solutions.
5. Prove or disprove:
2
7 is rational.
6. Prove or disprove the following conjectures about real numbers x, y.
(a) If 3x + 5y is irrational, then at least one of x and y is irrational.
(Be careful! This isn’t a logical ‘and’: what happens when you negate?)
(b) If x and y are rational, then 3x + 4xy + 2y is rational.
(c) If x and y are irrational, then 3x + 4xy + 2y is irrational.
7. Prove by contradiction: if x and y are positive real numbers, then
x + y =
x +
y.
How would you change things to make a contrapositive argument?
8. Prove that between any two distinct rational numbers there exists another rational number.
9. Consider the proposition:
For any non-zero rational r and any irrational number t, the number rt is irrational.
(a) Translate this statement into logic using quantifiers and propositional functions.
(b) Prove the statement.
10. (a) An integer n is not divisible by 3 if and only if k Z for which n = 3k + 1 or 3k 1.
Prove that if n
2
is divisible by 3, then n is divisible by 3.
(b) Prove that
3 is irrational.
(c) Prove that
3
2 is irrational. (Hint: revisit Exercise 2.3.10)
11. (Recall Example 2.34) You are given the following facts:
All polynomials are continuous.
(Intermediate Value Theorem) If f is continuous on the interval [a, b] and L lies between
f (a) and f (b), then there is some x in the interval (a, b) for which f (x) = L.
If f
(x) > 0 on an interval, then f is an increasing function.
Use these facts to give formal proofs of two claims that should be familiar from calculus:
(a) x
17
+ 12x
3
+ 13x + 3 = 0 has a solution x in the interval (1, 0).
(b) x
17
+ 12x
3
+ 13x + 3 = 0 has exactly one real number solution x.
30
12. The real numbers satisfy the Archimedean property:
For any x, y > 0, there exists a positive integer n such that nx > y.
(a) Use the Archimedean property to show that there are no positive real numbers which are
less than
1
n
for all positive integers n.
(b) Consider the following ‘proof of the fact that every real number is less than some positive
integer:
Proof. Consider a real number x. For example, x = 19.7. Then x < 20 and 20 is a positive
integer.
What is wrong with this argument? Give a correct proof.
(c) Suppose x < y are real numbers. Prove that there exists a positive integer n for which
n(y x) > 1.
(d) (Hard) Prove: x, y R with x < y, m, n Z for which nx < m < ny. Hence conclude
an extension of Exercise 8: between any two real numbers there exists a rational number.
13. Suppose x, y, z 0 satisfy x + y + z = 1. Use the AM–GM inequality (two-variable or full
version) to answer the following.
(a) What is the largest possible value of xyz and when does it occur?
(b) (Hard) Prove that (1 x)(1 y)(1 z) 8xyz.
14. (Hard) We prove the full AM–GM inequality.
(a) When n = 3, try mimicking our earlier approach by cubing the desired inequality. Why
does this seem unwise?
(b) Prove that x e
x1
for all real numbers x, with equality if and only if x = 1.
(Hint: Consider f (x) = e
x1
x and apply a derivative test from calculus)
(c) Let µ =
x
1
+x
2
+···+x
n
n
be the arithmetic mean. Apply part (b) to each expression x =
x
i
µ
to
conclude that x
1
···x
n
µ
n
and hence complete the proof.
31
3 Divisibility and the Euclidean Algorithm
In this section we introduce congruence, which generalizes the notion of an integer’s parity (even-
ness/oddness). The study of congruence is of fundamental importance to the sub-discipline of num-
ber theory, and provides some of the most straightforward examples of groups and rings. We will
cover the basics in this section, returning in Chapter 7 for more formal observations.
3.1 Divisors, Remainders and Congruence
Definition 3.1. Let m, n be integers. The proposition n | m is read n divides m, and means
k Z such that m = kn
We could also say that n is a divisor of m,” that m is divisible by n,” or that m is a multiple of n.”
The negated symbol is read does not divide.
Examples 3.2. 1. We write 4 | 20 since 20 = 4 ×5. The same equation also says that 5 | 20.
2. The proposition 9 7 is read 9 does not divide 7. It is shorthand for ¬(9 | 7).
When integers do not divide, there is a remainder left over. Your study of remainders likely goes back
to elementary school when you first learned division: for instance,
16
33 ÷5 = 6 r 3 (“6 remainder 3”)
An important foundational result says that unique remainders always exist.
Theorem 3.3 (Division Algorithm). Suppose m, n Z with n positive. Then there exist unique
integers q, r (the quotient and remainder) for which
m = qn + r and 0 r < n
In elementary school language, m ÷n = q r r.
Examples 3.4. 1. Given m = 23 and n = 7, we have 23 = 3 · 7 + 2; that is q = 3 and r = 2.
2. If m = 11 and n = 3, then 11 = (4) ·3 + 1; that is q = 4 and r = 1.
3. The formula m = 6q + 4, where q Z, describes all integers with remainder 4 on division by 6.
An algorithm is typically a computational process: if m > 0 one could view this as the repeated sub-
traction of n from m until the result r = m qn satisfies 0 r < n. A rigorous proof requires
foundational ideas related to induction to which we will return in Chapter 5. For our current pur-
poses, we just need to know that remainders exist. Indeed our next step is to find a way to compare
remainders without explicitly invoking the division algorithm.
16
The common meaning of divide is to apportion a quantity equally. Thus to divide 33 apples between 5 people, each
person gets 6 apples and 3 are left over. In grade school mathematics, fractions come much later.
32
Definition 3.5. Let a, b and n be integers with n positive. The proposition
a b (mod n) a is congruent to b modulo n
means that a and b have the same remainder on division by n. The integer n is called the modulus.
Examples 3.6. Consider remainders modulo 3 (division by 3).
1. We write 7 10 (mod 3), since 7 = 2 ·3 + 1 and 13 = 4 ·3 + 1 have the same remainder (r = 1).
2. We write 6 10 (mod 3), since 6 = 2 · 3 + 0 and 17 = 5 ·3 + 2 have different remainders.
Calculating using the division algorithm is tedious. Our next result is crucial in that it permits the
direct comparison of remainders. This can be treated as an equivalent definition of congruence.
Theorem 3.7. a b (mod n) n | (b a) b = a + kn for some integer k
Proof. The second biconditional is nothing more than an application of Definition 3.1:
n | (b a) k Z such that b a = kn
b = a + kn for some integer k
Before presenting direct arguments for each direction of the first biconditional, it is helpful to intro-
duce notation from the division algorithm:
a = q
1
n + r
1
b = q
2
n + r
2
0 r
1
, r
2
< n
= b a = (q
2
q
1
) n + (r
2
r
1
) ()
() If a b (mod n), then a, b have the same remainder r
1
= r
2
. But then () says that n | (b a).
() Assume that n | (b a) so that b a = kn for some integer k. By (), we see that
r
2
r
1
= (b a) (q
2
q
1
) n = (k q
2
+ q
1
) n
is divisible by n. Since the remainders satisfy 0 r
1
, r
2
< n, we moreover see that
n < r
2
r
1
< n
The only possibility is r
2
r
1
= 0. Otherwise said, a, b have the same remainder: a b (mod n).
If you’re having trouble with the last step, think about an example! Suppose n = 26 and write
x = r
2
r
1
. Hopefully you believe that x = 0 is the only integer satisfying the two conditions,
x is divisible by 26 and 26 < x < 26
Since the result is abstract, it is good to recap the relationship between congruence and divisibility.
Each a Z is congruent to exactly one of the integers 0, 1, 2, . . . , n 1 modulo n: its remainder.
a is divisible by n if and only if a 0 (mod n).
33
Examples 3.8. 1. We describe all integers x which are congruent to 7 on division by 11:
x 7 (mod 11) 11 | (x 7) x 7 = 11k x = 11k + 7
for some integer k.
2. To get more of a feel for the notation, consider the following conjectures:
(a) a 8 (mod 6) = a 2 (mod 3)
(b) a 2 (mod 3) = a 8 (mod 6)
Conjecture (a) is true. If a 8 (mod 6), then a = 6k + 8 for some integer k, from which
a = 6k + 8 = 3(2k + 2) + 2 = a 2 (mod 3)
Conjecture (b) is false. The counter-example a = 5 disproves this (universal) claim:
5 2 (mod 3) and 5 8 (mod 6)
Modular Arithmetic
Remainders have a natural arithmetic that is very similar to that of the real numbers. We the same
symbols; even the congruence symbol looks a bit like an equals sign!
17
Apart from being fun,
modular arithmetic has many applications, including cryptography and data security: cell-phones
and computers perform millions of these calculations every day! Here are the basic rules, which
generalize of most of the results we proved in Section 2.3.
Theorem 3.9. Suppose a, b, c, d are integers and that n is some modulus. Then,
1. If a c and b d modulo n, then
a ± b c ± d and ab cd (mod n)
2. The usual associative, commutative and distributive laws of arithmetic hold for congruences:
a + (b + c) (a + b) + c a + b b + a a(b + c) ab + ac
a(bc) (ab)c ab ba
The theorem says that the operations ‘take the remainder and ‘add/subtract/multiply’ can be per-
formed in any order or combination, the result will be the same.
Example 3.10. Find the remainder when 29 + 14 is divided by 6. We do this in two ways:
(a) First find the sum 43, then compute its remainder: 43 1 (mod 6) since 6 | (43 1).
(b) Alternatively, we could find the remainder of each component and then add:
29 + 14 5 + 2 7 1 (mod 6)
17
This is no accident. In Chapter 7 we’ll see that congruence is an important example of an equivalence relation: a general-
ized notion of equality. Indeed, two integers are congruent if and only if something about them is equal: their remainders!
34
Proof. 1. We prove the multiplication rule. Suppose that a c and b d. By Theorem 3.7, we
have c = a + kn and d = b + ln for some integers k, l. Now compute:
cd ab = (a + kn)(b + ln) ab = (bk + al + kln)n
is divisible by n, whence ab cd. The addition/subtraction argument is almost identical.
2. The associative, commutative and distributive laws hold because x = y = x y (mod n),
regardless of n (equal numbers have the same remainder!).
The ability to take remainders before adding and multiplying is remarkably powerful, and allows us
rapidly to perform some surprising calculations.
Examples 3.11. 1. Find the remainder when 37
423
is divided by 10.
The sheer size of 37
423
makes this appear impossible at first glance.
18
Instead we think about
the rules of arithmetic modulo 10. Since 37 7 3 (mod 10), we see that
37 ·37 (3) · (3) 9 1 (mod 10)
This is more promising, for we can use it to simplify the original expression:
37
423
(3) · (3) ···(3)
| {z }
423 times
( 3)
2
211
( 3) (1)
211
( 3) 3 (mod 10)
2. Here we compute modulo n = 6:
7
9
+ 14
3
1
9
+ 2
3
1 + 8 9 3
It would have been madness to compute 7
9
+ 14
3
= 40356351 before finding the remainder!
3. Find the remainder when 124
12
·65
49
is divided by 11.
This needs several steps and simplifications. Since 124 = 11
2
+ 3 and 65 = 11 ·6 1, we write
124
12
·65
49
3
12
·(1)
49
(3
3
)
4
·(1)
(27
4
) (5
4
)
(25
2
) (3
2
) 2 (mod 11)
When performing these calculations:
Replace each integer by something small with the same remainder: 37 3(mod 10) is more
helpful than 37 7 (mod 10), since powers of 3 are much easier to work with.
The base of an exponential expression can be reduced, but not the exponent: 17
23
3
23
(mod 7)
is correct, but 3
23
3
2
(mod 7). Exponentiation is just shorthand for repeated multiplication.
18
Using logarithms, a pocket calculator will tell you that 37
423
2.2 × 10
663
has 663 digits! This is no help since what
we want is the units digit, not its largest few significant figures.
35
Application: On what day were you born?
While we all know our date of birth, most of us do not know on which day of the week we were born.
You can answer this question quite easily (perhaps in your head!) using modular arithmetic.
Since 365 1 (mod 7), a standard year advances the calendar one weekday.
Each leap year
19
advances the calendar an additional day.
Can you figure the weekday today’s date in your year of birth? Thinking about the length of each
month modulo 7, you should also be able to find your birthday.
Example 3.12. Paul Revere was born January 1
st
, 1735, in Boston. Given that January 1
st
, 2024 was a
Monday, find the weekday of Revere’s birth.
The dates differ by 289 years, in which time there have been
288
4
2 = 70 leap years (not 1800 and
1900). The calendar has therefore advanced 289 + 70 2 weekdays: Revere was born on a Saturday.
Division and Congruence Equations
Division in modular arithmetic behaves in unexpected ways. We’ll consider this further in Exercise
3.2.15, but for the present it is safest to convert congruences to statements about integers.
Examples 3.13. 1. Even when there is a common factor, dividing both sides is perilous. For instance
42 12 (mod 10) = k Z, 42 12 = 10k = k Z, 21 6 = 5k
= 21 6 (mod 5)
Division by 2 also divided the modulus! If we hadn’t divided the modulus, the result would be
false: 21 6 (mod 10).
2. Congruence equations are much harder to solve than standard equations. For instance, we
cannot solve 2x 7 (mod 9) by division: x
7
2
is meaningless since
7
2
is not an integer!
It won’t always work, but in this case sneakily multiplying by 5 solves the problem:
2x 7 = 10x 35 = x 8 (mod 9)
Exercises 3.1. A reading quiz and several questions with linked video solutions can be found online.
1. Prove, using the definition of “divides,” that n | a and n | b = n | (a + b).
2. Let a, b, c be integers. Prove or disprove each of the following claims:
(a) a | b and b | c = a | c (b) a = b a | b and b | a
(b) a | b and a | c = a | bc (d) a | c and b | c = ab | c
3. List all integers x for which x 3 (mod 5) and 10 x 20.
4. Use the division algorithm to prove that if p is an odd prime, then p 1 or p 3 (mod 4).
19
Leap years occur whenever the year is divisible by 4. Among centuries, only years divisible by 400 are leap years: thus
1900 wasn’t a leap year but 2000 was. This is only practical back to the invention of the Gregorian calendar in the 1600s.
36
5. Prove the first part of Theorem 3.9: if a c and b d, then a + b c + d (mod n).
6. Find a positive integer n and integers a, b such that a
2
b
2
(mod n) but a ≡ b (mod n).
7. Check explicitly that 3
23
3
2
(mod 7). (Hint: 3
3
= 27 . . .)
8. Compute the following remainders—use a calculator to help!
(a) 12
9
+ 19
24
on division by 10.
(b) 30
10
on division by 13.
(c) 17
251
·23
12
19
41
on division by 5. (Hint: 17 2 and 2
2
1 (mod 5))
(d) (Hard) 12
10
+ 2
36
·18
12
on division by 141. (Hint: what nice number is close to 141?)
9. Prove that 3 | (4
n
1) for all positive integers n.
10. Let n be an integer. Prove that exactly one of n, n + 2 and n + 4 is divisible by 3.
11. (a) Let n be a positive integer. Prove that n is congruent to the sum of its digits modulo 9.
(Hint: e.g. 345 = 3 ·10
2
+ ···)
(b) Is the integer 123456789 divisible by 9?
12. Describe all integers x which satisfy the congruence equations:
(a) 3x 2 (mod 8) (b) 7x 28 (mod 42).
13. Abraham Lincoln was born February 12
th
, 1809. On what day of the week was this?
(Start by looking up the day for February 12
th
this year)
14. Let n be an integer.
(a) Prove: n
2
0 or 1 (mod 3). (Hint: prove by cases)
(b) Prove: n
2
0 or 1 (mod 4).
(c) Find all possible remainders of n
2
on division by 7.
(d) Find all possible remainders of n
3
on division by 7.
15. Use some part(s) of Exercise 14 to prove the following.
(a)
4m + 6 is not an integer, for any integer m 1.
(b) Any number which is simultaneously a square and a cube must be of the form 7k or 7k + 1
for some integer k.
16. Let n be an integer 2 and consider numbers of the form 11 ···11
| {z }
n times
(a) Prove every such number can be written as 4k + 3 for some k Z.
(b) Prove that no such number is a perfect square.
17. Fermat’s Little Theorem states that if p is prime and a ≡ 0 (mod p), then a
p1
1 (mod p).
(a) Use Fermat’s Little Theorem to prove that b
p
b (mod p) for any integer b.
(b) Prove that if p is prime then p | (2
p
2).
(c) Verify that 341 | (2
341
2). What does this say about the converse to part (b)?
37
3.2 Greatest Common Divisors and the Euclidean Algorithm
A basic goal for number theorists is to find integer solutions to equations. For instance:
Are there any integer points on the line with equation 9x 21y = 6? That is, does the
equation 9x 21y = 6 have any solutions, where both x, y are integers?
You might start by sketching both lines (lined graph paper will help). What do you observe? If there
are integer points, do they seem to follow any pattern?
In this section we will see how to solve all such linear Diophantine equations.
20
The method introduces
a famous procedure dating at least to Euclid’s Elements (c. 300 BCE).
Definition 3.14. Let a and b be integers, not both zero. Their greatest common divisor gcd(a, b) is the
largest (positive) divisor of both a and b. We say that a and b are relatively prime if gcd(a, b) = 1.
Example 3.15. The positive divisors of a = 60 and b = 90 are listed in the table. The greatest common
divisor gcd( 60, 90) = 30 is plainly the largest number common to both rows.
a 1 2 3 4 5 6 10 12 15 20 30 60
b 1 2 3 5 6 9 10 15 18 30 45 90
Listing divisors is very inefficient given large integers. This is where Euclid rides to the rescue.
Theorem 3.16 (Euclidean Algorithm). Let a > b be positive integers. We construct a decreasing
sequence of integers b = r
0
> r
1
> r
2
> ···
1. Apply the division algorithm (Theorem 3.3): a = q
1
b + r
1
with 0 r
1
< b
2. If r
1
> 0, apply the division algorithm again: b = q
2
r
1
+ r
2
with 0 r
2
< r
1
3. If r
2
> 0, apply again: r
1
= q
3
r
2
+ r
3
with 0 r
3
< r
2
4. While r
i
> 0, keep repeating the division algorithm, dividing each r
i+1
by r
i
.
The algorithm eventually terminates with a remainder of zero: some r
t+1
= 0. The greatest common
divisor is the last non-zero remainder: gcd(a, b) = r
t
.
Exercise 8 provides a proof. If either of a, b are negative just ignore the signs: for instance gcd(4, 34) =
gcd( 34, 4) = 2.
Example 3.17. We compute gcd(1260, 750) using the Euclidean algorithm. Note how each line is a
single instance of the division algorithm a = qb + r and how the remainders move diagonally at
each step. For this first example, we also summarize the data in a table.
a q b r
1260 = 1 ×750 + 510 1260 1 750 510
750 = 1 ×510 + 240 750 1 510 240
510 = 2 ×240 + 30 510 2 240 30
240 = 8 ×30 + 0 240 8 30 0
Theorem 3.16 says that gcd(1260, 750) = 30, the last non-zero remainder.
20
Equations with integer coefficients and solutions honor the number theorist Diophantus of Alexandria (3
rd
C. CE).
38
Reversing the Algorithm
To apply the Euclidean algorithm to our motivational problem of integer points on lines, we run it
backwards. Start with the penultimate line of the algorithm and move upwards, substituting remain-
ders one at a time. The result is an expression gcd(a, b) = ax + by for some integers x, y.
Example (3.17, cont). We find integers x, y such that 1260x + 750y = 30
= gcd(1260, 750)
.
Start by expressing 30 using the third step of the algorithm and work upwards:
30 = 510 2 ×240 (3
rd
/penultimate line)
= 510 2(750 510) = 3 × 510 2 ×750 (2
nd
line)
= 3(1260 750) 2 ×750 (1
st
line)
= 3 ×1260 5 ×750
Rearranging, we see that x = 3 and y = 5 satisfy the equation 1260x + 750y = 30. To simplify,
divide everything by 30 to see that ( 3, 5) is an integer point on the line 42x + 25y = 1.
This process of reversing the algorithm works in general, yielding a very powerful result.
Corollary 3.18 (B´ezout’s Identity). Given integers a, b, not both zero, x, y Z such that
gcd(a, b) = ax + by
If either a, b are negative, apply the algorithm to
|
a
|
,
|
b
|
and correct the signs afterwards.
Corollary 3.19. Suppose a, b, c are integers for which gcd(a, b) = 1 and a | bc. Then a | c.
Proof. By B
´
ezout’s identity, x, y Z for which ax + by = 1, whence acx + bcy = c. The left hand
side is now a multiple of a.
Examples 3.20. 1. The claim a | c and b | c = ab | c is, in general, false (e.g. a = b = c = 2).
However: Suppose c = 2m = 3n for some integers m, n. Since gcd(2, 3) = 1 and 2 | (3n), we
see that 2 | n. Thus n = 2k for some k Z and c = 6k. We conclude:
2 | c and 3 | c = 6 | c
Though we could have done this example without heavy machinery (use Theorem 2.29), B
´
ezout
proves that the general claim holds whenever a, b are coprime.
2. (Example 3.17, mk. III) We know that (x
0
, y
0
) = (3, 5) solves the equation 1260x + 750y = 30
(equivalently 42x + 25y = 1). Suppose (x, y) is any other integer solution and observe that
42(x x
0
) + 25(y y
0
) = 1 1 = 0 = 42(x x
0
) = 25(y y
0
)
Since gcd( 42, 25) = 1, the corollary says 42 | (y y
0
). Write y y
0
= 42t for some t Z, then
42(x x
0
) = 25 ·42t = x x
0
= 25t
We’ve therefore found all integer solutions to the original equation:
x = 3 25t, y = 5 + 42t where t Z
39
The method in the example works for all solvable linear Diophantine equations.
Theorem 3.21. Let a, b, c be integers where a, b are not both zero, and let d = gcd(a, b).
1. The equation ax + by = c has an integer solution (x, y) if and only if d | c.
2. If a solution exists, then there are infinitely many of them:
x = x
0
b
d
t, y = y
0
+
a
d
t ()
where t Z and (x
0
, y
0
) is some fixed solution (say as supplied by the Euclidean algorithm).
Warning! If c = d = gcd(a, b), you will need to scale the integers obtained in B
´
ezout’s identity to
find an initial solution (x
0
, y
0
): see below.
Example 3.22. We compute gcd(123, 78) = 3: remainders are underlined for clarity.
123 = 1 ×78 + 45
78 = 1 ×45 + 33
45 = 1 ×33 + 12
33 = 2 ×12 + 9
12 = 1 ×9 + 3
9 = 3 ×3 + 0
=
3 = 12 9
= 12 (33 2 × 12) = 3 × 12 33
= 3(45 33) 33 = 3 ×45 4 ×33
= 3 ×45 4(78 45) = 7 ×45 4 ×78
= 7(123 78) 4 ×78
= 7 ×123 11 ×78
(a) Since 3 8, the equation 78x + 123y = 8 has no integer solutions.
(b) By B
´
ezout’s identity, the equation 123x 78y = 6 has a particular solution
(x
0
, y
0
) = (14, 22) (Warning: Multiply ( 7, 11) by 2)
All integer solutions to the equation are then given by
(x, y) = (14, 22) +
78
3
,
123
3
t =
14 + 26t, 22 + 41t
, where t Z
Linear Congruence Equations
We began to consider linear congruence equations in Example 3.13. The “points on lines” method
also applies in this context. To see why, observe that
ax c (mod n) y Z such that ax = ny + c
The Theorem tells us when we can solve the right hand side, and how. To solve the congruence
equation, we just need to extract the x-part.
Examples 3.23. 1. To solve 123x 6 (mod 78) is to find a solution to the equation 123x = 78y 6.
By the above, all solutions have the form x = 14 + 26t. Otherwise said
123x 6 (mod 78) = x 14 12 (mod 26)
2. The congruence equation 4x 6 (mod 20) has no solutions. If it did, then the linear equation
4x = 20y + 6 would have integer solutions, but it doesn’t: gcd(4, 20) = 4 does not divide 6.
40
3. Here is a slightly different approach for 7x 11 (mod 23). By applying the algorithm,
gcd( 23, 7) = 1 = 7 ·10 23 · 3 = 7 ·10 1 (mod 23)
The original equation may now be solved via multiplication:
7x 11 = x 10 ·7x 110 18 (mod 23)
In this context, division by 7 really means multiplication
21
by 10.
Exercises 3.2. A reading quiz and several questions with linked video solutions can be found online.
Some of these questions are tricky, particularly the last few, and are included to give you a taste of
upper-division number theory and abstract algebra.
1. Use the Euclidean algorithm to compute the greatest common divisors.
(a) gcd( 20, 12) (b) gcd(100, 36) (c) gcd(207, 496)
2. For each part of Exercise 1, find integers x, y which satisfy B
´
ezout’s identity gcd(a, b) = ax + by.
3. Describe all the integer points on the line 9x 21y = 6 using Theorem 3.21.
4. (a) Use Theorem 3.21 to show that there are no integer points on the line 4x + 6y = 1.
(b) Give an elementary proof (without using the Theorem) of part (a)?
5. Find all integer points (x, y) on the following lines, or show that none exist.
(a) 16x 33y = 2 (b) 122x + 36y = 3
(c) 303x + 204y = 6 (d) 324x 204y = 12
6. (a) Show that there exists no integer x such that 3x 5 (mod 6).
(b) Find all solutions x to the congruence equation 12x 1 (mod 17).
7. Five people each take the same number of candies from a jar. Then a group of seven people
does the same: in so doing they empty the jar. If the jar originally contained 93 candies, can
you be sure how much candy each person took?
8. We complete the proof of the Euclidean algorithm (Theorem 3.16).
(a) Suppose a > b > r
1
> r
2
··· is a sequence of non-negative integers. Why must there be
only finitely many terms? This shows that the algorithm terminates with some r
t+1
= 0.
(b) Suppose that a, b, q, r are integers satisfying a = qb + r. Prove that gcd(a, b) = gcd(b, r).
(You cannot use B´ezout’s identity to do this, since B´ezout is a corollary of the algorithm!)
(c) Argue that gcd(a, b) = r
t
.
9. Suppose m = 0. What is gcd(m, 0)? Why? Why is B
´
ezout’s identity trivial in this situation?
10. Use B
´
ezout’s identity to prove that if k | a and k | b, then k | gcd(a, b).
21
In future studies, you’ll refer to 10 as the multiplicative inverse of 7 in the ring Z
23
, and write 7
1
= 10 (see Exercise 18).
41
11. Prove: gcd(m, n) = 1 x, y Z such that mx + ny = 1.
(Hint: One direction follows from ezout’s identity, but the other. . . )
12. Use Example 3.20.1 to prove the following.
(a) Let n 3 be an odd number. Show that n 1 (mod 3) = n 1 (mod 6).
(b)
1
6
n(n + 1)(2n + 1) is an integer.
13. Let a, b, p Z. Recall Definition 2.40: the only positive divisors of a prime are itself and 1.
(a) Suppose p is prime and that p | ab. Prove that p | a or p | b.
(Hint: if p a, use Corollary 3.19)
(b) Suppose p 2 is an integer with the property that a, b Z, p | ab = p | a or p | b.
Prove that p is prime.
(Hint: prove the contrapositive)
14. (Hard) Show that if a is relatively prime to both b and c then it is relatively prime to bc.
(Hint: suppose d | a and d | bc and try to prove that d = ±1)
15. The general rule for congruence division is as follows:
ac bc (mod n) = a b (mod
n
gcd(c,n)
)
(a) Use the rule to find all solutions to the congruence equation 22x 66 (mod 77).
(b) We prove the rule. Let d = gcd(c, n).
i. Explain why gcd(
c
d
,
n
d
) = 1
ii. If ac bc (mod n), prove that
n
d
| (a b).
16. (a) Prove part 1 of Theorem 3.21 using B
´
ezout’s identity.
(b) Prove part 2 by mimicking the method in Example 3.17, (mk. III).
17. (Hard) Apply the discussion of the Euclidean algorithm and linear equations to the following.
(a) Complete the table.
If n is a positive integer, make a conjecture for the
value of gcd( 2n, n + 1) and prove it.
n 1 2 3 4 5 6
gcd( 2n, n + 1)
(b) Show that gcd( 5n + 2, 12n + 5) = 1 for every integer n.
18. The set of remainders Z
n
= {0, 1, 2, . . . , n 1} is called a ring when equipped with addition
and multiplication modulo n. We say that b Z
n
is an inverse of a Z
n
if
ab 1 (mod n)
(a) Show that 2 has no inverse modulo 6.
(b) Prove that a has an inverse modulo n if and only if gcd(a, n) = 1. Conclude that the only
sets Z
n
for which all non-zero elements have inverses are those for which n is prime.
42
4 Sets and Functions
Sets are the fundamental building blocks of mathematics, providing the language necessary for de-
scribing mathematical objects and for grouping objects together according to shared characteristics.
Understanding how to read and effectively employ set notation is our primary focus. The mathe-
matical discipline of set theory is, however, far more ambitious than this. Set theorists define all basic
mathematical objects—numbers, addition, functions, etc.—purely in terms of sets, an impractical ap-
proach for most working mathematicians, most of the time.
22
We will only scratch the surface of this.
Indeed long before one can accept that such an approach has its place in mathematics, a significant
level of familiarity with sets and their basic operations is necessary.
4.1 Set Notation and Subsets
Without any attempt to define the meaning of object, we start with a na
¨
ıve definition.
Definition 4.1. A set is a collection of objects, its elements or members.
The notation x A is read x is an element/member of the set A,” or
more often simply x is in A.” Otherwise said, x is an object in the
collection labelled A.
If y is a member of some other set, but not of A, we write y / A (“y is
not in A”).
A
a
1
a
2
a
3
x
y
As in the definition, it is typical to use upper-case letters (A, B, C, . . .) for abstract sets and lower-case
letters for their elements.
Venn diagrams are useful for visualizing abstract sets. A set is represented by a region in the plane,
with elements depicted by dots. The diagram in the definition represents a set A comprising at least
four elements a
1
, a
2
, a
3
and x. The element y does not lie in A.
Example 4.2. Let A be the set of (names of) US states. Then Michigan A and Saskatchewan / A.
Definition 4.3. Let A and B be sets.
1. Sets are equal, written A = B, if they have precisely the same elements.
2. A is a subset of B, written A B, if every element of A is also an
element of B.
3. A is a proper subset of B if A B and A = B. To stress this, we’d write
A B. The Venn diagram on the right represents a proper subset.
A
B
The following observations are simply translations of the definition:
1. Equality: A = B A B and B A.
2. Subset: A B
x A = x B
x A, x B
3. Not a subset: A B x A for which x / B.
22
Within axiomatic set theory it can take over 100 pages to justify writing 1 + 1 = 2. The difficulty is that rigorous
definitions—using sets—are first required of the notions one, two, equals and add. . .
43
Roster & Set-Builder Notation
Roster notation is the most basic way to describe the elements of a set: simply list the elements in any
order between curly brackets {, }.
Example 4.4. Let A be the set of (real number) solutions to the equation 2x
2
7x + 3 = 0 and let B be
the set of integer solutions to the same equation. Since the polynomial factorizes as (2x 1)(x 3),
we see that A = {3,
1
2
} and B = {3}. We could also write A = {
1
2
, 3} since order doesn’t matter in roster
notation. Moreover:
A B since
1
2
A and
1
2
/ B.
B A since 3 (the only element of B) lies in A. Indeed B A is a proper subset since A = B.
Roster notation is ideal for small sets, but is of limited utility when trying to describe large sets. This
is where our second notation rides to the rescue.
Set-builder notation describes the elements of a set using some common property. Suppose U is some
(already understood) set and P(x) is a propositional function with domain U, then
A :=
x U : P(x)
(“A is the set of x in U such that P(x)”)
defines a set A as the subset of U all of whose elements x satisfy the property P(x). A vertical separator
| is often used instead of a colon: we’ll use both, though it might be essential in a given context to use
one rather than the other for clarity.
Examples 4.5. 1. Continuing Example 4.4, recall that R represents the set of real numbers and Z the
set of integers. In set-builder notation, our solution sets may be written
A =
x R : 2x
2
7x + 3 = 0
, B =
x Z : 2x
2
7x + 3 = 0
In this case the qualifying proposition P(x) is “2x
2
7x + 3 = 0.”
We can also express the fact that B is a subset of A in this notation (this time with a vertical
separator),
B =
x A
x Z} (“the set of elements x in A such that x is an integer”)
2. Let X = {2, 4, 6} and Y = {1, 2, 5, 6}. There are many options for how to write these in set-
builder notation. For instance:
X =
n Z :
1
2
n {1, 2, 3}
, Y =
n Z
1 n 6 and n = 3, 4
We now practice the opposite skill by converting five sets from set-builder to roster notation.
S
1
=
x X : x is divisible by 4
= {4} S
2
=
y Y : y is odd
= {1, 5}
S
3
=
x X
x Y
= {2, 6} S
4
=
x X : x / Y
= {4}
S
5
=
y Y
y is odd and y 1 X} = {5}
Can you find alternative descriptions in set-builder notation for the sets S
1
, . . . , S
5
above? Take
your time getting used to this notation: the ability to translate between various descriptions of
a set is crucial to reading mathematics!
44
3. We use the set C = {0, 1, 2, 3, . . . , 24} to describe D = {n Z : n
2
3 C} in roster notation.
Start by expanding the criterion for membership in D:
n
2
3 C n
2
3, 4, 5, . . . , 25, 26, 27
Since n must be an integer, it follows that D = {±2, ±3, ±4, ±5}.
4. To express E = {0, 2, 6, 12, . . .} in set-builder notation we might spot a pattern and decide that
E =
n Z : n = m(m + 1) for some integer m 0
The problem is that we cannot guarantee our correctness! Perhaps the correct formula is
n = m(m + 1) + m(m 2)(m 6)(m 12)
In the first case the next term in the sequence is 4 · 5 = 20, whereas in the second case it is
20 + 128 = 148. For larger sets, the clarity afforded by set-builder notation is essential!
Common Sets of Numbers
We’ve used some of this notation already, and much of the rest should be familiar.
Natural numbers N =
1, 2, 3, 4, . . .
is the set of positive integers.
Integers Z =
. . . , 3, 2, 1, 0, 1, 2, 3, . . .
.
Rational numbers Q =
m
n
: m Z and n N
=
a
b
a, b Z and b = 0
.
Real numbers R. Even a rudimentary definition is too involved for this text.
23
Complex numbers C =
x + iy : x, y R
where i
2
= 1. We won’t use these.
Examples 4.6. 1. For instance: 7 N, π R,
7
9
/ Z,
2 / Q and 3 +
5i C.
2. The basic symbols can be decorated to make natural modifications. For example:
N
0
=
0, 1, 2, 3, 4, . . .
= Z
+
0
=
x Z : x 0
. Also called the whole numbers (W).
Z
5
=
5, 6, 7, 8, . . .
=
x Z : x 5
denotes the integers greater than or equal to 5.
R
+
=
x R : x > 0
is the set of positive real numbers.
4Z =
. . . , 8, 4, 0, 4, 8, 12, . . .
=
x Z : 4 | x
is the set
24
of integer multiples of 4.
This notation can be used for non-integer multiples, e.g. πZ =
. . . , π, 0, π, 2π, . . .
.
2Z + 1 =
x Z : x 1 (mod 2)
is the set of odd integers.
3. Intervals are the most commonly encountered subsets of the real numbers. For instance:
[1, π] =
x R
1 x π
is a closed interval
[4, 7.21) = {x R
4 x < 7.21} is a half-open interval.
(,
2) = {x R
x <
2} is an infinite (open) interval.
23
We simply assume the reader is comfortable with the idea of the real line where number corresponds to length. A
rigorous development of R is a matter for an upper-division analysis course.
24
Be careful!—the colon is the “such that” separator while | denotes the property “4 divides x.”
45
In view of the natural subset relationships N Z Q R C, we consider a simple result.
Lemma 4.7 (Transitivity of Subset). Suppose A B and B C. Then A C.
Proof. Think back to the criteria following Definition 4.3. Suppose A B and B C. Then
x A
(AB)
= x B
(BC)
= x C
We conclude that A C.
Compare this to Exercise 2.1.9b: if we translate each subset relation into an implication, the proof
structure is (x A x B) (x B x C) = (x A x C). This is typical of basic
results about sets: after translation, the theorem reduces to one of the standard rules of logic.
Cardinality and the Empty Set
It is helpful to introduce some terminology to describe the size of a set.
Definition 4.8. A finite set contains only a finite number of elements: this number is its cardinality,
written
|
A
|
. A set with infinitely many elements is said to be an infinite set.
The symbol denotes the empty set: a set containing no elements (cardinality zero:
|
|
= 0).
Examples 4.9. 1. Let A =
1, 3, π,
2, 103
, then
|
A
|
= 5.
2. Let B =
4, {1, 2}, {3}
. The elements of B are 4, {1, 2} and {3}, therefore
|
B
|
= 3. It doesn’t
matter that the element {1, 2} B is also a set!
3. Recall some basic trigonometry:
x [0, 4π] : cos x =
1
2
=
π
3
,
5π
3
,
7π
3
,
11π
3
has cardinality 4.
1
0
1
π 2π 3π 4π
1
2
4. There are many representations of the empty set: for example
=
x R : x
2
= 1
=
x N : x
2
+ 3x + 2 = 0
=
n N : n < 0
In general, if X is any set and P(x) is false for all x X, then
25
=
x X : P(x)
.
Cardinality is a very simple concept for finite sets; if B is finite, so is any subset, and we have
A B =
|
A
|
|
B
|
For infinite sets, cardinality is more subtle. We’ll return to this issue and uncover some of the bizarre
and fun consequences of infinite cardinalities in Chapter 8.
25
In some formalizations of set theory, the existence of the empty set is an axiom: an assumption made without proof.
Provided one accepts that set-builder notation always defines a set—this is itself an axiom!—and that at least one set X
exists, the empty set may be defined as in the example: a suitable property P(x) might be something like x / {x}.”
46
We finish with a couple of simple results regarding the empty set.
Lemma 4.10. Let A be a set.
1. If
|
A
|
= 0, then A = . The empty set is the unique set with zero cardinality.
2. A and A A
Proof. Think about the claim A: by the observations following Definition 4.3, this means
x = x A
This is true (for any set A!) since there are no elements x satisfying the hypothesis.
26
1. Suppose A has cardinality zero. Repeating and combining with the above observation, we see
that A and A . We conclude that A = .
2. We already know that A. For the second part, simply observe that x A = x A.
Exercises 4.1. A reading quiz and several questions with linked video solutions can be found online.
1. Describe the following sets in roster notation: that is, list their elements.
(a)
x N : x
2
3x
(b)
n {0, 1, 2, 3, . . . , 19} : n + 3 5 (mod 4)
(c)
n {2, 1, 0, 1, . . . , 23} : 4 | n
2
(d)
x
1
2
Z : 0 x 4 and 4x
2
2Z + 1
(e)
y R : y = x
2
for some x R with x
2
3x + 2 = 0
2. Describe the following sets in set-builder notation (look for a pattern).
(a)
. . . , 3, 0, 3, 6, 9, . . .
(b)
3, 1, 5, 9, 13, . . .
(c)
1,
1
3
,
1
7
,
1
15
,
1
31
, . . .
3. Each of the following sets of real numbers is a single interval. Determine the interval.
(a)
x R : x > 3 and x 17
(b)
x R : x 3 or x 17
(c)
x
2
R : x = 0
(d)
x R
: x
2
16 and x
3
27
4. Is the set {x Z : 1 x < 43} finite or infinite? If finite, what is its cardinality?
5. What is the cardinality of the set
n
,
,
, {}
o
? What are its elements?
6. Let A = , B = {A}, C =
{A}
and D =
A, {0}, {0, 1}
.
Answer the following true or false:
(a) 0 A (b) A B (c) A C (d) B C (e) A D
(f) B D (g) 0 D (h) {0} D (i) {1} D
7. List all the proper subsets of {1, 2, 3}.
26
If P(x) is always false, then (x) P(x) = Q( x) is true. This is called a vacuous (empty) theorem.
47
8. Let A, B, C, D be the following sets:
A = {4, 1, 2, 4, 10} B =
m Z :
|
m
|
12
(absolute value of m)
C =
n Z : n
2
1 (mod 3)
D =
t Z : t
2
+ 3 [4, 20)
Of the 12 subset relations A B, A C, . . . , D C, which are true and which false?
9. Let A =
1, 2, {1, 2}, {3}
and B = {1, 2}. Answer the following true or false:
(a) B A (b) B A (c) 3 A (d) {3} A
(e) {3} A (f) A (g) A
10. Let A = {0, 2, 4, 6, 8, 10}. Write the set B = {X A : |X| = 2} in roster notation.
11. (a) Suppose A B C A. Show that A = B = C.
(b) Is it possible for sets A, B, C to satisfy A B C A? Why/why not?
12. Let A = {1,2,3,4}, and let B =
{x, y} : x, y A
.
(a) Describe B in roster notation (what happens when x = y?).
(b) Find the cardinalities of the following sets:
C =
n
x, {y}
: x, y A
o
and D =
n
x, {y}
: x, y A
o
13. Let A = {x R : x
3
+ x
2
x 1 = 0} and B = {x R : x
4
5x
2
+ 4 = 0}. Are either of the
relations A B or B A true? Explain.
14. For which real numbers x > 0 do we have [0, x] [0, x
2
]? Prove your assertion.
15. Let m, n N. Prove: mZ nZ n | m.
16. Given A Z and x Z, we say that x is A-mirrored if and only if x A. Also define
M
A
:=
x Z : x is A-mirrored
(a) What does it mean for x not to be A-mirrored?
(b) Find M
B
given B = {0, 1, 6, 7, 7, 100}.
(c) Assume that A Z is closed under addition: for all x, y A, we have x + y A. Show
that M
A
is closed under addition.
(d) In your own words, under which conditions is A = M
A
?
17. Define the set [1] =
x Z : x 1 (mod 5)
.
(a) Describe the set [1] in roster notation.
(b) Compute the set M
[1]
, as defined in Exercise 16. Is M
[1]
equal to [1]?
(c) Now consider the set [10] = {x Z : x 10 (mod 5)}. Are the sets [10] and M
[10]
equal?
Prove or disprove.
18. Consider the set A = {a, b, c, d}.
(a) Of each cardinality 0, 1, 2, 3 and 4, how many subsets has A? Is there a pattern?
(b) Completely expand the polynomial ( 1 + x)
4
. What do you notice about the coefficients?
48
4.2 Unions, Intersections and Complements
In this section we construct new sets from old, modeled on the logical concepts of and, or, and not.
Definition 4.11. Suppose A and B are sets.
1. The union of A and B is the set of elements in A or B:
A B :=
x : x A or x B
(x A B x A or x B)
2. The intersection of A and B is the set of elements in both A and B:
A B :=
x : x A and x B
(x A B x A and x B)
We say that A and B are disjoint if A B = .
3. The complement of A is the set of all elements not in A (with respect to some universal set
27
U):
A
C
:=
x U : x / A
(x A
C
x / A (and x U))
4. The complement of A relative B is the set of elements in B which are not in A:
B \ A =
x B : x / A
= B A
C
(x B \ A x B and x / A)
This can be read B minus A (some authors write B A). Similarly A
C
= U \ A, etc.
A
A
C
A \ B B \ A
A
B
A B
A B
In the first Venn diagram, the outer box depicts the universal set U. Though it doesn’t constitute a
proof, the second diagram certainly suggests that
A = (A \ B) (A B) and B = (B \ A) (A B)
Observe the notational similarity with logic: looks a bit like (OR); like (AND).
Examples 4.12. 1. Let U = {1, 2, 3, 4, 5}, A = {1, 2, 3}, and B = {2, 3, 4}. Then
A
C
= {4, 5} B
C
= {1, 5} B \ A = {4} A \ B = {1}
A B = {1, 2, 3, 4} A B = {2, 3} A B
C
= {1} A
C
B
C
= {1, 4, 5}
27
This is needed for complements since x has to live somewhere: should, say, {1}
C
be the set of all integers except 1,
real numbers except 1, etc.?! In many contexts the universal set is naturally assumed: U = R makes sense if you are doing
calculus, U = Z if doing modular arithmetic. The universal set is not needed for the rest of the definition (that the union is
a set is typically an axiom, while intersections and relative complements are automatically subsets of pre-existing sets).
49
2. Using interval notation, let U = [4, 5], A = [3, 2], and B = [4, 1). Then
A
C
= [4, 3) (2, 5]
B
C
= [1, 5]
A \ B = [1, 2]
B \ A = [4, 3)
A B = [4, 2]
A B = [3, 1)
4 3 2 1 0 1 2 3 4 5
U
[ ]
A
[ ]
B
[ )
A
C
[ ) ( ]
B
C
[ ]
B \ A
[ )
A \ B
[ ]
While you should be comfortable with these just from the picture, for practice it is worth trying
algebraic arguments. In particular, note how A
C
relies on de Morgan’s law (Theorem 2.15):
x A
C
x / A ¬
x A
¬
3 x and x 2
x < 3 or x > 2 (de Morgan)
x [4, 3) (2, 5] (remember that x U always!)
3. Let A = (, 3) and B = [2, ) in interval notation. Then A B = R and A B = [2, 3).
For the remainder of this section, we summarize the basic rules of set algebra.
Theorem 4.13 (Union/intersection rules). Let A, B, C be sets. Then:
1. A = A and A =
2. A B A A B
3. A B = B A and A B = B A
4. A (B C) = (A B) C and A (B C) = (A B) C
5. A A = A A = A
6. A B = A C B C and A C B C
If you don’t believe a result, try visualizing it using a Venn diagram. The basic proof strategy is the
same for all parts: convert each statement into propositions (Definition 4.11 parentheses) and use
what you know from basic logic (e.g., Theorem 2.15 and page 11). We prove part 2 and half of part 6,
leaving some of the rest to the Exercises.
Proof. 2. There are two results here: A B A and A A B. We prove separately, with some
commentary on the side.
(a) Suppose x A B. (Goal: want to prove x A B x A)
Then x A and x B. (Definition of intersection)
Plainly x A. We conclude that A B A (Definition of subset)
(b) Suppose y A. (Goal: prove y A y A B)
Then y A or y B is true, whence y A B. (Definition of union/or)
We conclude that A A B.
50
6. (first half) Suppose A B. We wish to prove that x A B = x A C. However,
x A C = x A or x C (definition of union)
= x B or x C (since A B)
= x B C
The next batch of rules describe how complements interact with other set operations: parts 1 and 2
are de Morgan’s laws for sets; unsurprisingly, their proofs depend on the corresponding laws of logic.
Theorem 4.14 (Complement rules). Let A, B be sets. Then:
1. (A B)
C
= A
C
B
C
(see picture)
2. (A B)
C
= A
C
B
C
3. (A
C
)
C
= A
4. A B B
C
A
C
A
B
Proof. We prove only part 1. As before, the natural approach is to restate the result using propositions.
x (A B)
C
¬
x A B
¬
x A and x B
¬
x A
or ¬
x B
(de Morgan’s first law of logic)
x A
C
or x B
C
x A
C
B
C
Our final pair of results describe the interaction of unions and intersections.
Theorem 4.15 (Distributive laws). For any sets A, B, C:
1. A (B C) = (A B) (A C)
2. A (B C) = (A B) (A C)
The Venn diagram illustrates the second result: think about adding the
colored regions.
Proof. We prove only the first result.
x A (B C) x A and x B C
x A and
x B or x C
x A and x B
or
x A and x C
(distributive law, page 11)
x A B or x A C
x (A B) (A C)
51
Exercises 4.2. A reading quiz and several questions with linked video solutions can be found online.
1. Describe each set simply as you can: e.g.,
x R : x
2
< 9 and x
3
< 8
= (3, 3) (, 2) = (3, 2)
(a)
x R : x
2
= x
(b)
x R : x
3
2x
2
3x 0 or x
2
= 4
(c)
y R : x R with y = x
2
and x = 1
(d)
z Z : z
2
is even and z
3
is odd
(e)
y 3Z + 2 : y
2
1 (mod 3)
2. Let A = {1, 3, 5, 7, 9}, B = {1, 4, 7, 10} and U = {1, 2, . . . , 10}. What are the following sets?
(a) A B (b) A B (c) B \ A (d) A
C
(e) (A \B)
C
(f) A
C
B
C
(g) (A B) \ (A B)
3. Give formal proofs of the following parts of Theorems 4.13, 4.14 and 4.15.
(a) A = (b) A (B C) = (A B) C
(c) (A
C
)
C
= A (d) A (B C) = (A B) (A C)
(e) A B B
C
A
C
4. By showing that each side is a subset of the other, give a formal proof of the set identity
A = (A \ B) (A B)
Now repeat your argument using only results from set algebra (Theorems 4.14 and 4.15).
5. Prove the identity A B = A B A for any sets A, B.
6. Prove the identities for any sets A, B, C:
(a) (A B C)
C
= A
C
B
C
C
C
(b) (A B) \ (A B) = (A \ B) (B \ A)
7. Prove or disprove the following conjectures (Hint: revisit Section 2.4).
(a) x R \Q such that x
2
Q. (b) x R \Q we have x
2
Q.
8. Let A R, and let x R. We say that x is far away from the set A if and only if:
d > 0 such that A [x d, x] =
If this does not happen, we say that x is close to A.
(a) Draw a picture of a set A and elements x, y such that x is far away from and y is close to A.
(b) State the meaning of x is close to A (negate x is far away from A”).
(c) Let A = {1, 2, 3}.
i. Show that x = 4 is far away from A using the definition.
ii. Let A = {1, 2, 3}. Show that x = 1 is close to A.
(d) For general A R, show that if x A, then x is close to A.
(e) Let A = (a, b) be a bounded interval. Is the end-point a far away from A? What about b?
52
4.3 Introduction to Functions
Sets become a lot more useful and interesting once you start transforming their elements! This is
accomplished using functions. In this section we introduce some basic concepts and notation, much
of which should be familiar. A formal definition will be given in Chapter 7, but for the present the
following will suffice.
Definition 4.16. Let A, B be sets. A function f : A B is a rule assigning to each input a A a
single output b B, typically denoted f (a). Various sets are associated to f :
Domain: dom( f ) = A is the set of inputs to the function.
Codomain: codom( f ) = B is the set of potential outputs.
Image of a subset U A: the set of outputs given inputs in U
f ( U) :=
f (u) B : u U
Range: range( f ) = f (A) = {f (a) B : a A} is the set of
realized outputs.
f
a
1
b
1
a
2
b
2
a
3
b
3
b
4
a
4
A
B
f (A)
Inverse image (or pre-image) of a subset V B: the set of inputs which are mapped into V
f
1
(V) :=
a A : f (a) V
The rule defining a function can be described using arrow notation f : a 7 b.
Examples 4.17. 1. Functions whose codomain is (a subset of) the real numbers R are often graphed:
the domain and range are found by projecting the graph onto the two axes.
For instance if f : [3, 2) R is the square function
f : x 7 x
2
(equivalently f (x) = x
2
)
then dom( f ) = [3, 2) and range( f ) = [0, 9]. We could
also calculate other images/pre-images, for example,
f
[1, 2)
=
x
2
: 1 x < 2
= [0, 4)
f
1
( 10, 2]
=
x [3, 2) : 10 < x
2
2
= [
2,
2]
3
6
9
f (x)
3 2 1 0 1 2
x
range
domain
2. Define f : Z {0, 1, 2} by f : n 7 n
2
(mod 3). The table
shows a few examples (remember dom( f ) = Z is infinite!).
n 0 1 2 3 4 5 6 7
f (n) 0 1 1 0 1 1 0 1
Exercise 3.1.14 confirms what the examples suggest, that range( f ) = {0, 1}. We also compute a
single inverse image (revisit the previous two sections if you’re unsure about the notation):
f
1
{1}
=
x Z : x
2
1 (mod 3)
=
x Z : x 1 or 2 (mod 3)
= (3Z + 1) (3Z + 2)
53
3. Let A = {0, 1, 2, . . . , 7} be the set of remainders modulo 8
and define two functions f , g : A A:
f (n) = 3n (mod 8) g(n) = 6n (mod 8)
n 0 1 2 3 4 5 6 7
f (n) 0 3 6 1 4 7 2 5
g(n) 0 6 4 2 0 6 4 2
Since the domain has only 8 elements, the table describes everything. Observe that
range( f ) = A f
{1, 5}
= {3, 7} f
1
{1, 2, 3, 4}
= {1, 3, 4, 6}
range(g) = {0, 2, 4, 6} g
{1, 5}
= {6} g
1
{1, 2, 3, 4}
= {2, 3, 6, 7}
4. Let A = {0, 1, 2, 3, 4} and let B = {two-element subsets of A}. Define
f : A B : a 7 {a, a + 1 (mod 5)}
where we take the remainder modulo 5. You should be able to convince yourself that
range( f ) =
{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0}
f
{1, 4}
=
f (1), f (4)
=
{1, 2}, {4, 0}
and f
1
{2, 4}, {4, 0}
= {4}
Injections, Surjections and Invertibility
We turn our attention to perhaps the most important properties a function can possess.
Definition 4.18. Let f : A B be a function. We say that f is:
1. Injective (1–1, an injection) if it never outputs the same value twice. Equivalently,
28
f (a
1
) = f (a
2
) = a
1
= a
2
(“a
1
, a
2
A is typically hidden)
2. Surjective (onto, a surjection) if every possible output is realized: B = range( f ). Equivalently,
28
b B, a A such that f (a) = b
3. Bijective (invertible, a bijection) if it is both injective and surjective. Equivalently
b B, a unique a A such that f (a) = b
When f is bijective, its inverse function is f
1
: B A : b 7 a.
Since the definitions of injectivity and surjectivity are both universal statements, it suffices to provide
counter-examples to show that a function is not injective or not surjective. Indeed:
f not injective: a
1
= a
2
A such that f (a
1
) = f (a
2
)
f not surjective: b B such that a A, f (a) = b
28
For injectivity this is the contrapositive: if f never takes the same value twice, then a
1
= a
2
= f (a
1
) = f (a
2
).
For surjectivity, the quantified statement expresses B range( f ). The inclusion range( f ) B is true for any function.
54
Examples (4.17, cont.). We briefly revisit our previous examples.
1. Let f : [3, 2) R : x 7 x
2
.
f is non-injective: f (1) = f (1) provides a counter-example. (a
1
= 1 = a
2
)
f is non-surjective: there is no x [ 3, 2) for which x
2
= 5. (b = 5)
We can obtain a related injective function by shrinking the domain,
for instance g : [0, 2) R : x 7 x
2
. Indeed
g(x
1
) = g(x
2
) = x
2
1
= x
2
2
= x
1
= x
2
since x
1
, x
2
[0, 2) are non-negative. By also shrinking the codomain,
we get a surjective (now bijective) function: h : [0, 2) [0, 4) : x 7 x
2
.
Proof of surjectivity: Given y [0, 4), let x =
y, then y = h(x).
0
2
4
0 1 2x
y
2. f : Z {0, 1, 2} : n 7 n
2
(mod 3) is neither injective nor surjective.
f is non-injective: for instance f (1) = f (2).
f is non-surjective: range( f ) = {0, 1} = {0, 1, 2} = codom( f ).
3. Given f , g : A A where A = {0, 1, . . . , 7} as in the table:
f is bijective: all elements of codom( f ) appear exactly
once in the f -row.
g is non-injective: e.g., g(0) = g(4).
g is non-surjective: e.g., 1 / range(g) = {0, 2, 4, 6}.
n 0 1 2 3 4 5 6 7
f (n) 0 3 6 1 4 7 2 5
g(n) 0 6 4 2 0 6 4 2
4. Let A = {0, 1, 2, 3, 4} and f : A
two-element subsets of A
: a 7 {a, a + 1 (mod 5)}
f is injective: suppose a
1
, a
2
A, then
f (a
1
) = f (a
2
) = {a
1
, a
1
+ 1 (mod 5)} = {a
2
, a
2
+ 1 (mod 5)} = a
1
= a
2
f is not surjective: e.g., {1, 3} / range( f ).
You should have seen the approach of the next example in other classes.
Example 4.19. We show that f : (, 2) (1, ) : x 7→ 1 +
1
(x2)
2
is
bijective by computing its inverse function. Just solve for x in terms of y:
y = 1 +
1
(x 2)
2
= (x 2)
2
=
1
y 1
= f
1
( y) = x = 2
1
p
y 1
The sign of the square-root was chosen so that x dom( f ) = (, 2).
1
2
3
4
5
1 0 1 2x
y
55
Composition of Functions
We consider how injectivity and surjectivity interact with composition of functions.
Definition 4.20. Given functions f : A B and g : B C,
their composition is the function
g f : A C : a 7 g
f (a)
Note the order: to compute (g f )(a), first apply f , then g.
f g
g f
a
f (a)
g
f (a)
A
B
C
In practice, some restriction of domains might be required in order to define a composition.
Example 4.21. If f (x) = x
2
and g(x) =
1
x1
, then
(g f )(x) =
1
x
2
1
and ( f g)(x) =
1
(x 1)
2
Even though ±1 are legitimate inputs for f , dom(g f ) = R \ {±1} is implied so as to prevent
division by zero.
Theorem 4.22. Let f : A B and g : B C be functions. Then:
1. If f and g are injective, then g f is injective.
2. If f and g are surjective, then g f is surjective.
It follows that the composition of bijective functions is also bijective.
Proof. Suppose f and g are injective and let a
1
, a
2
A. Then
(g f )(a
1
) = (g f )(a
2
) = g
f (a
1
)
= g
f (a
2
)
= f (a
1
) = f (a
2
) (since g is injective)
= a
1
= a
2
(since f is injective)
That is, g f is injective. We leave part 2 to the exercises.
Somewhat surprisingly, the converse of this theorem is false. If a composition is injective or surjective,
only one of the original functions is required also to be.
Theorem 4.23. Suppose f : A B and g : B C.
1. If g f is injective, then f is injective.
2. If g f is surjective, then g is surjective.
The picture illustrates what can happen: f is only injective,
g is only surjective, but g f is bijective.
f
g
a
2
a
1
b
2
b
1
b
3
c
2
c
1
A
B
C
56
Example 4.24. Here is a formulaic version of the picture in the theorem. Make sure you’re comfort-
able with the definitions and draw pictures or graphs to help make sense of what’s going on.
f : [0, 2] [4, 4] : x 7 x
2
(injective only)
g : [4, 4] [0, 16] : x 7 x
2
(surjective only)
g f : [0, 2] [0, 16] : x 7 x
4
(bijective!)
Proof. This time we leave part 1 for the Exercises. Let c C and assume g f is surjective. But then
a A such that c = (g f )(a) = g
f (a)
Otherwise said, b(= f (a)) B for which c = g(b): that is, g is surjective.
Functions and Cardinality
Injectivity and surjectivity are intimately tied to the notion of cardinality. In Chapter 8, we will use
such functions to define cardinality for infinite sets. For the present we stick to finite sets.
Theorem 4.25. Let A and B be finite sets. The following are equivalent:
1.
|
A
|
|
B
|
2. f : A B injective 3. g : B A surjective
Moreover,
|
A
|
=
|
B
|
f : A B bijective.
The theorem asserts that any one of the three numbered statements is true if and only
if all are. It might appear that six arguments are required but, by proving in a circle,
we only need three: for instance
1
3
holds because
1
2
and
2
3
.
The proof is very abstract, but if you focus on the picture it should make sense.
1
2
3
=
=
=
Proof. Suppose
|
A
|
= m,
|
B
|
= n and label the elements in roster notation:
A = {a
1
, a
2
, . . . , a
m
} B = {b
1
, b
2
, . . . , b
n
}
1
2
If m n, define f : A B by f (a
k
) = b
k
as in the
picture. This is injective since the b
1
, . . . , b
m
are distinct.
{a
1
,
_
f
a
2
, . . . , a
m
}
_
f
{b
1
,
_
g
OO
b
2
, . . . , b
m
,
_
g
OO
z }| {
b
m+1
, . . . , b
n
}
m
g
yy
2
3
Suppose f : A B is injective. Without loss of generality, label the elements of B such that
b
k
= f (a
k
) for 1 k m. Define the surjective function g : B A as in the picture:
29
g(b
k
) :=
(
a
k
if k m
a
1
if k > m
3
1
Suppose g : B A is surjective. Without loss of generality, label the elements of B such
that a
k
= g(b
k
) for 1 k m. Since the b
k
must be distinct, we see that n m.
When m = n, the constructed functions are plainly bijections with f
1
= g.
29
The elements b
m+1
, . . . , b
n
could be mapped anywhere, we choose a
1
for simplicity.
57
Exercises 4.3. A reading quiz and several questions with linked video solutions can be found online.
1. For each of the following functions f : A B determine whether f is injective, surjective or
bijective. Prove your assertions.
(a) f : [0, 3] R where f (x) = 2x.
(b) f : [3, 12) [0, 3) where f (x) =
x 3.
(c) f : (4, 1] (5, 3] where f (x) =
x
2
+ 9.
2. Suppose that f : [3, ) [8, ) and g : R R are defined by
f (x) = x
2
+ 6x + 1, g(x) = 2x + 3
Compute g f and show that it is injective.
3. (a) Find a set A so that the function f : A R : x 7 sin x is injective.
(b) Find a set B so that the function f : R B : x 7 sin x is surjective.
4. A function f : R R is even if and only if x R, f (x) = f (x).
(a) Prove that f : x 7 x
2
is even.
(b) By negating the definition, state what it means for a function not to be even.
(c) Give an example of a function that is not even: prove it.
(d) Prove or disprove: for every f , g : R R even, the composition h = f g is even.
5. The picture in Definition 4.16 illustrates a function
f : {a
1
, a
2
, a
3
, a
4
} {b
1
, b
2
, b
3
, b
4
}
State the following:
a a
1
a
2
a
3
a
4
f (a) b
1
b
2
b
3
b
3
(a) range( f ) (b) f
{a
1
, a
4
}
(c) f
1
{b
3
}
(d) f
1
{b
4
}
6. (a) Let A = {a, b, c}, B = {1, 2, 3, 4}and f : A B be the function defined by f (a) = f (c) = 1
and f (b) = 3. State the following:
i. f
1
{1}
(b) f
1
{3}
(c) f
1
{1, 3}
(d) f
1
{2, 4}
(b) Let g : [1, ) R : x 7 x
2
+ 2x + 1. Compute g
1
(0, 2]
.
(c) Let h : R R : x 7 sin x. Find h
1
{1, 1}
.
7. Define f : ( , 0] R and g : [0, ) R by
f (x) = x
2
, g(x) =
(
x
1x
x < 1
1 x x 1
Is g f : (, 0] R surjective? Justify your answer.
8. Recall Example 4.17.3. Consider the nine functions f
k
: A A : x 7 kx (mod 10), where
k = 1, 2, . . . , 9. Find the range of each f
k
. Can you find a relationship between k and the
cardinality of range( f
k
)?
58
9. Let f : R R
+
be the function defined by f (x) = e
x
. Explain why the following “proof that
f is surjective is incorrect. Then, give a correct proof.
Proof? Let e
x
R
+
be arbitrary. Then f (x) = e
x
. We conclude that f is surjective.
10. (a) Show there is a bijection between Z and 2Z.
(b) Let S be the set of all circles in the plane which are centered at the origin. Find a bijection
between S and R
+
.
(c) Let A, B be finite sets. If A B, is it possible for there to be a bijection between A and B?
11. Prove that the composition of two surjective functions is surjective.
12. Suppose that g f is injective. Prove that f is injective.
13. Let f : A B. Prove the following:
(a) f is injective if and only if b B, f
1
{b}
has at most one element.
(b) f is surjective if and only if b B, f
1
{b}
has at least one element.
14. Prove that functional composition is associative. That is, if f : A B, g : B C, and h : C D
are functions, then for all a A we have
f (g h)
(a) =
( f g) h
(a)
15. Following Theorem 4.22, the composition of bijective functions f , g is itself bijective. Give a
brief explanation as to why (g f )
1
= f
1
g
1
.
16. Let f : A B and X A. Fill in the blanks to complete a proof of the following facts:
(a) X f
1
f (X)
. (b) If f is injective, then X = f
1
f (X)
.
Proof. (a) x X = f (x) . Let y = f (x), then x f
1
f (X)
.
(b) a f
1
f (X)
= , whence x X with f (a) = f (x). By injectivity, ,
whence a X. We conclude that . Combine with part (a) for the result.
17. Let f : A B be a function and let Y B. Prove the following facts:
(a) f
f
1
(Y)
Y. (b) If f is surjective, then f
f
1
(Y)
= Y.
18. (Hard) Let f : A B be a function and X, Y A.
(a) Prove that f (X Y) f (X) f (Y).
(b) If f is injective, prove that f (X Y) = f (X) f (Y).
(c) If f (X Y) = f (X) f (Y) for all X, Y A, prove that f is injective.
59
5 Mathematical Induction and Well-ordering
In Section 2.3 we discussed three methods of proof: direct, contrapositive, and contradiction. The
fourth standard method, induction, has a very different flavor. Before giving a formal definition, we
consider how the need for induction arguments often arises.
5.1 Iterative Processes & Proof by Induction
Recursive processes are very common in mathematics and its applications: an unknown x
n
satisfies
a simple recurrence relation x
n+1
= f (x
n
) where an initial value x
1
is given. The typical approach
to such problems is to hypothesize a general formula x
n
= g(n) (spot a pattern!), and then prove the
validity of the formula. Induction is the proof method often employed in such situations. To get us
started, we investigate a famous game.
The Tower of Hanoi
Circular disks of decreasing radius are stacked on three pegs. Disks are moved one at a time from
the top of a stack onto an empty peg or on top of a larger disk. If we start with 10 disks on the first
peg, how many moves are required to transfer all disks to another peg?
To get a feel for the problem, try playing the game with smaller numbers of disks. Suppose n disks
require r
n
moves. Then:
r
1
= 1 since there is only one disk to move!
r
2
= 3 as shown in the picture.
More experimentation will hopefully convince you that r
3
= 7, at which point you might be ready to
hypothesize a general formula—if not, experiment more!
Conjecture 5.1. The Tower of Hanoi with n disks requires r
n
= 2
n
1 moves.
To make progress, consider a stack of n + 1 disks. To move the largest disk, all other disks must be
stacked on a single peg. Moving n + 1 disks is therefore a three-step process:
1. Move the smallest n disks to another peg.
2. Move the largest disk.
3. Move the remaining disks on top of the largest.
r
n
moves
1 move
r
n
moves
The upshot is that r
n
satisfies a recurrence relation: r
n+1
= r
n
+ 1 + r
n
= 2r
n
+ 1.
60
We are now in a position to prove our conjecture.
Proof. Certainly the formula r
n
= 2
n
1 holds when n = 1 disk (1 disk requires r
1
= 1 move).
Now suppose that n disks require r
n
= 2
n
1 moves, where n N is some fixed number. Then n + 1
disks require
r
n+1
= 2r
n
+ 1 = 2(2
n
1) + 1 = 2
n+1
1
moves (). Since n was arbitrary, we have in fact proved an infinite collection of implications:
r
1
= 2
1
1 = r
2
= 2
2
1 = r
3
= 2
3
1 = ··· = r
n
= 2
n
1 = ···
Since the first of these propositions (r
1
= 2
1
1) is true, we conclude that r
n
= 2
n
1 for all n N.
To answer the original question, 10 disk require r
10
= 2
10
1 = 1023 moves; at one move per second
this would take 17 minutes, 3 seconds.
Proof by Induction
The Tower of Hanoi argument is an example of proof by induction. This method is invoked when we
want to prove a sequence of propositions P(1), P(2), P(3), . . . , one for each natural number. The
abstract structure of an induction proof consists of two separate arguments:
(Base case) Prove that P(1) is true.
(Induction step) Prove, for each n N, that P(n) = P(n + 1). During this phase, P(n) is termed the
induction hypothesis.
The result is an infinite chain of implications:
P(1) = P(2) = P(3) = P(4) = P(5) = ···
Since P(1) is true (base case), all the remaining propositions P(2), P(3), P(4), . . . are also true.
Re-read the Tower of Hanoi proof; can you separate the base case and induction step? Our pre-
sentation was informal since we were only introducing the concept. For a formal argument, a few
modifications should be made.
Set-up the proof: orient the reader by stating, “We prove by induction.” It might also be helpful
to spell out the propositions P(n) and to tell the reader what variable (n) controls the induction.
Label the base case and induction step so the reader knows what you are doing!
After the induction step is complete, state your conclusion. In the above we would replace
everything after () with, “By mathematical induction, r
n
= 2
n
1 for all n N.”
Here is a straightforward and famous result, where we write the proof in our new language.
Theorem 5.2. The sum of the first n positive integers is
n
k=1
k =
1
2
n(n + 1)
You should be familiar with summation notation
n
k=1
k = 1 + 2 + 3 + ··· + n: if not ask!
61
Proof. We prove by induction. For each n N, let P(n) be the proposition
n
k=1
k =
1
2
n(n + 1).
Base case (n = 1):
1
k=1
k = 1 =
1
2
1( 1 + 1), says that P(1) is true.
Induction Step: Fix n N, and assume that P(n) is true for this n. We compute the sum of the first
n + 1 positive integers and use our induction hypothesis P(n) to simplify:
n+1
k=1
k =
n
k=1
k + (n + 1) =
1
2
n(n + 1) + (n + 1) (induction hypothesis)
=
1 +
1
2
n
( n + 1) =
1
2
( n + 2)(n + 1)
=
1
2
( n + 1)
( n + 1) + 1
Therefore P(n + 1) is true.
By mathematical induction, we conclude that P(n) is true for all n N. That is
n N,
n
k=1
k =
1
2
n(n + 1)
Note how we grouped
1
2
( n + 1)
( n + 1) + 1
so that it is obviously the right hand side of P(n + 1).
We present several more examples in a similar vein, but done a little faster. As is typical, we don’t
explicitly introduce the symbol P(n), though you should feel free to continue doing this if you find
it helpful. Aim for a layout like these in your formal writing.
Example 5.3. We prove by induction that, for all n N,
2 + 5 + 8 + ···+ (3n 1) =
1
2
n(3n + 1) ()
Base case (n = 1): The proposition () is trivially true: 2 =
1
2
·1 · (3 · 1 + 1).
Induction Step: Fix n N and assume () holds for this value of n. Then
2 + 5 + ··· + (3n 1) + [3(n + 1) 1] =
1
2
n(3n + 1) + 3n + 2
=
1
2
(3n
2
+ 7n + 4) =
1
2
( n + 1)(3n + 4)
=
1
2
( n + 1)
3(n + 1) + 1
which is the required proposition for n + 1.
By mathematical induction () holds for all n N.
For brevity we labelled the desired proposition (what we’d have called P( n)) by () so it could be
referenced. The structure is similar to Theorem 5.2: since the goal is to evaluate a sum, the induction
step is little more than adding the same thing (3n + 2) to both sides of the induction hypothesis. In
fact, the example could have been proved directly by invoking Theorem 5.2—can you see how?
62
Our next two examples are a little harder, requiring more creativity to invoke the induction hypoth-
esis. Both could alternatively be proved directly using modular arithmetic (Chapter 3).
Examples 5.4. 1. We prove by induction that n N, the integer 17
n
4
n
is divisible by 13.
Base case (n = 1): Plainly 17
1
4
1
is divisible by 13.
Induction Step: Fix n N and assume that 17
n
4
n
= 13k for some k Z. Then
17
n+1
4
n+1
= 17
17
n
4
n+1
= 17
13k + 4
n
4
n+1
(induction hypothesis)
= 17 ·13k + (17 4)4
n
= 13
17k + 4
n
is divisible by 13.
By mathematical induction, 17
n
4
n
is divisible by 13 for all n N.
2. We prove by induction: if n N, then n(n + 1)(2n + 1) is divisible by 6.
Base case (n = 1): The proposition reads 1 · (1 + 1) · (2 · 1 + 1) = 6, which is divisible by 6.
Induction Step: Fix n N and assume that n(n + 1)(2n + 1) = 6k for some k Z. Then
( n + 1)(n + 2)
2(n + 1) + 1
6k = (n + 1)
( n + 2)(2n + 3) n(2n + 1)
= (n + 1)
2n
2
+ 7n + 6 (2n
2
+ n)
= 6(n + 1)
2
from which
( n + 1)
( n + 1) + 1
2(n + 1) + 1
= 6
( n + 1)
2
+ k
is divisible by 6.
By mathematical induction, n(n 1)(2n 1) is divisible by 6 for all n N.
Scratch work is your friend! Unless things are very simple, you should build an induction ar-
gument by starting with some scratch work for the hard part: the induction step. If you’re stuck,
explicitly stating the propositions P(n) and P(n + 1) might help you see how to manipulate one into
the other. Here are the propositions for Example 5.4.1:
P(n): 17
n
4
n
= 13k for some integer k
P(n + 1): 17
n+1
4
n+1
= 13l for some integer l
Since 17
n
is common to both, you could try multiplying both sides of P(n) by 17; if you re-read
the example, you’ll see that this is essentially the induction step! For Example 5.4.2, you might try
multiplying out the cubic expressions
n(n + 1)(2n + 1) and (n + 1)(n + 2)(2n + 3)
and comparing coefficients. Since the leading term in both is n
3
, the difference is quadratic and there-
fore much easier to think about. . .
Remember that scratch work isn’t a proof; while your scratch work may make perfect sense to you,
if a reader cannot follow it without assistance, then it isn’t a proof! It is essential, once you think
63
you understand the induction step, to lay out the entire proof cleanly: set-up, base case, induction step,
conclusion. As an example of what happens when you don’t, here is a typical attempt at Example 5.3
by a student who is new to induction:
P(n + 1) = 2 + 5 + ···+ (3n 1) + [3(n + 1) 1] =
1
2
( n + 1)
3(n + 1) + 1
1
2
n(3n + 1) + (3n + 2) =
1
2
( n + 1)(3n + 4)
3n
2
+ n + 6n + 4 = 3n
2
+ 7n + 4
Is this convincing to you? While there are many issues,
30
the student’s work isn’t without merit,
since the required calculation is present (left side of 1
st
line = left side of 2
nd
). While helpful as
scratch work, a substantial re-write is needed to make this convincing.
We finish this section with a trickier example of this thinking at work.
Example 5.5. An L-shaped tromino is an arrangement of three squares in an “L shape. We claim:
If any single square is removed from a 2
n
×2
n
square gird, then
the remaining grid may be tiled by L-shaped trominos.
The claim has the form n N, P(n), but note that P(n) is itself universal.
The picture shows one of the sixteen possible examples when n = 2. To get
an idea of how to structure the induction step, think how you might use
2 ×2 grids to analyse a 4 ×4 grid. The picture shows how!
Whatever square we remove, one quarter of the 2
2
×2
2
grid is a 2
1
×2
1
grid with one square removed: this is tilable.
Place a single tromino (yellow in the picture) so that one of its squares lies in each remaining
quadrant. What’s left of each quadrant is a 2
1
×2
1
grid with one missing square: again tilable.
This scratch work is really an argument P(1) = P(2)! It remains only to formalize this intuition
into a general proof. We proceed by induction on n.
Base case (n = 1): If a single square is removed from a 2 ×2 grid, the three remaining squares form
single L-shaped tromino.
Induction step: Fix n N and assume that after removing any square from any 2
n
× 2
n
grid, the
remainder is tilable. Now take any 2
n+1
×2
n+1
grid and remove a square.
By the induction hypothesis, the 2
n
×2
n
quadrant with the removed square is tilable.
Place a single tromino in the center so that one of its squares lies in each remaining quad-
rant. What’s left of each quadrant is a 2
n
×2
n
grid with one missing square: again tilable
by the induction hypothesis.
By induction, we conclude that every 2
n
×2
n
grid is tilable by trominos after any square is removed.
30
P(n) There is no set-up, base case or conclusion and the word induction is missing. The argument needs some English!
P(n) has not been defined. If you don’t define it, don’t write it!
P(n + 1) is a proposition: it cannot equal a number! Replacing P(n + 1) = with P(n + 1) would correct this.
There are no conditional connectives to indicate the logical flow. Moreover, read top to bottom, the argument is
essentially P(n) P(n + 1) = T, rather than the correct induction step P(n) = P(n + 1) .
64
Exercises 5.1. A reading quiz and several questions with linked video solutions can be found online.
1. Suppose you can move one disk on the Tower of Hanoi per second.
(a) One of the oldest versions of the problem has monks transferring a tower of 64 disks.
Roughly how many years would this take?
(b) In a realistic human lifetime, how large a tower could be moved?
2. Imagine you cut a large large piece of paper in half and stack the two pieces on top of each
other. You then repeat the process, cutting all sheets in half and making a single taller stack.
Cut and stack
If a single sheet of paper has thickness 0.1 mm, how many times would you have to repeat the
cut-and-stack process until the stack of paper reached to the sun? ( 150 million kilometers).
Prove that you are correct.
3. A room contains n people. Everybody wants to shake everyone else’s hand (but not their own).
(a) Suppose n people require h
n
handshakes. If person n + 1 enters the room, how many
additional handshakes are required? Obtain a recurrence relation for h
n+1
in terms of h
n
.
(b) Hypothesize a general formula for h
n
, and prove it by induction.
4. (a) In Example 5.4.2, what is the proposition P(n + 1)?
(b) In the induction step of Example 5.4.2, explain why it would be incorrect to write
P(n + 1) P(n) = (n + 1)
( n + 2)(2n + 3) n(2n + 1)
= (n + 1)(2n
2
+ 7n + 6 2n
2
n)
= 6(n + 1)
2
(c) Extend the Example by proving, by induction, that
n
k=1
k
2
=
1
6
n(n + 1)(2n + 1).
5. Prove by induction that for each natural number n, we have
n
k=0
2
k
= 2
n+1
1.
6. Consider the statement: If n is a natural number, then
n
k=1
k
3
=
1
4
n
2
( n + 1)
2
(a) What, explicitly, is
4
k=1
k
3
?
(b) What would be meant by the expression
n
k=1
n
3
, and why is it different to
n
k=1
k
3
?
(c) Proof the statement by induction.
7. (a) Prove by induction that n N we have 3 | (2
n
+ 2
n+1
).
(b) Give a direct proof that 3 | (2
n
+ 2
n+1
) for all integers n 1.
8. Prove by induction that for every n N we have n 5 or n 6 or n 7 (mod 3).
65
9. Prove by induction that, for all n N,
1 ·2 + 2 · 3 + 3 ·4 + ···+ n(n + 1) =
1
3
n(n + 1)( n + 2)
10. (a) Show, by induction, that for all n N, the number 4 divides the integer 11
n
7
n
.
(b) More generally, prove by induction that (a b) | (a
n
b
n
) for any a, b, n N.
11. (a) Find a formula for the sum of the first n odd natural numbers. Prove your assertion.
(b) Use Theorem 5.2 to give an alternative direct proof of your formula.
12. Find the error in the following “proof of the statement, “All cats have the same color fur.”
Proof. Let P(n) be the proposition, “Any set of n cats have the same color fur.” We prove by
induction on n.
Base case (n = 1): Any cat has the same color fur as itself.
Induction step: Fix n N and assume P(n). Take any set S = {C
1
, C
2
, . . . , C
n+1
} of n + 1 cats.
The set S \{C
1
} has n cats; by the induction hypothesis all have the same color fur. Again
by the induction hypothesis, all cats in S \{C
2
} have the same color fur. Combining these
observations, we see that all cats in S have the same color fur. Since S was arbitrary, we
see that P(n + 1) holds.
By induction, P(n) is true for all n N, which establishes the claim.
13. Use induction, the product rule, and the fact that
d
dx
x = 1 to prove the power law from calculus:
n N,
d
dx
x
n
= nx
n1
14. A (real) polynomial of degree n is a function p(x) = a
n
x
n
+ a
n1
x
n1
+ ··· + a
1
x + a
0
, whose
coefficients a
k
are real numbers and where a
n
= 0.
(a) Prove: for all n N,
d
n
dx
n
e
x
2
= p
n
(x)e
x
2
where p
n
(x) is some polynomial of degree n.
(b) (Hard) Let p(x) be a polynomial of degree n 1. Show p has at most n roots.
(Hint: induct on the degree n)
15. Consider the following scratch work. Determine what result is being proved, then convert the
scratch work into a formal proof of that result.
(1 + x)
n+1
= (1 + x)
n
(1 + x) (1 + nx)(1 + x)
= 1 + x + nx + nx
2
= 1 + (n + 1)x + nx
2
1 + (n + 1)x
66
5.2 Well-ordering and the Principle of Mathematical Induction
In this section we think more carefully about the logic behind induction, by tying it to a fundamental
property of the natural numbers.
Definition 5.6. A non-empty set of real numbers A is well-ordered if every non-empty subset of A
contains a minimum element.
To test if a set A is well-ordered, we need to check all of its non-empty subsets. The definition could be
written as equivalently as follows, where in the second line we expand what is meant by a minimum:
B A such that B = , min B exists.
B A, B = = b B such that x B, b x.
To show that A is not well-ordered, we need only exhibit a non-empty subset B with no minimum.
Examples 5.7. 1. A = {4, 7, π, 19, ln 2} is a well-ordered set. There are 31(!) non-empty subsets of
A, each of which has a minimum element.
Can you justify this fact without listing the subsets? It might be easier to think about why any
finite set A = {a
1
, . . . , a
n
} R is well-ordered. . .
2. The interval A = [3, 10) is not well-ordered. Indeed B = (3, 4) is a non-empty subset which has
no minimum element. While you should believe this, let’s prove it anyway!
We need to prove that b B, x B with x < b. Given any b (3, 4), observe that x :=
b+3
2
satisfies
3 < x < b < 4 from which x B and x < b
You could also argue by contradiction (if b B is min B, then. . . ).
3. The integers Z are not well-ordered. For instance, Z is a non-empty subset of itself and there is
no minimum integer.
You might suspect (wrongly!) that every well-ordered set is finite. That the natural numbers form
a well-ordered infinite set is, for us, an axiom:
31
a foundational claim that forms part of our basic
conception of the natural numbers.
Axiom 5.8 (Well-ordering Principle). N is well-ordered.
Also known as the least natural number principle, the well-ordering principle is used repeatedly in
mathematics. In fact we’ve already done so in this text! Consider the set of positive remainders
generated by the Euclidean algorithm (Theorem 3.16) applied to a > b N:
{. . . , r
2
, r
1
, b, a} N
Well-ordering guarantees that this set has a minimal element r
t
(which turns out to be gcd(a, b)); this
is essentially the argument for Exercise 3.2.8(a).
31
There are many ways to define the natural numbers. Typically well-ordering is either an axiom (essentially part of the
definition) or a theorem. Compare with Exercise 11 for an alternative approach.
67
Armed with this axiom, we can justify the method of proof by induction.
Theorem 5.9 (Principle of Mathematical Induction). For each n N, let P(n) be a proposition.
Additionally make the two standard assumptions for induction:
Base case: P(1) is true
Induction step: n N, P( n) = P(n + 1)
Then P(n) is true for all n N.
Before attempting a proof, consider how the theorem could be written as a pure implication:
P(1)
n N, P(n) = P(n + 1)
=
n N, P(n)
This helps us select a proof strategy: a direct approach seems hard since the conclusion is universal; a
contrapositive approach requires an ugly negation of the hypothesis; a proof by contradiction seems
most sensible since negation of the conclusion is straightforward.
Proof. We argue by contradiction. Assume the base case, the induction step, and that n N for
which P(n) is false. The set of natural numbers
S :=
k N : P(k) is false
is non-empty (since n S). Well-ordering guarantees that s := min S exists. Observe:
s S = P(s) is false.
The base case tells us that s = 1, whence s 1 N.
s 1 < min S = P(s 1) is true.
The induction step (P(s 1) = P(s)) tells us that P(s) is true.
Contradiction: P(s) cannot be both true and false!
Now we have the proof, it is straightforward to extend the principle of induction. For any integer m
(positive, negative or zero), the set
Z
m
= {n Z : n m} = {m, m + 1, m + 2, m + 3, . . .}
is also well-ordered. By changing the base case to P(m) and replacing N with Z
m
, we immediately
obtain the proof of a more general principle of induction.
Corollary 5.10 (Induction with base case m). Fix an integer m. For each integer n m, let P(n) be
a proposition. Suppose:
Base case: P(m) is true
Induction step: n Z
m
, P(n) = P(n + 1)
Then P(n) is true for all n Z
m
.
The intuitive concept is exactly as before, just with a different base case!
P(m) = P(m + 1) = P(m + 2) = P(m + 3) = ···
68
Examples 5.11. 1. For all integers n 2, we have
32
n
k=2
1
k(k 1)
= 1
1
n
()
Base case (n = 2): When n = 2, () reads
2
i=2
1
i(i1)
=
1
2
= 1
1
2
.
Induction step: Assume that () is true for some fixed n 2. Then
n+1
i=2
1
k(k 1)
=
n
i=2
1
k(k 1)
+
1
( n + 1)n
= 1
1
n
+
1
n(n + 1)
(induction hypothesis)
= 1
( n + 1) 1
n(n + 1)
= 1
1
n + 1
which is exactly () when n is replaced by n + 1.
By induction () holds for all integers n 2.
2. For all integers n 4, we claim that 3
n
> n
3
.
We really need a different base case: when n = 3, the claim 3
3
> 3
3
is false! As is often the case,
it helps to do some scratch work first. The induction hypothesis allows us to see that
3
n+1
= 3 ·3
n
> 3n
3
The proof of the induction step therefore hinges on being able to show that 3n
3
(n + 1)
3
.
There are many ways to convince yourself of this: for instance
3n
3
(n + 1)
3
3
n + 1
n
3
=
1 +
1
n
3
(†)
The right side decreases as n increases; since n 4, the right side is at most
5
4
3
=
125
64
< 2,
whence () holds for all n 4.
We now prove the original claim by induction.
Base case (n = 4): Observe that 3
4
= 81 > 64 = 4
3
.
Induction step: Fix n Z
4
and suppose that 3
n
> n
3
. By (†), we see that
3
n+1
= 3 ·3
n
> 3n
3
(n + 1)
3
By induction, we conclude that 3
n
> n
3
whenever n Z
4
.
32
You might have encountered this example as a telescoping series in calculus:
n
k=2
1
k(k 1)
=
1
2 ·1
+
1
3 ·2
+ ··· +
1
n(n 1)
=
1
1
2
+
1
2
1
3
+ ··· +
1
n 1
1
n
= 1
1
n
In calculus, you’d take the limit as n to obtain the infinite series
k=2
1
k(k1)
= 1
69
As a final example, we prove an extended version of de Morgan’s law for sets (Theorem 4.14(a)).
Example 5.12. For any collection of sets A
1
, . . . , A
n
where n 2, we have
(A
1
··· A
n
)
C
= A
1
C
··· A
n
C
(‡)
Base case (n = 2): A
1
A
2
C
= A
1
C
A
2
C
is precisely the standard de Morgan identity.
Induction step: Fix n N
2
and suppose (‡) holds for all collections of n sets. Given a collection of
n + 1 sets, we see that
(A
1
··· A
n
A
n+1
)
C
=
(A
1
··· A
n
) A
n+1
C
= (A
1
··· A
n
)
C
A
n+1
C
(de Morgan again!)
= A
1
C
··· A
n
C
A
n+1
C
(induction hypothesis)
By induction the claim (‡) holds for any collection of n sets.
We could have approached the argument as a standard induction with base case n = 1. Instead we
deliberately chose the base case n = 2, both to avoid confusion (the trivial A
1
C
= A
1
C
isn’t helpful or
interesting) and to highlight the importance of de Morgan’s law for two sets to the entire argument.
Proof by Minimal Counter-example
Sometimes authors present induction arguments as contradiction proofs in line with Theorem 5.9:
the element s = min S is known as the minimal counter-example. Here are two variations on this idea;
the first is a straight translation of an induction where the base case and induction step are clear.
Examples 5.13. 1. We prove: for all n N
0
,
n
k=0
2
k
= 2
n+1
1.
Suppose to the contrary and let s 0 be the minimal counter-example.
Since
0
k=0
2
k
= 2
0
= 1 = 2
0+1
1, we see that s = 0. (base case)
But then
s
k=0
2
k
= 2
s
+
s1
k=0
2
k
= 2
s
+ 2
s
1 = 2
s+1
1 (induction step)
contradicts the fact that s is a counter-example!
2. We re-prove Theorem 2.37:
2 / Q. Suppose
2 is rational and consider the set
S =
x N : y N with x
2
= 2y
2
Let s = min S and t N be such that s
2
= 2t
2
: plainly t < s. Since s
2
even = s even, we can
write s = 2k, from which
4k
2
= 2t
2
= n
2
= 2k
2
= t S
This contradicts the minimality of m.
This approach is often used in number theory in the guise of Fermat’s method of infinite descent.
70
Aside: Well-ordering more generally Definition 5.6 is a weak version of a much deeper concept.
Informally, to well-order a set means to list its elements in some order so that every non-empty subset
has an initial element with respect to that order.
For instance, the set of negative integers Z
= {. . . , 4, 3, 2, 1} is not well-ordered with respect
to the standard ordering of the integers, but is well-ordered with respect to the reverse ordering
Z
= {−1, 2, 3, 4, . . .}
The principle of mathematical induction is easily modified to accommodate theorems of the form
n Z
, P(n) : the base case is P(1) and the induction step justifies the chain
P(1) = P(2) = P(3) = ···
All the infinite well-ordered sets we’ve thus far seen have “looked like” the natural numbers, how-
ever more esoteric examples exist. For instance, the following well-ordered set looks like two copies
of the natural numbers, one following the other:
A =
0,
1
2
,
2
3
,
3
4
,
4
5
, . . . , 1,
3
2
,
5
3
,
7
4
,
9
5
, . . .
=
1
1
n
: n N
2
1
n
: n N
Every non-empty subset of A really does have a minimum! It is possible to modify induction to
apply to propositions indexed by well-ordered sets like this, though an extra step is required to deal
with limit elements (like 1 A) with no immediate predecessor. If your further studies include set
theory, you’ll likely spend much time considering well-orders and their associated ordinals.
Exercises 5.2. A reading quiz and several questions with linked video solutions can be found online.
1. Prove that the interval (2, 5] has no minimum element.
2. Prove that every finite set of real numbers is well-ordered.
3. (a) Suppose that n 3. Prove that
n+1
n
2
< 2.
(b) Hence or otherwise, prove that n
2
< 2
n
for all natural numbers n 5.
4. Consider the following result. For every natural number n 2,
1
1
4
1
1
9
1
1
16
···
1
1
n
2
=
n + 1
2n
(a) If the statement is written in the form n N
2
, P(n) , what is the proposition P(n)?
(b) Prove the result by induction.
5. Prove the geometric series formula: if r = 1 and n N
0
, then
n
k=0
r
k
=
1r
n+1
1r
6. For all integers n 3, prove that
n
k=3
1
k(k2)
=
3
4
2n1
2n(n1)
7. Prove: for any n N,
n
i=1
1
i
2
< 2
(Hint: prove the stronger fact that
n
i=1
1
i
2
< 2
1
n
for all n 2)
71
8. The set A
3
= {1, 2, 3} satisfies the property that the sum of its elements (1 + 2 + 3 = 6) is
divisible by every element of A
3
.
(a) Use induction to prove that for any n 3, there is a set A
n
of n natural numbers such that
the sum of its elements is divisible by every element of A
n
.
(b) Prove by contradiction that no set of two natural numbers satisfies this property.
9. Suppose that x
2
+ 4y
2
= 3z
2
has a solution (x, y, z) where all three are positive integers.
(a) By considering remainders modulo 3, prove that 3 | z. Thus create a new solution (X, Y, Z)
in positive integers, where Z < z.
(b) Use the method of minimal counter-example to prove that x
2
+ 4y
2
= 3z
2
has no solutions
where x, y, z N.
10. We use the fact that N
0
is well-ordered to prove the division algorithm (Theorem 3.3).
If m Z and n N, then unique q, r Z such that m = qn + r and 0 r < n.
Given m, n, define
S = N
0
m + nZ
=
k N
0
: k = m qn for some q Z
(a) (Existence) Show that S is a non-empty subset of N
0
. By well-ordering, define r := min S.
Prove that 0 r < n.
(b) (Uniqueness) Suppose two pairs of integers (q
1
, r
1
) and (q
2
, r
2
) satisfy m = q
i
n + r
i
and
0 r
1
, r
2
< n. Prove that r
1
= r
2
.
11. (Hard) We consider a version of Peano’s axioms for the natural numbers.
i. (Initial element) 1 N
ii. (Successor function) f (n) = n + 1 is a function f : N N
iii. (No predecessor of the initial element) 1 ∈ range( f )
iv. (Unique predecessor/order) f is injective: m + 1 = n + 1 = m = n
v. (Induction) Any subset A N with the following properties equals N:
1 A and a A, a + 1 A
(a) Replace N with Z in each axiom. Which are true and which false?
(b) Let T =
( m, n) : m, n N
be the set of all ordered pairs of natural numbers.
i. Let f : T T be the function f (m, n) = (m + 1, n). Letting the pair (1, 1) play the role
of 1, and f the successor function, decide which of Peano’s axioms are satisfied by T.
ii. Repeat the question for the same initial element and
f : T T : (m, n) 7
(
( m 1, n + 1) if m 2
( m + n, 1) if m = 1
(c) Prove that range( f ) = N \ {1}: every element except 1 is the successor of something.
(Hint: let A = {1} range( f ) in the induction axiom)
(d) Prove that N, as defined by Peano, is well-ordered (with respect to x < x + 1, etc.).
72
5.3 Strong Induction
The principle of mathematical induction (Theorem 5.9) is often known as weak induction. The pri-
mary difference with strong induction is that the induction step assumes more than one proposition.
Theorem 5.14 (Principle of Strong Induction). Let l m be fixed integers and suppose P(n) is a
proposition, one for each n Z
m
. Suppose:
Base case(s): P(m), P(m + 1), . . . , P(l) are true
Induction step: n l,
P(m) P(m + 1) ··· P(n)
= P(n + 1)
Then P(n) is true for all n m.
Exercise 6 provides a proof by showing that strong and weak induction are equivalent. We instead
concentrate on a few examples. The main additional challenge of strong induction lies in deter-
mining how many base cases are required and in identifying precisely how to phrase the induction
hypothesis: in practice one rarely needs to use all the propositions P(m), . . . , P(n) explicitly.
Example 5.15 (Fibonacci numbers). This famous sequence ( f
n
)
n=1
= (1, 1, 2, 3, 5, 8, 13, 21, . . .) is
defined by the 2
nd
-order recurrence relation
(
f
n+1
= f
n
+ f
n1
if n 2
f
1
= f
2
= 1
While the Fibonacci sequence seems to be increasing, it also appears to be less than doubling at each
step, suggesting the claim
n N, f
n
< 2
n
We prove this using strong induction. Two base cases are suggested since the sequence is defined by
two initial conditions ( f
1
= f
2
= 1): in the language of the Theorem, m = 1 and l = 2. Moreover, the
fact that each term from f
3
onwards is the sum of its two predecessors suggests that the induction step
requires the explicit use of two propositions.
Proof. Base cases (n = 1, 2): f
1
= 1 < 2
1
and f
2
= 1 < 2
2
.
Induction step: Fix n 2 and suppose
33
that f
n1
< 2
n1
and f
n
< 2
n
. Then
f
n+1
= f
n
+ f
n1
< 2
n
+ 2
n1
< 2
n
+ 2
n
= 2
n+1
By induction, f
n
< 2
n
for all n N.
The Fibonacci numbers satisfy many identities which can often be established by induction (e.g.,
Exercises 3 & 4).
33
To follow Theorem 5.14 precisely, we would assume that f
k
< 2
k
for all k n. Feel free to write this if you like, though
our phrasing is more typical. Since we only make explicit use of two cases in the induction step, it is clearer to state these
concretely rather than introducing a new variable k.
73
Before seeing further examples, it is instructive to consider why we really needed strong induction to
prove our Fibonacci example. Here are two broken attempts to prove the claim by weak induction.
Broken Proof A. Base case (n = 1): f
1
= 1 < 2
1
.
Induction step: Fix n 2 and suppose that f
n
< 2
n
. Then
34
f
n+1
= f
n
+ f
n1
< 2
n
+ ????
What is the problem? The induction hypothesis assumes f
n
< 2
n
, but not anything about f
n1
: we
are stuck! Let’s correct this flaw by making the induction hypothesis as in the correct proof.
Broken Proof B. Base case (n = 1): f
1
= 1 < 2
1
.
Induction step: Fix n 2 and suppose that f
n1
< 2
n1
and f
n
< 2
n
. Then
f
n+1
= f
n
+ f
n1
< 2
n
+ 2
n1
< 2
n
+ 2
n
= 2
n+1
By induction, f
n
< 2
n
for all n N.
Where is the problem now? Consider the first instance, n = 2, in which the induction step is invoked:
f
3
= f
2
+ f
1
< 2
2
+ 2
1
We haven’t proved enough base cases to get us started: the single base case establishes f
1
< 2
1
, but
not f
2
< 2
2
. The induction step correctly establishes the chain of implications
P(1) P(2) = P(3), P(3) P(4) = P(5), P(4) P(5) = P(6), . . .
but we can only get the process started if we prove both base cases P(1) and P(2).
The moral here is to try the induction step as scratch work. Your attempt should tell you if you need
strong induction and how many base cases are required.
Example 5.16. A sequence of integers (a
n
)
n=0
is defined by
(
a
n+1
= 5a
n
6a
n1
if n 1
a
0
= 0, a
1
= 1
We prove by induction that a
n
= 3
n
2
n
for all n N
0
.
Proof. Base cases (n = 0, 1): a
0
= 0 = 3
0
2
0
and a
1
= 1 = 3
1
2
1
.
Induction step: Fix n 1 and suppose thata
k
= 3
k
2
k
for all k n. Then
a
n+1
= 5a
n
6a
n1
= 5(3
n
2
n
) 6(3
n1
2
n1
)
= (15 6)3
n1
+ (10 6)2
n1
= 3
n+1
2
n+1
By induction, a
n
= 3
n
2
n
for all n N
0
.
34
The induction step requires n 2 so as to invoke the recurrence relation: f
n+1
= f
n
+ f
n1
is meaningless when n = 1
( f
n1
= f
0
doesn’t exist).
74
For another sequential induction example in the same vein, see Exercise 5.3 where three base cases
are required, and the induction step explicitly uses three propositions.
To see strong induction in all its glory, where the induction step requires all previous propositions,
we prove the existence part of the Fundamental Theorem of Arithmetic, which states that all integers
2 can be (uniquely) expressed as a product of primes: e.g., 3564 = 2
2
×3
4
×11.
Theorem 5.17. Every integer n 2 is either prime or a product of primes.
This provides the missing piece in our discussion of Euclid’s Theorem (2.41) on the existence of
infinitely many primes. First recall Definition 2.40: p N
2
is prime if and only if its only positive
divisors are itself and 1. A non-prime q N
2
is said to be composite: a, b N
2
such that q = ab.
Proof. We prove by induction.
Base case (n = 2): The only positive divisors of 2 are itself and 1, hence 2 is prime.
Induction step: Fix n 2 and suppose that every natural number k satisfying 2 k n is either prime
or a product of primes. There are two possibilities:
n + 1 is prime. Certainly n + 1 is divisible by a prime!
n + 1 is composite. Then n + 1 = ab for some natural numbers a, b 2. Clearly a, b n;
by the induction hypothesis, both are prime or the product of primes. Therefore n + 1 is
also the product of primes.
By induction we see that all natural numbers n 2 are either prime, or a product of primes.
Think carefully about why only one base case is required!
Exercises 5.3. A reading quiz and several questions with linked video solutions can be found online.
1. Define sequence (b
n
)
n=1
as follows:
(
b
n+1
= 2b
n
+ b
n1
if n 2
b
1
= 3, b
2
= 6
Prove by induction that b
n
is divisible by 3 for all n N.
2. Define a sequence (c
n
)
n=0
:
(
c
n+1
=
49
8
c
n
225
8
c
n2
if n 2
c
0
= 0, c
1
= 2, c
2
= 16
Prove by induction (use three base cases!) that c
n
= 5
n
3
n
for all n N
0
.
3. Let f
n
be the n
th
Fibonacci number (Example 5.15). Prove the following by induction n N:
(a)
n
k=1
f
2
k
= f
n
f
n+1
(b) f
n
3
2
n2
(Hints: Weak induction is good enough for (a); why?)
75
4. Extending Exercise 3(b), prove Binet’s formula for the n
th
Fibonacci number:
f
n
=
1
5
ϕ
n
ˆ
ϕ
n
where ϕ =
1
2
(1 +
5) and
ˆ
ϕ =
1
2
(1
5)
(ϕ is the famous golden ratio: ϕ,
ˆ
ϕ are the solutions to the quadratic equation x
2
= x + 1)
5. Prove by induction that every n N can be written in the form
n = 2
r
1
+ 2
r
2
+ ···+ 2
r
for some N and distinct integers r
1
, r
2
, . . . r
0.
(Hints: try proving in the style of Theorem 5.17; consider the cases when n + 1 is even/odd separately)
6. Prove the principle of strong induction (Theorem 5.14) by applying weak induction to a new
family of propositions Q(n) via:
Q(n) P(m) P(m + 1) ··· P(n)
7. Consider the proof of Theorem 5.17.
(a) If the Theorem is written in the form n N
2
, P(n), what is the proposition P(n)?
(b) Explicitly carry out the induction step for the three situations n + 1 = 9, n + 1 = 106 and
n + 1 = 45. How many different ways can you perform the calculation for n + 1 = 45?
(c) Explain why it is only necessary in the induction step to assume that all integers k satisfy-
ing 2 k
n+1
2
are prime or products of primes.
8. In this question we use the alternative definition of prime (Exercise 3.2.13).
35
An integer p 2 is prime if and only if a, b N, p | ab = p | a or p | b.
Let p be prime, let n N, and let a
1
, . . . , a
n
be natural numbers such that p | a
1
a
2
···a
n
. Prove
by induction that,
p | a
i
for some i {1, 2, . . . , n}
(Hint: n = 1 isn’t really part of the induction, but you can treat it as a base case)
9. The Fundamental Theorem of Arithmetic states that every integer n 2 can be written as a product
of prime factors in a unique way (up to reordering of the prime factors). In other words,
i. n = p
1
p
2
··· p
k
for some primes p
1
, p
2
, . . . , p
k
, and,
ii. If n = q
1
q
2
···q
for primes q
1
, q
2
, . . . , q
, then k = and p
i
= q
i
after possibly reordering
the prime factors.
Part i. is Theorem 5.17. Using Exercise 8, or otherwise, supply a proof of part ii.
35
This is the strict definition of prime, while Definition 2.40 is the definition of irreducible. For the integers, Exercise 3.2.13
says that these concepts are synonymous.
76
6 Set Theory, Part II
In this chapter we return to set theory and consider several more-advanced constructions.
6.1 Cartesian Products
You have been working with Cartesian products for years, referring to a point in the plane R
2
by its
Cartesian co-ordinates (x, y), an ordered pair where each co-ordinate (x, y) is a member of the set R. The
same approach can be used for any sets.
Definition 6.1. The Cartesian product of sets A and B is the set of ordered pairs
A × B =
(a, b) : a A and b B
Otherwise said: (a, b) A × B a A and b B.
Examples 6.2. 1. The Cartesian product of the real line R with itself is the usual xy-plane.
As you’ve seen in other classes, rather than writing R × R which
is unwieldy, we denote this set
R
2
=
(x, y) : x, y R
More generally, the set of n-tuples of real numbers is
36
R
n
=
(x
1
, x
2
, . . . , x
n
) : x
1
, x
2
, . . . , x
n
R
= R ×R ×···×R
| {z }
n times
2
2
4
y
2 2 4
x
(2, 3)
2. If A = {1, 2, 3} and B = {α, β}, then the Cartesian product of A and B is
A × B =
(1, α), (1, β), (2, α), (2, β), (3, α), (3, β)
The order of terms in an ordered pair really matters: the Cartesian product with the roles re-
versed is
B × A =
( α, 1), (β, 1), (α, 2), (β, 2), (α, 3) , (β, 3)
While A × B = B × A, note that both Cartesian products have six (= 3 ·2 = 2 ·3) elements.
3. The menu in a restaurant might be summarized set-theoretically:
Mains = {fish, steak, eggplant, pasta}, Sides = {asparagus, salad, potatoes}
The Cartesian product Mains ×Sides is the set of all possible meals consisting of one main and
one side. It should be obvious that there are 4 ×3 = 12 possible meal choices.
The last two examples illustrate one of the simplest properties of Cartesian products, in a result which
indeed justifies the very use of the word product!
36
Strictly this should be defined inductively, e.g., R
3
:= R
2
×R =
n
(x, y), z
: x, y, z R
o
, but this is very tedious!
77
Theorem 6.3. If A and B are finite sets, then
|
A × B
|
=
|
A
|
·
|
B
|
.
Proof. Label the elements of each set and list the elements of A × B lexicographically. If
|
A
|
= m and
|
B
|
= n, then
A × B =
(a
1
, b
1
), (a
1
, b
2
), (a
1
, b
3
), ··· (a
1
, b
n
),
(a
2
, b
1
), (a
2
, b
2
), (a
2
, b
3
), ··· (a
2
, b
n
),
.
.
.
.
.
.
.
.
.
.
.
.
(a
m
, b
1
), (a
m
, b
2
), (a
m
, b
3
), ··· (a
m
, b
n
)
Every element of A ×B is listed exactly once. There are m rows and n columns, so
|
A × B
|
= mn.
Set Identities These may be established as we’ve done previously (Section 4): convert everything
into propositions regarding elements of sets and use basic logic. If you’re feeling more confident, you
might also be able to invoke previously established rules of set algebra.
Examples 6.4. 1. Consider the complement of a Cartesian product A × B. If you had to guess an
expression for (A × B)
C
, you might mistakenly think it is A
C
×B
C
. Let us think more carefully:
(x, y) (A × B)
C
¬((x, y) A × B) (definition of complement)
¬(x A and y B) (definition of A × B)
x ∈ A or y ∈ B (de Morgan (logic))
By contrast, (x, y) A
C
× B
C
x / A and x / B, so (A × B)
C
= A
C
× B
C
. Indeed the
complement of a Cartesian product is not a Cartesian product! For more on this, see Exercise 5.
2. Let A, B, C, D be any sets. We prove that (A ×B) (C × D) (A C) × (B D).
(x, y) (A × B) (C × D) = (x, y) A × B or (x, y) C × D
= (x A and y B) or (x C and y D)
= (x A or x C) and (y B or y D)
= x A C and y B D
= (x, y) (A C) × (B D)
All implications except the red arrow are in fact biconditional.
To convince yourself of its truth, first consider what must be
true about x, then do the same for y. The picture provides a
visualization where A, B, C, D are intervals of real numbers:
(A ×B) (C × D) is the solid shaded region.
(A C) ×(B D) is the larger dashed square.
If x C \ A and y B \D, then (x, y) (A C) ×(B D) but
(x, y) (A × B) (C × D), so we do not, in general, expect
these sets to be equal.
A × B
C × D
A
C
B
D
78
Exercises 6.1. A reading quiz and several questions with linked video solutions can be found online.
1. (a) Suppose that A = {1, 2} and B = {3, 4, 5}. State the set A × B in roster notation.
(b) Sketch both A × B and B × A using dots in R
2
. What do you observe about your pictures?
(c) If A, B, C are any sets, we may define
A × B × C =
(a, b, c) : a A, b B, c C
If C = {6, 7} and A, B are as above, state the set A × B × C in roster notation.
2. Rewrite the condition (x, y) (A
C
B) × (C \ D) in terms of (some of) the propositions
x A, x A, x B, x B, y C, y C, y D, y D
3. Consider the intervals A = [2, 5] and B = (0, 4) of real numbers.
(a) Express the set (A \ B)
C
in interval notation, as a disjoint union of intervals.
(b) Draw a picture of the set (A \ B)
C
×(B \ A).
(Be careful: In this problem B = (0, 4) is an interval (a subset of R), not a point in R
2
!)
4. A straight line in R
2
is a subset of the form
A
a,b,c
=
(x, y) : ax + by = c
, for some constants a, b, c, with a, b not both zero
(a) Draw the set A
1,2,3
. Is it a Cartesian product?
(b) Which straight line subsets in the plane R
2
are Cartesian products? Otherwise said, find a
condition on the constants a, b, c for which the set A
a,b,c
is a Cartesian product.
5. Draw a picture, similar to that in Example 6.4.2, which illustrates the fact that
(A × B)
C
= (A
C
× B
C
) (A
C
× B) (A × B
C
)
Now give a rigorous proof of the claim.
6. Let A = [1, 3], B = [2, 4] and C = [2, 3]. Prove or disprove:
(A × B) (B × A) = C ×C
(Hint: Draw the sets A × B, B × A and C ×C in the Cartesian plane)
7. Prove that A B = (A × B) (B × A) = .
(Hint: try the previous question first)
8. Let A, B, C be sets. Prove:
(a) A ×(B C) = (A × B) (A ×C)
(b) A ×(B C) = (A × B) (A ×C)
(c) A ×(B \C) = (A × B) \ (A ×C)
79
9. (a) Give an explicit example of sets A, B, C, D such that
(A × B) (C × D) = (A C) ×(B D)
(b) For any sets A, B, C, D, prove that
(A C) × (B D) = (A × B) (A × D) (C × B) (C × D)
10. Prove by induction. For all n N, if A
1
, . . . , A
n
are finite sets, then
|
A
1
×···× A
n
|
=
|
A
1
|
···
|
A
n
|
11. (a) Suppose
|
A
|
= 3, and
|
B
|
= 4. What are the minimum and maximum values for the
cardinalities
|
(A × B) (B × A)
|
and
|
(A × B) (B × A)
|
?
(b) (Hard) More generally, suppose
|
A
|
= m,
|
B
|
= n and
|
A B
|
= c. What can you say
about the cardinalities
|
(A × B) (B × A)
|
and
|
(A × B) (B × A)
|
?
12. Let A and B be nonempty sets. Define functions π
1
: A × B A and π
2
: A × B B by
π
1
(a, b) = a and π
2
(a, b) = b respectively (these are called projection maps).
(a) If A = B = R and X = [1, 3], Y = (2, 4], then X × Y A × B. Compute the images
π
1
(X ×Y) and π
2
(X ×Y).
(b) Let Z be any set and suppose there are functions ρ
1
: Z A and ρ
2
: Z B. Show that
there is a unique function h : Z A × B such that ρ
1
= π
1
h and ρ
2
= π
2
h.
13. Let E N ×N be the smallest subset satisfying the following conditions:
Base case: ( 1, 1) E
Generating Rule I: If (a, b) E then (a, a + b) E
Generating Rule II: If (a, b) E then (b, a) E
(a) Show in detail that ( 4, 3) E.
(b) Show by induction that for every n N, (1, n) E.
(c) (Hard!) Show that E =
(a, b) N ×N : gcd(a, b) = 1
.
(Hint: what do the generating rules have to do with the Euclidean algorithm?)
14. (Hard) A strict set-theoretic definition requires that ordered pair (a, b) be defined as a set for
instance (a, b) :=
a, {a, b}
. We prove that (a, b) = (c, d) a = c and b = d.
(a) The regularity axiom of set theory says there is no set a for which a a. Use this to prove
that the cardinality of
a, {a, b}
is two.
(b) Prove that (a, b) = (c, d) =
a = c and b = d
or
a = {c, d} and c = {a, b}
(c) In the second case, prove that there exists a set S such that a S a. The axiom of
regularity also says that this is illegal. Conclude that (a, b) = (c, d) a = c and b = d.
80
6.2 Power Sets
Thus far we have used the operations of subset, complement, union, intersection and Cartesian prod-
uct to build new sets from old. There is essentially only one further method available.
Definition 6.5. Let A be a set. Its power set P(A) is the set of all subsets of A:
P(A) =
B : B A
Otherwise said: B P(A) B A.
Examples 6.6. 1. The set A = {1, 3, 7} has the following subsets:
0-element subsets:
1-element subsets: {1}, {3}, {7}
2-element subsets: {1, 3}, {1, 7}, {3, 7}
3-element subsets: {1, 3, 7}
Gathering these together yields the power set:
P(A) =
, {1}, {3}, {7}, {1, 3}, {1, 7}, {3, 7}, {1, 3, 7}
The power set therefore has eight elements. Be absolutely certain you understand the difference
between and . Here are eight propositions; which are true and which false?
37
(a) 1 A (b) 1 P(A) (c) {1} A (d) {1} P(A)
(e) 1 A (f) 1 P(A) (g) {1} A (h) {1} P(A)
2. The set B =
n
1,
{2}, 3
o
has precisely two elements, namely 1 and
{2}, 3
. As before, we
gather the subsets of B in a table:
0-element subsets:
1-element subsets: {1},
n
{2}, 3
o
2-element subsets:
n
1,
{2}, 3
o
Remember that to make a subset out of a single element you surround the element with braces:
1 B = {1} B = {1} P(B)
{2}, 3
B =
n
{2}, 3
o
B =
n
{2}, 3
o
P(B)
Using different-sized braces is essential here! The power set of B has four elements:
P(B) =
, {1},
n
{2}, 3
o
,
n
1,
{2}, 3
o
As a further exercise in making careful use of notation, we prove a simple theorem.
37
Only (a), (d), and (g) are true. Make sure you understand why!
81
Theorem 6.7. If A B, then P(A) P(B).
Proof. Suppose A B and let C P(A). We must show that C P(B).
C P(A) = C A (definition of power set)
= C B (since C A and A B)
= C P(B) (definition of power set)
We conclude that P(A) P(B).
The converse to this is also true: P(A) P(B) = A B. Try proving it yourself.
Cardinality and Power Sets
Let’s investigate the relationship between the cardinality of a set and its power set. Consider a few
basic examples where we list all of the subsets, grouped by cardinality.
Set A 0-elements 1-element 2-elements 3-elements
|
P(A)
|
1
{a} {a} 1 + 1 = 2
{a, b} {a}, {b} {a, b} 1 + 2 + 1 = 4
{a, b, c} {a}, {b}, {c} {a, b}, {a, c}, {b, c} {a, b, c} 1 + 3 + 3 + 1 = 8
You’ve seen this pattern before: we are looking at the first few lines of Pascal’s Triangle!It should be
no surprise that if
|
A
|
= 4, then
|
P(A)
|
= 1 + 4 + 6 + 4 + 1 = 16. The progression 1, 2, 4, 8, 16, . . . in
the final column immediately suggests a general result.
Theorem 6.8. Let A be a finite set. Then
|
P(A)
|
= 2
|
A
|
.
Conjuring a proof may seem daunting given how little we know about A; only its cardinality. By
introducing a variable n for the cardinality and rephrasing the theorem
n N
0
,
|
A
|
= n =
|
P(A)
|
= 2
n
induction seems like a sensible approach. But what might the induction step look like? The basic idea
is to view a set with n + 1 elements as the disjoint union of a set with n elements and a single-element
set. It is instructive to see an example of the strategy before writing the proof.
Example 6.9. Let B = {1, 2, 3}. Delete 3 B to create a smaller set
A = B \ {3} = {1, 2}
In the table, the subsets of Y B are split into two groups depending on whether
3 Y. Each subset Y B either has the form X or X {3} where X A.
Plainly B has twice the number of subsets of A; two for each subset X A.
Subsets of B
X X {3}
{3}
{1} {1, 3}
{2} {2, 3}
{1, 2} {1, 2, 3}
This method of pairing is exactly mirrored in the induction step of our formal proof.
82
Proof. We prove by induction on the cardinality of A. For each n N
0
, consider the proposition
Every set A with cardinality n has
|
P(A)
|
= 2
n
()
Base case (n = 0): If n = 0, then A = (Lemma 4.10). But then P(A) = {} =
|
P(A)
|
= 1 = 2
0
.
Induction step: Fix n N
0
and assume () is true for this n. Let B be any set with n + 1 elements.
Choose an element b B and define A = B \ {b}. The subsets of B may be separated into two
types:
1. Subsets X B which do not contain b.
2. Subsets Y B which contain b.
In the first case, X is a subset of A.
In the second case we can write Y = X {b}, where X is again a subset of A.
Each subset X A therefore corresponds to precisely two subsets X and X {b} of B. Since
|
A
|
= n, the induction hypothesis () tells us there are 2
n
subsets X A, whence
|
P(B)
|
= 2
|
P(A)
|
= 2
n+1
By induction, () holds for all n N
0
.
Exercise 7 gives an alternative proof.
Example 6.10. You might erroneously expect the sets P(A × B) and P(A) × P(B) to be the same.
Here is a simple counter-example to convince you otherwise!
Let A = {a} and B = {b, c}. Think about cardinalities:
|
P(A × B)
|
= 2
|
A×B
|
= 2
|
A
||
B
|
= 2
2
= 4
|
P(A) × P(B)
|
=
|
P(A)
||
P(B)
|
= 2
|
A
|
2
|
B
|
= 2
|
A
|
+
|
B
|
= 2
3
= 8
Since the cardinalities are different, the sets cannot be equal: P(A × B) = P(A) × P(B). But what
about subset? Might the smaller set be a subset of the larger? Again the answer is no, as can be seen
by computing the sets explicitly.
A × B =
(a, b), (a, c)
= P(A × B) =
, {(a, b)}, {(a, c)}, {(a, b), (a, c)}
The elements of P(A × B) are sets of ordered pairs. By contrast, the elements of P(A) × P(B) are
ordered pairs of sets:
P(A) × P(B) =
, {a}
×
, {b}, {c}, {b, c}
=
n
,
,
, {b}
,
, {c}
,
, {b, c}
,
{a},
,
{a}, {b}
,
{a}, {c}
,
{a}, {b, c}
o
The elements of the two sets have completely different types, so there is no way that one could be a
subset of the other!
83
Exercises 6.2. A reading quiz and several questions with linked video solutions can be found online.
1. For each A, find P(A) and
|
P(A)
|
.
(a) A = {1, 2} (b) A = {1, 2, 3} (c) A =
(1, 2), (2, 3)
(d) A =
, 1, {a}
(e) A =
n
1, 2
, 3,
4, {5}
o
(f) A =
n
(1, 2), 3,
4, {5}
o
2. Let A = {1, 3} and B = {2, 4}.
(a) Draw a picture of the set A × B as a subset of R
2
.
(b) Compute P(A × B).
(c) What is the cardinality of P(A) × P(B)?
3. Determine whether the following statements are true or false. Justify your answers.
(a) If {7} P(A), then {7} / A.
(b) Suppose that A P(B) C where
|
A
|
= 2. Then
|
C
|
can be 5, but
|
C
|
cannot be 4.
(c) If
|
B
|
=
|
A
|
+ 1, then P(B) has at least two more elements than P(A).
(d) If A, B, C, D are cardinality-two subsets of {1, 2, 3}. Then at least two of them are equal.
4. Here are three incorrect proofs of Theorem 6.7: A B = P(A) P(B). Why does each fail?
(a) Let x P(A). Since A B, we have x B. Therefore x P(B), and so P(A) P(B).
(b) Let A = {1, 2} and B = {1, 2, 3}. Then
P(A) =
, {1}, {2}, {1, 2}
, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, B
= P(B)
(c) Let {x} P(A). Then x A. Since A B, we have x B. But then {x} P(B).
5. (a) Prove that P(A) P(B) P(A B). Provide a counter-example to show that we do not
expect equality.
(b) Does anything change if you replace with in part (a)? Justify your answer.
6. (a) For any set A, show there is an injection ι : A P(A). (Explicitly construct a map, and
show that it is one-to-one.)
(b) Is there any set A such that A P(A) = ?
7. If you’ve studied combinatorics, you’ll know that the binomial coefficient
(
n
r
)
=
n!
r!(nr)!
denotes
the number of distinct ways one can choose r objects from a set of n objects.
(a) Prove directly:
(
n+1
r
)
=
(
n
r
)
+
(
n
r1
)
whenever 1 r n.
(b) (Hard) Prove by induction that n N
0
,
n
r=0
(
n
r
)
= 2
n
, by using part (a) in the induction
step.
(c) Explain why part (b) provides an alternative proof of Theorem 6.8.
If you found this easy, try proving the binomial theorem: n N
0
, (x + y)
n
=
n
r=0
(
n
r
)
x
r
y
nr
.
84
6.3 Indexed Collections of Sets: Union and Intersection Revisited
In Definition 4.11 we defined the union of two sets A B = {x : x A or x B}, which inductively
extends to any finite union of sets
A
1
··· A
n
= {x : x A
k
for some k}
In this section we consider a stronger definition and compute unions and intersections of (potentially)
infinite collections of sets.
Definition 6.11. Given a set of sets {A
n
} (each A
n
is a set!), we form its union and intersection:
[
A
n
= {x : x A
n
for some n} x
[
A
n
n such that x A
n
\
A
n
= {x : x A
n
for all n} x
\
A
n
n we have x A
n
We say that {A
n
} is pairwise disjoint if A
m
A
n
= whenever m = n.
For all examples in this section, the sets A
n
are indexed: each n lies in some indexing set, typically
N, Z or R. It is typical to decorate the union/intersection symbols to indicate this: e.g., if n N we
might use the notation
S
nN
A
n
or
S
n=1
A
n
.
Example 6.12. Here is a simple (finite) example to get us used to the notation. Let
A
1
= {1, 3, 5}, A
2
= {2, 3, 4, 6}, A
3
= {1, 2, 3, 6}
The indexed collection {A
n
: n I} is indexed by I = {1, 2, 3}. Then
3
[
n=1
A
n
= A
1
A
2
A
3
= {1, 2, 3, 4, 5, 6}
3
\
n=1
A
n
= A
1
A
2
A
3
= {3}
Lemma 6.13. Let {A
n
} be a set of sets. For any A
m
{A
n
},
A
m
[
A
n
and
\
A
n
A
m
A proof is almost immediate from the definition: can you supply it?
Nested Collections
When a collection of sets is indexed by the natural numbers N in such a way that successive sets
satisfy a subset relation, we describe the collection as nested, for instance
A
1
A
2
A
3
···
Since A
n
A
1
for all n, we see that
S
n=1
A
n
= A
1
:
x
[
n=1
A
n
n N, x A
n
x A
1
Computing the intersection in such a situation typically requires much more care. . .
85
Example 6.14. Consider the nested collection {A
n
: n N} of half-open intervals A
n
=
0,
1
n
:
m n =
1
n
1
m
= A
n
A
m
= A
1
A
2
A
3
···
The union is therefore
S
n=1
[0,
1
n
) = A
1
= [0, 1).
Before considering the full intersection, we first compute all finite intersections. The nesting condition
says that a finite intersection is simply the smallest of the listed sets: for any constant m N,
m
\
n=1
0,
1
n
= A
1
··· A
m
= A
m
=
0,
1
m
To find the infinite intersection, it is very tempting to take limits:
\
n=1
0,
1
m
?
= lim
m
m
\
n=1
0,
1
m
?
=
h
0, lim
m
1
m
= [0, 0)
This is mathematical garbage! Nothing you know about limits justifies either questionable equality.
Moreover, the ‘answer [0, 0) could only mean the empty set, which is incorrect: we claim that
\
n=1
0,
1
n
= {0}
Proof. First observe that
x
\
n=1
A
n
=
\
n=1
0,
1
n
n N, 0 x <
1
n
Certainly x = 0 satisfies these inequalities. It remains to eliminate the other possibilities.
If x < 0, then x / A
1
= [0, 1) and so x /
T
A
n
.
Suppose that x > 0. There exists
38
N large enough so that
1
N
x. Otherwise said,
x / A
N
, whence x /
T
A
n
.
If the last part of the argument seems difficult, try an example! If x = 0.13, observe that
0.1 < 0.13 = x / A
10
= x /
\
n=1
A
n
x0
1
10
A
5
By modifying the endpoints of the sets A
n
we obtain slightly different results:
\
n=1
0,
1
n
) =
\
n=1
0,
1
n
] =
\
n=1
0,
1
n
] = {0}
How would the arguments differ from what we did above?
The moral is that you cannot na
¨
ıvely apply limits to sequences of sets. If thinking about limits helps
your intuition, great, but you can’t trust it blindly!
38
The existence of N
1
x
should be intuitive; it is in fact guaranteed by the Archimedean property (Exercise 2.4.12).
86
An indexed collection can also be nested the other way round, in which case the intersection is
straightforward (though unions need more work)
A
1
A
2
A
3
··· =
\
n=1
A
n
= A
1
Examples 6.15. Here are a few more simple examples of computing unions and intersections of
indexed collections; some are nested, some not.
1. Let A
n
= [n, n + 1) R, for each n Z. For example A
3
= [3, 4) and A
17
= [17, 16).
Every real number lies in precisely one such set (the sets A
n
are pairwise disjoint), whence
[
nZ
A
n
= R and
\
nZ
A
n
=
To prove the former, note that x [n, n + 1) where n = x is the greatest integer less than or
equal to x: i.e., x R, we have x A
x
, whence R
S
nZ
A
n
(the reversed subset inclusion
is trivial since each A
n
R).
2. For each n N, let A
n
= [n, n] be a closed interval. This is a nested collection
A
1
A
2
A
3
··· =
\
n=1
A
n
= A
1
= [1, 1]
Similarly to the previous example, x R we have x A
n
where n is any integer
|
x
|
: we
conclude that
S
n=1
A
n
= R.
3. For each n N, let A
n
= {x R :
x
2
1
<
1
n
}. Before computing the union and intersection
of these sets, it is helpful to write each set as a pair of intervals. Note that
x
2
1
<
1
n
1
n
< x
2
1 <
1
n
r
1
1
n
<
|
x
|
<
r
1 +
1
n
The sets are nested: A
1
A
2
A
3
A
4
···, where
A
n
=
q
1 +
1
n
,
q
1
1
n
q
1
1
n
,
q
1 +
1
n
=
[
n=1
A
n
= A
1
= (
2, 0) (0,
2)
For the intersection,
2
2
0
A
1
A
2
A
3
A
4
A
5
n N, x A
n
n N,
x
2
1
<
1
n
x
2
1 = 0
It follows that
T
n=1
A
n
= {1, 1}.
4. Let A
0
= {0, 1}, A
n
= {1} is n 1 is odd, and A
n
= {2} if n 2 is even. Then,
\
n=1
[
k=n
A
k
=
[
k=1
A
k
!
[
k=2
A
k
!
··· = {0, 1, 2} {0, 1}{0, 1}··· = {0, 1}
Think about why x
T
n=1
S
k=n
A
k
x lies in infinitely many of the sets A
n
.
87
Unions: Don’t Confuse Sets and Elements
When working with large unions, it is easy to confuse two sets:
{A
n
} is a set of sets, each element of which is some set A
n
.
S
A
n
is the set whose elements lie in at least one A
n
.
It is important to understand the difference! Sometimes the indexed collection itself is the object of
interest, other times we may want to use its union or intersection to define something new.
Example 6.16 (Projective space). Let A
m
be the line
39
through the ori-
gin in R
2
with gradient m R {}. Since every point in R
2
lies on
such a line, and distinct lines intersect at the origin, we see that
[
A
m
= R
2
and
\
A
m
=
(0, 0)
The indexed collection is known as projective space
A
1
A
2
A
4
A
3
A
0
A
A
1
2
A
3
4
A
1
5
P( R
2
) =
A
m
: m R {}
and is interesting in its own right. Each element of projective space is a line, making P(R
2
) a very
different set to R
2
. This example also shows that indexing sets don’t have to be simple sets of integers!
In the next example we use an infinite union to define an interesting set.
Example 6.17 (Finite Decimals). For each n N, let A
n
be the set of decimals of length n,
A
n
=
0.a
1
a
2
. . . a
n
: where each a
i
{0, 1, . . . , 9}
For example 0.134 A
3
. Since 0.134 = 0.1340, we also have 0.134 A
4
. This is a nested collection
A
1
A
2
A
3
A
4
··· =
\
nN
A
n
= A
1
=
0, 0.1, . . . , 0.9
Now consider unions. If m N, then
m
[
n=1
A
n
= A
m
=
x [0, 1) : x has a decimal representation of length m
You might guess that the infinite union would be the entire
40
interval [0, 1], but this is incorrect:
x
[
nN
A
n
n N such that x A
n
x is a decimal with some finite length n
The infinite union
S
A
n
is precisely the set of x [0, 1) which have a finite decimal representation!
This is far from the entire interval: many rational numbers are excluded (e.g.,
1
3
= 0.3333 ··· /
S
A
n
),
and the union contains no irrational numbers.
39
The symbol is used to indicate the vertical line A
with ‘infinite gradient.’
40
We would include 1 = 0.9999 ···
88
Optional! We finish this section with a bit of fun, using an infinite intersection to create a fractal set.
Example 6.18 (Cantors middle-third set). Starting with the interval C
0
= [0, 1], construct a sequence
of sets C
n
by repeatedly removing the middle third of all intervals in C
n
.
C
0
= [0, 1]
C
1
= [0,
1
3
] [
2
3
, 1]
C
2
= [0,
1
9
] [
2
9
,
1
3
] [
2
3
,
7
9
] [
8
9
, 1]
.
.
.
0
1
3
2
3
1
The sequence is drawn up to C
9
, though you’ll have to zoom in a long way to see the detail!
Cantors middle-third set is defined to be the infinite intersection C :=
T
n=0
C
n
.
Cantor’s set has several interesting properties which we state non-rigorously.
Zero Measure (length) It should seem reasonable to write
len(C
0
) = 1, len(C
1
) =
2
3
, len(C
2
) =
2
3
2
, . . . , len(C
n
) =
2
3
n
, . . .
where len(C
n
) is the sum of the lengths of all intervals in C
n
. Since C C
n
for all n, we conclude
that len(C) = 0: Cantor’s set contains no intervals of positive length.
Infinite Cardinality Cantor’s set contains the endpoints of every interval removed at any stage of
its construction. In particular,
1
3
n
C for all n N
0
, whence C is an infinite set.
41
Self-similarity Let f , g : R R be functions f (x) =
1
3
x and
g(x) =
1
3
x +
2
3
. Since C
n+1
= f (C
n
) g(C
n
), we conclude
C = f (C) g(C)
C
f (C) g(C)
Cantor’s set consists of two shrunken copies of itself, a classic property of fractals.
We’ll analyze Cantor’s set a little and consider a related construction in Exercises 14 & 15. Other
fractal sets with a similar construction include the Sierpi´nski carpet and the von Koch snowflake.
Exercises 6.3. A reading quiz and several questions with linked video solutions can be found online.
1. Let I = {1, 3, 4}. Determine
S
rI
S
r
and
T
rI
S
r
, where each S
r
= [r 1, r + 3] is an interval.
2. For each integer n, consider the set B
n
= {n}× R.
(a) Draw a picture (in the Cartesian plane) of
S
4
n=2
B
n
= B
2
B
3
B
4
.
(b) Draw a picture of the set C = [1, 5] × {2, 2}.
(Careful! [1, 5] is an interval, while {2, 2} is a set containing two points)
(c) Compute
S
4
n=2
B
n
C.
(d) Compute
S
4
n=2
(
B
n
C
)
. Compare with your answer to part (c).
41
In fact it is more than merely infinite, it is uncountably so, as we’ll discuss in Chapter 8. The bizarre contrast between
this and the zero measure property was part of the reason Cantor introduced his set.
89
3. Give an example of four subsets A, B, C, D of {1, 2, 3, 4}such that all intersections of two subsets
are different.
4. For each of collection, define an interval A
n
such that the given collection is {A
n
: n N}.
Then find both the union and intersection of the collection.
(a)
[1, 2 + 1), [1, 2 +
1
2
), [1, 2 +
1
3
), . . .
(b)
( 1, 2), (
3
2
, 4), (
5
3
, 6), (
7
4
, 8), . . .
(c)
(
1
4
, 1), (
1
8
,
1
2
), (
1
16
,
1
4
), (
1
32
,
1
8
), (
1
64
,
1
16
), . . .
5. For each real number x, let A
x
= {3, 2} {y R : y > x}. Find
S
xR
A
x
and
T
xR
A
x
.
6. Use Definition 6.11 to prove that A
1
A
2
A
3
··· =
T
nN
A
n
= A
1
7. Let A
n
be the set of decimals of length n, as described in Example 6.17.
(a) Prove directly that the cardinality of A
n
is 10
n
.
(b) Prove by induction that
|
A
n
|
= 10
n
.
(c) Prove that
S
n=1
A
n
Q.
(d) Explain why
1
9
/
S
n=1
A
n
.
8. Suppose that n N, A
n
= and m n = A
m
A
n
. Prove or disprove the following:
(a)
293
S
n=1
A
n
= (b)
293
T
n=1
A
n
= (c)
S
nN
A
n
= (d)
T
nN
A
n
=
9. Compute the set
S
n=1
T
k=n
[
1
k
, 2 +
1
k
]. For a general family of sets {A
n
: n N} Explain why it
is is reasonable to write
x
[
n=1
\
k=n
A
k
x lies in all except finitely many A
n
10. Let {A
n
: n I} and {B
n
: n I} be indexed families of sets. Give explicit examples for which
the following hold:
(a)
(
S
nI
A
n
)
(
S
nI
B
n
)
=
S
nI
(A
n
B
n
)
(b)
(
T
nI
A
n
)
(
T
nI
B
n
)
=
T
nI
(A
n
B
n
)
11. (De Morgan’s laws) Let {A
n
: n I} be an indexed family of sets and B a set. Prove
(a) B \
(
S
nI
A
n
)
=
T
nI
(B \ A
n
)
(b) B \
(
T
nI
A
n
)
=
S
nI
(B \ A
n
)
12. Suppose we are working in a universal set U (so every set is considered a subset of U). Give an
explanation for why it makes sense to define
T
nI
A
n
= U when I = .
90
13. (Hard) Let A
n
= {
m
n
Q : 0 < m < n, m N}, for each n N.
(a) State A
1
, A
2
, A
3
, A
4
explicitly.
(b) Prove that A
m
A
pm
for any p N.
(c) Argue that
S
nN
A
n
= Q (0, 1).
(d) Argue that further
S
nN
A
2n
= Q (0, 1).
(e) Extend your proof to show that, for any fixed p N,
S
nN
A
pn
= Q (0, 1).
14. (Hard) A ternary representation
42
of a number x [0, 1] is an expression
x =
n=1
a
n
3
n
=
a
1
3
+
a
2
3
2
+
a
3
3
3
+ ··· where each a
n
{0, 1, 2}
We write x = [0.a
1
a
2
a
3
···]
3
. For example [0.12]
3
=
1
3
+
2
3
2
=
5
9
.
(a) Verify that [0.02101]
3
=
64
243
, [0.22222 ···]
3
= 1 and [0.020202020 ···]
3
=
1
4
.
(Hint: You’ll need the geometric series formula
n=1
r
n
=
r
1r
for the latter two)
(b) Let C
n
be the n
th
set in the construction of Cantor’s middle-third set C (Example 6.18).
Prove by induction that C
n
is the set of all x [0, 1] with a ternary representation whose
first n digits are only 0 or 2.
(Hints: Use C
n+1
= f (C
n
) g(C
n
); What does division by 3 do to a ternary representation?)
(c) Argue that
1
4
C, but that it is not an endpoint of any of the deleted middle-thirds re-
moved during the construction of C.
15. (Hard) We construct a modified Cantor set and fractal curve. Starting with F
0
= [0, 1], repeat-
edly delete the third quarter segment of each interval to obtain a sequence of sets F
0
, F
1
, F
2
, . . .:
F
1
= [0,
1
2
] [
3
4
, 1], F
2
= [0,
1
4
] [
3
8
,
1
2
] [
3
4
,
7
8
] [
15
16
, 1], . . .
(a) Prove that the sum of the lengths of all of all line segments in F
n
is
3
4
n
.
(b) Prove that
T
n=1
F
n
contains no intervals of positive length.
(c) Instead of deleting the third quarter of each line seg-
ment, replace it with the other three sides of a square.
The first three steps and the result of applying the pro-
cess infinitely many times are shown in the pictures.
After step 1 the curve has length
1
=
3
2
and the area
under the curve is A
1
=
1
4
2
. After step 2 the length is
2
=
9
4
and the area A
2
= A
1
+
1
4
A
1
+
1
16
A
1
=
21
4
4
.
i. Find the length
n
of the curve after n steps. What
is the ‘length’ of the resulting fractal curve?
ii. Repeat for the area under each curve F
n
. Prove that
the area between the fractal and the x-axis is
1
8
.
42
Analogous to a decimal representation x =
n=1
a
n
10
n
=
a
1
10
+
a
2
10
2
+
a
3
10
3
+ ··· where a
n
{0, 1, 2, . . . , 9}.
91
7 Relations and Partitions
The mathematics of sets is rather basic until one has a notion of how to relate elements of sets to each
other. We are already familiar with several examples of this, for instance:
1. The usual order of numbers (e.g., 3 < 7) is a way of relating/comparing two elements of R.
2. A function f : A B relates elements in a set A with those in B.
In this chapter we discuss a general framework based on the Cartesian product (Section 6.1).
7.1 Binary Relations on Sets
Definition 7.1. Let A and B be sets. A (binary) relation R from A to B is a set of ordered pairs
R A ×B
A relation on A is a relation from A to itself. The domain and range of R are the sets
dom(R) =
a A : b B, (a, b) R
range(R) =
b B : a A, (a, b) R
If (a, b) R we can also write a R b, and say a is related to b.’ Similarly a R b means (a, b) R.
Examples 7.2. 1. R =
(1, 3), (2, 2), (2, 3), (3, 2), (4, 1), (5, 2)
defines a relation on N. Various true
statements about this relation include
(2, 2) R, (4, 2) / R, 2 R5, 3 R 2
In this case dom(R) = {1, 2, 3, 4, 5} and range(R) = {1, 2, 3}.
2. R =
[1, 3) ×(3, 4]
(2t + 1, t
2
) : t [
1
2
, 2]
is a relation on R. This time
we have dom(R) = [1, 5] and range(R) = [
1
4
, 4].
3. For any set A, the set R =
(a, a) : a A
is a relation on A. The relation
R is simply ‘equals:’
(a, b) R a = b
4. On R, the relation can be graphed: we plot all points (x, y) R
2
such
that x y.
5. If A is the set of all humans, we may define R A × A by
(a, b) R a, b have a parent/child or sibling relationship
In this example, the mathematical use of relation is similar to that in English:
I am related to my sister, and my mother is related to me.
6. If A is a set, then is a relation on the power set P(A) (the set of subsets).
For instance, if A = {1, 2, 3} then {1} {1, 3} but {1, 3} {1}.
0
2
4
0 2 4
Example 1
0
2
4
0 2 4
Example 2
2
2
2 2
x
y
Example 4
7. If f : A B is a function then
a, f (a)
: a A
is a relation! We’ll revisit this in Section 7.2.
92
With abstract relations, there are only a small number of things we can do.
Definition 7.3. Given a relation R A × B, its inverse R
1
B × A is the set
R
1
=
( b, a) B × A : (a, b) R
To find the elements of R
1
, you simply switch the components of each ordered pair in R.
We say that R is symmetric if R = R
1
(requires A = B): i.e., (x, y) R (y, x) R.
Theorem 7.4. For any relations R, S A × B:
1. dom(R
1
) = range(R) 2. range(R
1
) = dom(R)
3. (R
1
)
1
= R 2. R S R
1
S
1
5. (R S)
1
= R
1
S
1
4. (R S)
1
= R
1
S
1
7. If A = B, then R R
1
and R R
1
are both symmetric
Proof. Here are two of the arguments. Try the others yourself.
4. Suppose R S. Then,
( b, a) R
1
= (a, b) R (definition of inverse)
= (a, b) S (since R S)
= (b, a) S
1
(definition of inverse)
Therefore R
1
S
1
. Replacing R, S with R
1
, S
1
and applying part 1, we also see that
R
1
S
1
= (R
1
)
1
(S
1
)
1
= R S
7. We prove the first half. By part 3,
( R R
1
)
1
= R
1
(R
1
)
1
= R
1
R = R R
1
Example (7.2.1, cont.). R =
(1, 3), (2, 2), (2, 3), (3, 2), (4, 1), (5, 2)
is not
symmetric. Indeed
R
1
=
(3, 1), (2, 2), (3, 2), (2, 3), (1, 4), (2, 5)
= R
as should be plain: e.g., ( 1, 3) R but (3, 1) / R. However,
R R
1
=
(2, 2), (2, 3), (3, 2)
and
R R
1
=
(1, 3), (3, 1), (2, 2), (2, 3), (3, 2), (4, 1), (1, 4), (5, 2), (2, 5)
0
2
4
0 2 4
are both symmetric. Observe the symmetry in the picture. One obtains R
1
by reflecting
43
R in the
line y = x: a symmetric relation on R has reflection symmetry in this line.
43
Just as one does for inverse functions in calculus. . .
93
Exercises 7.1. A reading quiz and practice question can be found online.
1. Let R be the relation on {0, 1, 2} defined by
0 R0 0 R 1 2 R1
(a) Write R as a set of ordered pairs. What are its domain and range?
(b) What is the inverse of R?
2. (a) Let R be the relation on R defined by a Rb
|
a b
|
= 1. Is this relation symmetric?
(b) Let S be the relation on R defined by
a S b x Q \{0} such that a = x
2
b
Is this relation symmetric?
3. Draw pictures of the following relations on the set of real numbers R.
(a) R =
(x, y) : y 2 and y x and y 2 x
(b) S =
(x, y) : (x 4)
2
+ (y 1)
2
9
State the domain and range and draw the inverse of each relation.
4. A relation is defined on N by a R b
a
b
N. Let c, d N. Under what conditions can we
write c R
1
d?
5. Let R {1, 2, 3, 4} × {1, 2, 3, 4} be the relation
R =
(1, 3), (1, 4), (2, 2), (2, 4), (3, 1), (3, 2), (4, 4)
(a) Find dom(R), range(R) and R
1
.
(b) Compute the relations R R
1
and R R
1
, and check that they are symmetric.
6. For the relation R =
(x, y) : x y
on N, what is R
1
, and what is the intersection RR
1
?
7. Let R Z × Z be the relation m R n iff m | n. Compute R R
1
.
8. Let A be a set with
|
A
|
= 4. What is the maximum number of elements that a relation R on A
can contain such that R R
1
= ?
9. Give formal proofs of the remaining parts of Theorem 7.4.
10. Let R and S be two symmetric relations on a set A.
(a) Show R S is symmetric.
(b) Does R S have to be symmetric? Give a proof or counterexample.
11. Let R be a relation on a set A and define S = R R
1
. Prove that S is the smallest symmetric
relation on A containing R in the following sense: if
T =
n
T A × A : T symmetric and R T
then
S =
\
T T
T
(S is known as the symmetric closure of R)
94
7.2 Functions revisited
In Section 4.3, we na
¨
ıvely defined a function f : A B as a rule associating to each element a A an
element f (a) B. But what do we mean by a rule? We address this issue by turning Example 7.2.7
on its head: a function f : A B is precisely its graph.
Example 7.5. The function f : [0, 4] [ 0, 2] : x 7
x corresponds to
the relation
x,
x
: x [0, 4]
[0, 4] × [0, 2]
0
2
0 2 4
x
x
(x,
x)
The difficulty is that we cannot use the notation f (a) until we know that we have a function. . .
Definition 7.6. A function from A to B is a relation f A × B satisfying two conditions:
1. dom( f ) = A (each a A is related to at least one b B)
2. (a, b
1
), (a, b
2
) f = b
1
= b
2
(each a A is related to at most one b B)
A relation f A × B is a function if and only if every a A is the first entry of exactly one ordered
pair (a, b) f . This is simply an abstraction of the vertical line test from calculus.
Example 7.7. Let A = [0, 4] and B = [0, 5]. Two relations f , R A × B are drawn below.
The first relation defines a function f : A B since every a A corresponds to exactly one b B:
the vertical line through any a A intersects the graph in exactly one point (a, b).
The second relation R does not define a function. In fact it fails both parts of the definition:
1. The vertical line through
˜
a A does not intersect the graph:
˜
a / dom(R).
2. The vertical line through a A intersects the graph in two points (a, b
1
) = (a, b
2
).
0
2
4
0 2 4
a
b
dom( f ) = A
range( f )
0
2
4
0 2 4
a
b
1
b
2
˜
a
dom(R) = A
range(R)
Injectivity (Definition 4.18) can be rephrased in this new context: f : A B injective means
( a A) (a
1
, b), (a
2
, b) f = a
1
= a
2
Surjectivity has the same meaning as before: range( f ) = B.
95
Example 7.8. Let A = {1, 2, 3} and B = {p, q, r}. The relation
f =
(1, r), (2, p), (3, r)
satisfies both conditions necessary to be a function. In elementary
language, f (1) = r, f (2) = p and f (3) = r. Moreover f is:
Not injective since ( 1, r), (3, r) f and 1 = 3
Not surjective since range( f ) = {p, r} = B
The inverse relation
f
1
=
(r, 1), (p, 2), (r, 3)
B × A
is not a function due to failing both conditions of Definition 7.6.
1. dom( f
1
) = {p, r} = B. The vertical line through b = q does
not intersect (the graph of) f
1
.
2. (r, 1) f
1
and (r, 3) f
1
, but 1 = 3. The vertical line
through b = r intersects f
1
twice.
Note how the manner of these failures are identical to the failures of
injectivity and surjectivity. . .
1 2 3
A
B
p
q
r
The function f : A B
1
2
3
B
A
p q r
f
1
B × A: not a function
The example highlights one advantage of the relational approach: the inverse of a function f : A B
always exists; it is the inverse relation f
1
B × A. The question is whether f
1
is also a function. From
the example and our discussions in Section 4.3, you should strongly suspect the answer.
Theorem 7.9. Let f : A B be a function and consider its inverse relation f
1
B × A. Then
f
1
is a function f is bijective (both injective and surjective)
Proof. Recalling Definition 7.6, we see that f
1
is a function if and only if the two conditions hold:
1. dom( f
1
) = B
2. (b, a
1
), (b, a
2
) f
1
= a
1
= a
2
By Theorem 7.4, condition 1 is equivalent to range( f ) = B; that is, f is surjective.
Condition 2 is equivalent to (a
1
, b), (a
2
, b) f = a
1
= a
2
: i.e., f is injective.
Example (7.5 cont.). f =
(x,
x) : x [0, 4]
[0, 4] × [0, 2] is
Injective since (x
1
, y), (x
2
, y) f = x
1
= y
2
and x
2
= y
2
, whence x
1
= x
2
.
Surjective since range( f ) =
x : x [0, 4]
= [0, 2].
Since f is bijective, its inverse relation is a function: f
1
=
( y, y
2
) : y [0, 2]
or, as we’d normally
write, f
1
: [0, 2] [0, 4] : y 7→ y
2
.
96
Exercises 7.2. A reading quiz and practice questions can be found online.
1. Suppose f is the relation
f =
(1, 1), (2, 3), (3, 5), (4, 7)
{1, 2, 3, 4} × {1, 2, 3, 4, 5, 6, 7}
(a) Show that we have a function f : {1, 2, 3, 4} {1, 2, 3, 4, 5, 6, 7}. Can you find a concise
formula f (x) to describe this function?
(b) Is f injective? Justify your answer.
(c) Suppose g {1, 2, 3, 4} × B is another relation so that the graphs of f and g are identical:
that is, as sets,
(a, f (a)) : a {1, 2, 3, 4}
=
(a, g(a)) : a {1, 2, 3, 4}
If g is a bijective function, what is B?
2. Decide whether each of the following relations are functions. For those which are, decide
whether the function is injective and/or surjective.
(a) R =
(x, y) [1, 1] ×[1, 1] : x
2
+ y
2
= 1
(b) S =
(x, y) [1, 1] ×[0, 1] : x
2
+ y
2
= 1
(c) T =
(x, y) [0, 1] × [1, 1] : x
2
+ y
2
= 1
(d) U =
(x, y) [0, 1] × [0, 1] : x
2
+ y
2
= 1
3. (a) Express the function f : R R : x 7 x
4
+ 3 as a relation.
(b) What is the inverse relation f
1
?
(c) Use Definition 7.6 to prove that the relation f
1
is not a function.
(d) Prove directly from Definition 4.18 that f is not injective and not surjective. Compare your
arguments with your answer to part (c).
4. Repeat the previous question for f : R R : x 7
x
2
4x + 5.
5. (a) Express the function f : R R : x 7 x
3
as a relation on R.
(b) What is the inverse relation f
1
? Is it a function? Justify your answer.
6. Let A be any set and define the relation id
A
=
(a, a) : a A
on A. Show that id
A
is a bijective
function (it is called the identity function on A). What is its inverse?
7. Consider the relation f =
(x, x) : x Q
(x, 0) : x Q
R
2
(a) Prove that f is a function R R.
(b) Is f injective? Surjective? Explain.
8. Suppose f A × B is a function.
(a) If U A, explain why it would be reasonable to write the image of U as
f ( U) =
b B : u U with (u, b) f
(Recall Definition 4.16 if you’re unsure what this means)
(b) If V B, how would you write the inverse image f
1
(V) in this language?
97
7.3 Equivalence Relations & Partitions
What do we mean when we say that two objects are equal? Mathematicians use the word flexibly,
often in reference to non-identical objects which share some common property.
44
You’ve been doing
this for years, indeed our very first result (Theorem 1.1: even + even = even) has exactly this flavor.
To help develop a more flexible notion of equality, consider three important concepts.
Example 7.10. Let X be a set. The following are immediate:
Reflexivity: x X, x = x
Symmetry: (x, y X) x = y = y = x
Transitivity: (x, y, z X) x = y and y = z = x = z
We turn this simple example on its head to create an abstract, generalized notion of equality.
Definition 7.11. We define the following properties for a relation
45
on a set X:
Reflexivity: x X, x x (every element of X is related to itself)
Symmetry: x y = y x (if x is related to y, then y is related to x)
Transitivity: x y and y z = x z (if x is related to y and y is related to z,
then x is related to z)
An equivalence relation on X is a relation satisfying all three properties.
Example 7.10 says that ‘equals’ is indeed an equivalence relation on any set X. Things would be very
boring if this were the only example. . .
Example 7.12. Define a relation on Z by
x y x y is even (otherwise said, x y (mod 2))
We claim that is an equivalence relation on Z.
Reflexivity: x Z, x x = 0 is even, hence x x.
Symmetry: Given x, y Z, x y = x y even = y x even = y x.
Transitivity: Given x, y, z Z,
x y and y z = x y even and y z even
= x z = (x y) + (y z) is even (Theorem 1.1!)
= x z
As we’ll see shortly, an equivalence relation algebraically characterizes what it means for elements to
share a common property: here x y if and only if they have the same parity.
44
This goes back at least to Euclid, who used equal to refer to congruent triangles. To Euclid, congruent triangles were
essentially identical and therefore not worth distinguishing.
45
Symmetry is precisely as in Definition 7.3. As we’ve done, the universal quantifiers for symmetry and transitivity are
typically hidden. The symbol (‘tilde,’ or ‘twiddles’) is commonly used for an abstract equivalence relation. It is the same
symbol used to denote similar triangles: congruence and similarity are both equivalence relations on the set of triangles!
98
It would also be somewhat dull if every relation were an equivalence relation. In fact most are not.
Examples 7.13. 1. Consider the relation on the natural numbers N. We check each condition:
Reflexivity: True. x R, x x.
Symmetry: False. For example, 2 3 but 3 2.
Transitivity: True. x, y, z R, if x y and y z, then x z.
Plainly is not an equivalence relation on N.
2. Let X be the set of lines in the plane and define
1
R
2
1
,
2
intersect.
Reflexivity: True. Every line intersects itself, so R for all X.
Symmetry: True. For all lines
1
,
2
A, if
1
intersects
2
,
then
2
intersects
1
.
Transitivity: False. As the picture illustrates, if
1
,
3
are par-
allel and
2
crosses both, then
1
R
2
,
2
R
3
and
1
R
3
.
1
3
2
Again R is not an equivalence relation on X.
3. The relation R =
(1, 1), (1, 3), (3, 1), (3, 3)
is not an equivalence relation on X = {1, 2, 3}.
Reflexivity: False. For instance ( 2, 2) / R (otherwise said, 2 R2).
Symmetry: True. In all four cases, (x, y) S = (y, x) R is clear.
Transitivity: True. Check this yourself; there are six valid combinations!
The usefulness of equivalence relations comes when we group together all related elements.
Definition 7.14. Given an equivalence relation on X, the equivalence class of x X is the set
[x] = {y X : y x} (y [x] y x)
If y [x], we call y a representative of the equivalence class [x]. The quotient of X by is the set of
equivalence classes:
X
=
[x] : x X
(read X modulo ’)
Examples 7.15. We start by revisiting our first two examples.
1. (Example 7.10) For the equivalence relation x y x = y on a set X, each equivalence class
has precisely one element [x] = {x}; the quotient is the set of singleton subsets,
X
=
{x} : x X
2. (Example 7.12) For the relation x y x y is even, there are two equivalence classes:
[0] = {. . . , 4, 2, 0, 2, 4, . . .} = 2Z = {even integers}
[1] = {. . . , 3, 1, 1, 3, 5, . . .} = 1 + 2Z = {odd integers}
and the quotient has two elements:
Z
=
[0], [1]
.
99
Note that any even number is a representative of the first class in the even/odd example: for instance
4 [0] since 4 0 = 4 is even.
Indeed [4] = [ 0], which leads us a simple piece of bookkeeping. . .
Lemma 7.16. Suppose is an equivalence relation. Then x y [x] = [y].
Observe how the proof uses all three defining properties of an equivalence relation.
Proof. () By reflexivity, x [x]. Thus [x] = [y] = x [y] = x y.
( ) Suppose x y. We prove that [x] = [y] by showing that each side is a subset of the other.
( ) Let z [x] . By definition, z x. By transitivity,
z x and x y = z y = z [y]
( ) By symmetry, we also have y x. Repeating the previous argument yields [y] [x].
Example 7.17. Let X = {students taking this course} and defined, x, y X,
x y x achieves the same letter-grade as y
It should be clear that this is an equivalence relation (try saying out loud what reflexivity, symme-
try & transitivity mean here!). There is one equivalence class for each letter-grade awarded, each
class being the set of all students who obtain a given grade. If we label the equivalence classes
A
+
, A, A
, B
+
, . . . , F, where, say, B = {students obtaining a B-grade}, then the quotient
X
=
A
+
, A, A
, B
+
, . . . , F
is essentially the set of possible letter-grades! Suppose Laura & Jorge both achieve a B
+
; both are
representatives of this equivalence class and the following propositions are all true:
Laura B
+
, Jorge B
+
, Laura Jorge, [Laura] = [Jorge] = B
+
The example is a special case of a general construction.
Theorem 7.18. Suppose f is a function with domain X. Then
x y f (x) = f (y)
defines an equivalence relation on X. There is one equivalence class [x] = {y X : f (x) = f (y)} for
each value in range( f ).
The proof is an exercise. A suitable function in the previous example would be
f : X
A
+
, A, A
, B
+
, . . . , F
where f (x) = x’s letter grade”
This converse to the theorem always holds: if is an equivalence relation then the so-called canonical
map f : X
X
: x 7 [x] satisfies x y f (x) = f (y)!
100
Examples 7.19. 1. The function
f : Z {0, 1, 2, 3, 4} : x 7 x
2
(mod 5) (take the remainder on division by 5)
defines an equivalence relation on Z:
x y x
2
y
2
(mod 5)
2. The function f : R
2
R : (x, y) 7 x
2
+ y
2
defines an equivalence relation
46
on R
2
:
(x, y) (v, w) x
2
+ y
2
= v
2
+ w
2
As stated in the Theorem, there is one equivalence classes for
each element r
2
range( f ) = R
+
0
: if x
2
+ y
2
= r
2
, then
[(x, y)] =
n
( v, w) R
2
: v
2
+ w
2
= r
2
o
is the circle of radius r centered at the origin. The equivalence class
[(1, 0)] highlighted in the picture. Moreover, the quotient set is
R
2
= {circles centered at the origin}
1
1
w
1 1
v
Partitions When you cut a cake, each crumb ends up in exactly one slice. To partition a set is to do
precisely this: split into disjoint subsets so that each element lies in exactly one subset.
Definition 7.20. Let X be a set. A collection {A
n
} of non-empty subsets A
n
X partitions X if
1. X =
S
A
n
(each x X lies in at least one subset A
n
)
2. If A
m
= A
n
, then A
m
A
n
= (each x X lies in at most one
47
subset A
n
)
Partitions are intimately related to equivalence relations, as the next example illustrates.
Example 7.21. Partition X = {1, 2, 3, 4, 5} into subsets
A
1
= {1, 3}, A
2
= {2, 4}, A
3
= {5}
and consider the relation on X defined by
48
x y x, y are in the same subset A
n
Run through the checklist: is reflexive, symmetric & transitive; it is an equivalence relation! More-
over, its equivalence classes are precisely the partitioning subsets A
1
, A
2
and A
3
:
[1] = [3] = {1, 3} = A
1
, [2] = [4] = {2, 4} = A
2
, [5] = {5} = A
5
46
Be careful: is a subset of R
2
×R
2
, whereas each equivalence class is a subset of R
2
!
47
Distinct sets A
n
are pairwise disjoint (Definition 4.11). It is sometimes useful in examples to permit A
m
= A
n
.
48
Otherwise said, is the set
(1, 1), (1, 3) , (3, 1) , (3, 3), (2, 2), (2, 4), (4, 2), (4, 4), ( 5, 5)
X × X.
101
This tight relationship between partitions and equivalence relations is completely general: equiva-
lence relations provide a straightforward algebraic method of working with partitions.
Theorem 7.22. 1. If is an equivalence relation on X, then its equivalence classes partition X.
2. A partition {A
n
} of X defines an equivalence relation on X by
x y A
n
such that x, y A
n
Its equivalence classes are the distinct subsets A
n
: otherwise said,
X
= {A
n
}.
In short, equivalence relations and partitions are essen-
tially the same thing!
49
The picture illustrates part 2
and the cake-cutting metaphor:
A
1
= [a], A
2
= [b] = [c],
b c, a b, a c
XXXXX
a
a
b
b
c
c
partition
A
1
A
2
A
3
A
4
A
5
Before reading the proof, look back at every example of an equivalence relation in this section and
convince yourself that the equivalence classes really do partition the ‘big set.’ In both parts of the
proof look for where the assumptions are used—reflexive, symmetric, transitive in part 1; the two
partition conditions in part 2—and think about why they are needed.
Proof. 1. Given an equivalence relation on X, we must establish two claims:
(a) Every x X lies in some equivalence class. This follows by reflexivity: for each x X,
x x = x [x]
Every element of X lies in the equivalence class defined by itself!
(b) Distinct equivalence classes are pairwise disjoint: [x] = [y] = [x] [y] = . We establish
the contrapositive. If [x] [y] = , then z [x] [y]. But then
z x and z y = x z and z y (symmetry)
= x y (transitivity)
= [x] = [y] (Lemma 7.16)
2. We need only demonstrate the reflexivity, symmetry and transitivity of .
Reflexivity: X =
S
A
n
= every x X lies in some A
n
. Thus x x for all x X.
Symmetry: x y = A
n
such that x, y A
n
= y, x A
n
= y x.
Transitivity: If x y and y z, then A
m
, A
n
such that x, y A
m
and y, z A
n
. Then
y A
m
A
n
= A
m
A
n
= = A
m
= A
n
= x, z A
n
= x z
49
Even more is true. If you think carefully, conditions 1 & 2 in the definition of partition (7.20) now form a disguised
version of the vertical line test for the canonical map (Theorem 7.18)!
102
Exercises 7.3. A reading quiz and practice questions can be found online.
1. Show that x y x y (mod 3) defines an equivalence relation on Z. What are the
equivalence classes?
2. (a) Let be the relation on Z defined by a b a + b is even. Show that is an equiva-
lence relation and determine its equivalence classes.
(b) If ‘even’ is replaced by ‘odd’ in part (a), which of the properties reflexive, symmetric,
transitive does now possess?
3. For each equivalence relation on R
2
, identify the equivalence classes and draw several of them.
(a) (a, b) (c, d) ab = cd (b) (v, w) (x, y) v
2
w = x
2
y
4. Let X = {1, 2, 3, 4, 5, 6}. The distinct equivalence classes resulting from an equivalence relation
on X are {1, 4, 5}, {2, 6}, and {3}. What is ? Give your answer as a subset of X × X.
5. is a relation on any set of sets. Is reflexive, symmetric, transitive? Prove your assertions.
6. Suppose X is a set with at least two elements. Which of the properties reflexive, symmetric,
transitive are satisfied by the relation =?
7. Let X = {ax
3
+ bx
2
+ cx + d : a, b, c, d R} be the set of polynomials of degree 3. Define a
relation R on X by
p R q p and q have a common real root
x R : p(x) = q(x)
For instance p(x) = (x 1)
2
and q(x) = x
2
1 have the root 1 in common, so p Rq. Determine
which of the properties reflexive, symmetric and transitive are possessed by R.
8. Let A = {2
m
: m Z}. A relation is defined on the set Q
+
of positive rational numbers by
a b ab
1
A
Show that is an equivalence relation and describe the elements in the equivalence class [3].
9. A relation is defined on the set X = {a + b
2 : a, b Q, a + b
2 = 0} by x y
x
y
Q.
Show that is an equivalence relation and determine the distinct equivalence classes.
10. For the purposes of this question, a real number is x small if
|
x
|
1. Let R be the relation on
the set of real numbers defined by x Ry x y is small.
Prove or disprove: R is an equivalence relation on R.
11. Find the equivalence classes for the relation in Example 7.19.1.
12. For each relation R on Z, decide whether it is reflexive, symmetric, or transitive, and whether
it is an equivalence relation.
(a) a Rb a b (mod 3) or a b (mod 4)
(b) a Rb a b (mod 3) and a b (mod 4)
13. For Example 7.13.3, compute the ‘classes’ [x] = {y X : xRy}. What do you observe?
103
14. Let X = {1, 2, 3}. Define the relation S =
(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (3, 1), (3, 3)
on X.
(a) Which of the properties reflexive, symmetric, transitive are satisfied by S?
(b) Let A
n
= {x X : x S n}. Show that {A
1
, A
2
, A
3
} do not partition X.
(c) Repeat parts (a) and (b) for the relation T on X, where
T =
(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 3)
(Warning! Some of the sets A
1
, A
2
, A
3
might be the same in these examples)
15. (Example 7.19.2) Prove directly that the circles A
r
=
(x, y) : x
2
+ y
2
= r
2
partition R
2
: i.e.,
R
2
=
[
r0
A
r
and A
r
1
A
r
2
= = A
r
1
= A
r
2
16. Determine whether each collection {A
n
: n R} partitions R
2
. Sketch several of the sets A
n
.
(a) A
n
=
(x, y) R
2
: y = 2x + n
(b) A
n
=
(x, y) R
2
: y = (x n)
2
(c) A
n
=
(x, y) R
2
: xy = n
(d) A
n
=
(x, y) R
2
: y
4
y
2
= x n
17. Let X be the set of all humans. If x X, define the set
A
x
= {people who had the same breakfast or lunch as x}
(a) Does the collection {A
x
: x X} partition X? Explain your answer.
(b) Is your answer different if the or in the definition of A
x
is changed to and?
18. A relation R is antisymmetric if
(x, y) R
( y, x) R
= x = y. Give examples of
relations R on X = {1, 2, 3} having the stated property.
(a) R is both symmetric and antisymmetric.
(b) R is neither symmetric nor antisymmetric.
(c) R is transitive but R R
1
is not transitive.
19. Let R be a relation on X and define its reflexive closure S = R
(x, x) : x X
. Prove that S
is reflexive and that, if T is any reflexive relation for which R T , then S T .
20. (a) Prove Theorem 7.18.
(b) If f has domain X, explain why
f
1
( {b}) : b range( f )
forms a partition of X.
21. Define a relation on R
2
\{(0, 0)} by
(x, y) (v, w) λ = 0 such that (λx, λy) = (v, w)
(a) Prove that is an equivalence relation.
(b) What does this relation have to do with projective space P(R
2
) (Example 6.16)?
22. (If you’ve studied linear algebra) We say that square matrices A, B are similar if there exists a
matrix M such that B = MAM
1
.
(a) Prove that similarity is an equivalence relation on the set of n × n matrices.
(b) What is the equivalence class of the identity matrix?
(c) Show that
11 15
5 9
and
4 10
0 6
are similar.
(Hint: diagonalize the matrices!)
104
7.4 Well-definition, Rings and Congruence
We return to our discussion of congruence (Section 3.1) in the context of equivalence relations and
partitions. The important observation is that congruence modulo n is an equivalence relation on Z, each
equivalence class being the set of all integers sharing a remainder modulo n.
Theorem 7.23. For a fixed n N, define x
n
y x y (mod n). Then
n
is an equivalence
relation on Z.
The theorem is merely a generalization of Example 7.12 and Exercise 7.3.1. You should prove this
yourself. The equivalence classes are precisely the integers which are congruent modulo n:
[a] =
x Z : x a (mod n)
=
x Z : x and a have the same remainder as when divided by n
=
x Z : x a is divisible by n
In this language, we can restate what it means for two equivalence classes to be equal.
Lemma 7.24. [a] = [ b] a b (mod n) k Z such that b = a + kn.
If the meaning of any of the above is unclear, re-read the previous section! The equivalence classes of
n
partition the integers into exactly n subsets, one for each remainder. The quotient set is therefore
Z
n
=
[0], [1], . . . , [n 1]
We use this set to define an extremely important object.
Definition 7.25. Define operations +
n
and ·
n
on the quotient set
Z
n
as follows:
[x] +
n
[y] := [x + y], [x] ·
n
[y] := [x ·y]
The ring Z
n
is the set
Z
n
together with the operations +
n
and ·
n
.
It is important to appreciate that +
n
and ·
n
are new operations, defining addition/multiplication of
equivalance classes in terms of standard addition/multiplication of integers.
Example 7.26. We work in the ring Z
8
. According to the definition,
[3] +
8
[6] = [3 + 6] = [9] = [1]
There is a potential difficulty: each equivalence class is large (e.g., [3] = {. . . , 5, 3, 11, 19, . . .}), so we
have lots of choice regarding representatives. For instance, since [3] = [11] and [6] = [22] we should
be able to observe that
[11] +
8
[22] = [3] +
8
[6]
Is this true? If not, then the operation +
8
would not be particularly useful. Thankfully this is not a
problem: according to the definition of +
8
, things turn out exactly as we’d like,
[11] +
8
[22] = [11 + 22] = [33] = [1] = [3] +
8
[6]
105
Consider things more abstractly. Given equivalence classes X and Y, here is the process for comput-
ing the equivalence class X +
n
Y:
1. Choose representatives x X and y Y so that X = [x] and Y = [y].
2. Sum the integers x and y to get a new integer x + y Z.
3. Take the equivalence class X +
n
Y = [x + y].
The concern is that there are infinitely many possible choices for elements x X and y Y in step 1. If
+
n
is to make sense, we must obtain the same equivalence class [x + y] regardless of our choices of x
and y. This indeed happens, as we indicate with a special piece of terminology.
Theorem 7.27. The operations +
n
and ·
n
are well-defined.
This is nothing more than a rehash of Theorem 3.9: compare it with what follows until you are
comfortable we are doing the same thing! Observe that
[x] =
z Z : z x (mod n)
=
x + kn : k Z
Otherwise said, all representatives (all possible choices in step 1) of the equivalence class [x] have the
form x + kn for some k Z. Thinking similarly for y, the Theorem requires only that we prove
k, l Z, [x + kn] +
n
[y + ln] = [x] +
n
[y] and [x + kn] ·
n
[y + ln] = [x] ·
n
[y]
Proof. We prove that +
n
is well-defined.
[x + kn] +
n
[y + ln] = [(x + kn) + (y + ln)] (definition of +
n
)
= [x + y + (k + l)n] = [x + y] (Lemma 7.24)
= [x] +
n
[y] (definition of +
n
)
The argument for ·
n
is similar.
Compare our equivalence class notation with that from Section 3.1. For instance
[3] +
8
[12] = [1] means the same thing as 3 + 12 1 (mod 8) ()
Aside: Advanced Notation Given the applicability of Z
n
, it is customary in higher-level mathe-
matics to drop the square brackets and all subscripts, simply writing
Z
n
=
0, 1, 2, . . . , n 1
In this language, () would simply be written 3 + 12 = 1 in Z
8
. It is critical to appreciate here that
3, 12 and 1 denote sets (equivalence classes), not integers. Until you are 100% certain of this, you
should stick to either of the notations in ().
It is something of a mathematical joke to write 1 + 1 = 0 (in Z
2
). Even in this context, 1 + 1 still
equals 2; the issue is that 2 = 0 in Z
2
, hence the seemingly paradoxical statement. This is really a
very simple claim about sets: that the sum of any two odd numbers is even!
106
Functions and Partitions Our construction of Z
n
is a special case of a more general situation.
50
Definition 7.28. Let be an equivalence relation on a set X and let A be any set. Suppose we
construct f :
X
A using a rule of the form
f ([x]) := “do something to a representative x
We say that f is well-defined if this construction defines a legitimate function. More formally:
[x] = [y] = f ([x]) = f ([y])
Examples 7.29. 1. Consider Z
3
=
Z
, that is X = Z where x y x y (mod 3). The rule
f ([x]) = 2x + 1 does not produce a well-defined function f : Z
3
Z since, for instance
[0] = [9] but f ([0]) = 1 = 19 = f ([9])
2. The rule f ([x]) = [2x + 1] does produce a well-defined function f : Z
3
Z
3
however:
[x] = [y] = y = x + 3k for some integer k
= f ([y]) = f ([x + 3k]) = [2x + 6k + 1] = [2x + 1] = f ([x])
since 6x 0(mod 3). If this seems abstract, note that f is easily
stated in tabular form since there are only three possible inputs!
[x]
[0] [1] [2]
f ([x]) [1] [0] [2]
3. This last example is something of an advert for the advanced notation in the previous aside.
We ask for which integers k the rule f
k
(x) = kx produces a well-defined function f
k
: Z
4
Z
6
.
If this is confusing, re-rewrite using either of the notations
f
k
(x) = kx (mod 6) or f
k
([x]
4
) = [kx]
6
Start with a special case to get a feel for things. A table
of values for f
1
(x) shows an immediate problem!
x 0 1 2 3 4 5 6 ···
f
1
(x) 0 1 2 3 4 5 0 ···
In Z
4
, we have 0 = 4, however f
1
(0) = 0 and f
1
(4) = 4 which are not equal in Z
6
! It follows that
f
1
is not well-defined: it isn’t a function (and never was!).
Now proceed systematically.
x y (mod 4) = x y = 4n = kx ky = 4kn (for some n Z)
It follows that f
k
is well-defined ( f
k
(x) = f
k
( y) Z
6
) if and only if 6 | 4kn for all n Z. This is
the case if and only if 6 | 4k. Otherwise said,
f
k
is well-defined 6 | 4k 3 | 2k 3 | k
Since kx Z
6
, equivalent values of k modulo 6 won’t
change f
k
: there are only two well-defined functions
f
0
(x) = 0 and f
3
(x) = 3x.
x 0 1 2 3 4 5 6 ···
f
0
(x) 0 0 0 0 0 0 0 ···
f
3
(x) 0 3 0 3 0 3 0 ···
You’ll have much more practice with problems like these when you study group theory.
50
Theorem 7.27 verifies the well-definition of two functions +
n
, ·
n
:
Z
n
×
Z
n
Z
n
107
Just for Fun: Geometric Applications (optional!)
We consider how equivalence relations permit the easy construction of certain geometric objects and
of functions on such.
Examples 7.30. 1. Define an equivalence relation on R
2
by
(a, b) (c, d) a c Z and b = d
The equivalence classes are horizontal strings of points with the same y co-ordinate:
[(a, b)] =
(a + n, b) : n Z
The set of equivalence classes
R
2
may be visu-
alized as a cylinder by imagining rolling the plane
into a tube of circumference 1 so that all points in
a given equivalence class coincide.
51
Now consider the rule f ([(x, y])) = y sin(2πx).
wrap
around
x
y
0
1
[(x, y)] = [(v, w)] = y = w and x = v + n, for some n Z
= f
[(x, y)]
= y sin(2πx) = w sin(2πv) = f
[(v, w)]
Otherwise said, f :
R
2
R is a well-defined function whose domain is the cylinder. More
generally, and F : R
2
R for which (x, y) (v, w) = F(x, y) = F(v, w) may be viewed as a
function on the cylinder.
2. As a natural extension, see if you can visualize why the equivalence classes of the relation
(a, b) (c, d) a c Z and b d Z
on R
2
may be identified with a torus (the surface of a ring-doughnut). The function
f
[x, y]
= sin(2πx) cos(2πy)
is well-defined and may thought of as having domain the torus. The pictures below illustrate
f , where the colors correspond.
0
1
0 1
1.0
0.5
0.0
+0.5
+1.0
f
[(x, y)]
= sin(2πx) cos(2πy)
1
2
1
2
x
y
51
Alternatively, imagine piercing a roll of toilet paper and unrolling it: the single puncture becomes a row of (almost!)
equally spaced holes. Unfortunately for the analogy, toilet paper has purposeful thickness!
108
Equivalence relations and partitions are regularly used in this manner to describe objects in geometry
and topology. Here is a final famous example written using the language of partitions.
Example 7.31 (M¨obius Strip). Partition the a rectangle X as follows:
If P X does not lie on the left or right edges, place it in a subset {P} by itself.
Otherwise, pair Q with a point on the other edge identified in the opposite direction
Q,
ˆ
Q
.
These subsets clearly partition the rectangle X and thus describe an equivalence relation on X. The
quotient set
X
may be visualized via the classic construction of a M
¨
obius strip: give the rectangle
a half-twist and glue the two edges so that both points in each equivalance class coincide. This
construction allows us to analyse the strip while working on the rectangle: if you walk off the right
side of the rectangle (at
ˆ
Q) you simply end up at the corresponding point (Q) on the left side!
P
Q
ˆ
Q
Rectangle Half-twist and glue
Exercises 7.4. A reading quiz and practice questions can be found online.
1. Let X be the set of students in a (large) math class and define an equivalence relation on X via
x y x, y either both wear glasses, or both do not wear glasses
Does the rule f ([x]) = x’s name” describe a well-defined function? Explain.
2. (a) Explicitly check that [7] + [ 21] = [98] + [5] in Z
13
.
(b) Suppose that [5] · [7] = [8] · [9] makes sense in the ring Z
n
. Find n.
3. Prove the second half of Theorem 7.27, that ·
n
is well-defined.
4. Suppose that p is prime and that in Z
p
, we have [a] = [0]. Show [a]
2
= [0].
(Hint: Recall Exercise 3.2.13)
5. Give an explicit proof of Theorem 7.23.
6. Determine whether the following are well-defined.
(a) f : Z
3
Z
5
: [x]
3
7 [x
3
]
5
(b) g : Z
10
Z
20
: [x]
10
7 [x
2
]
20
(c) h : Z
8
Z
16
where h(x) = 2x (equivalently h(x) = 2x (mod 16), or h([x]
8
) = [2x]
16
).
(d) j : Z
8
Z
12
where j(x) = 2x.
7. (a) Suppose n Z, (x + 4n)
2
x
2
(mod m). Find all integers m 2 for which this is true.
(b) For what m N
2
is the function f : Z
4
Z
m
: x 7 x
2
(mod m) well-defined.
8. In the sense of Example 7.30, can we view F(x, y) = ( y
2
1) sin
2
( πx) as a function whose
domain is the cylinder? Explain.
109
9. (a) Suppose f :
X
A is well-defined. State what it means for f to be injective. What do
you notice?
(b) Prove that f : Z
7
Z
35
: [x]
7
7 [15x]
35
is a well-defined, injective function.
(c) Repeat part (b) for g : Z
100
Z
300
: [x]
100
7 [9x]
300
.
(Hint: You may find it useful that 9 · (11) 1 (mod 100))
10. Define a partition of the sphere S
2
=
(x, y, z) : x
2
+ y
2
+ z
2
= 1
into subsets consisting of
pairs of antipodal points:
(x, y, z), (x, y, z)
Let be the equivalence relation whose equivalence classes are the above subsets.
(a) f :
S
2
R : [(x, y, z)] 7 xyz is not well-defined. Explain why.
(b) Prove that f :
S
2
R
3
: [(x, y, z)] (yz, xz, xy) is a well-defined function.
The image of this function is Steiners Roman Surface; look it up!
11. Consider the relation (a, b) (c, d) ad = bc on Z × N.
(a) Prove that is an equivalence relation.
(b) List several elements of the equivalence class [(2, 3)]. Repeat for [(3, 7)]. What does
have to do with the set of rational numbers Q?
(c) Define operations + and × on
Z ×N
by
[(a, b)] + [(c, d)] = [(ad + bc, bd)] [(a, b)] ×[(c, d)] = [(ac, bd)]
Prove that + and × are well-defined (do this without using division!).
(d) (Hard) Prove that f
[(x, y)]
=
x
y
is a well-defined bijection f :
Z ×N
Q, and that f
transforms + and × into the usual addition and multiplication on Q: that is,
f
[(a, b)] + [(c, d)]
= f
[(a, b)]
+ f
[(c, d)]
, etc.
(This is essentially a formal definition of the ring of rational numbers!)
12. Define on R by x y if and only if x y Z.
(a) Show is an equivalence relation on R.
(b) Find an example of a surjective function F : R [0, 1) such that x y = F(x) = F(y).
(c) Use part (b) to find a well-defined function f :
R
[0, 1).
13. Suppose is an equivalence relation on X and let γ(x) = [x]. Prove the following:
(a) If f :
X
A is well-defined, then F = f γ : X A satisfies x y = F(x) = F( y).
(b) If F : X A satisfies x y = F(x) = F(y), then there is a unique function f :
X
A
satisfying F = f γ.
14. (Just for fun!) Prove that you can cut a M
¨
obius strip round the middle yet
still end up with a single loop.
Look up the description of a Klein bottle: how is the relationship between
it and the M
¨
obius strip similar to the torus/cylinder relationship?
110
8 Cardinality and Infinite Sets
During the late 1800’s, Georg Cantor assaulted the foundations of mathematics by introducing cer-
tain infinite sets, in particular his middle-third set (Example 6.18). Cantor ideas about infinity met
significant resistance: some mathematicians and philosophers felt his approach to be unnatural; he
even inflamed religious scholars who considered his investigations an affront to the divine!
Despite initial antipathy, Cantor’s notion of cardinality is now universally accepted. By unearthing
several contradictions inherent in contemporary (na
¨
ıve) set theory, mathematicians became con-
vinced that a rigorous axiomatic approach was necessary. Developing an axiomatic foundation to
mathematics became a core goal of early 20
th
century mathematics.
8.1 Cantors Notion of Cardinality
Recall that the cardinality
|
A
|
of a finite set A is simply the number of elements of A (Definition 4.8).
While “number of elements” is meaningless for infinite sets, cardinality also gives rise to a relation
which can be used to compare sets; this interpretation does extend to infinite sets. . .
Example 8.1. Consider sets
A = {fish, dog} B = {α, β, γ}
While the elements of A and B are completely different, the sets themselves may be compared using
cardinality: we write
|
A
|
|
B
|
to indicate that A has no more elements than B. In Theorem 4.25, we
saw that this mandates the existence of an injective function f : A B. It should be clear that
f (fish) = α, f (dog) = β
defines a suitable function.
Theorem 4.25 tells us how to compare cardinalities of finite sets using functions and without counting
elements. Cantor’s seemingly innocuous idea was to turn this theorem for finite sets into a general
definition of cardinality.
Definition 8.2. The cardinality of a set A is denoted
|
A
|
. We compare cardinalities as follows:
|
A
|
|
B
|
f : A B injective
|
A
|
=
|
B
|
g : A B bijective
|
A
|
<
|
B
|
means
|
A
|
|
B
|
and
|
A
|
=
|
B
|
, that is f : A B injective but g : A B bijective.
Lemma 8.3. On any collection of sets, A B
|
A
|
=
|
B
|
defines an equivalence relation.
Cardinality is an abstract property whereby sets can be compared rather than a value attaching to a
given set.
52
Regardless, it should be clear that cardinality partitions any collection of sets: every set
has a cardinality, and no set has more than one cardinality. It is moreover natural to identify the
cardinalities of finite sets with the cardinal numbers 0, 1, 2, 3, 4, . . .
52
We could use the Lemma to define
|
A
|
:= [A] as the equivalence class of A, though this likely feels confusing!
111
Countably Infinite Sets
To make progress, it is helpful to introduce a symbol for the cardinality of the simplest infinite set.
Definition 8.4. We say that A is a countably infinite
53
set and write
|
A
|
=
0
(read aleph-nought or
aleph-null), if its cardinality equals that of the set of natural numbers N:
|
A
|
=
0
g : N A bijective
In the next section we’ll see why a new symbol is needed; why doesn’t suffice.
Examples 8.5. 1. The function g : N N
2
defined by g(n) = n + 1 is a bijection, whence
N
2
= {2, 3, 4, 5, . . .} is countably infinite.
54
2. Let 2N = {2, 4, 6, 8, 10, . . .} be the set of positive even integers. The function
h : N 2N : n 7→ 2n
is a bijection. It follows that
|
2N
|
=
|
N
|
=
0
and that 2N is countably infinite.
Theses examples demonstrate a perplexing property of infinite sets. For instance, 2N is a proper subset
in bijective correspondence with N! It feels like we want to say two contradictory things:
N has the ‘same number of elements’ as 2N (bijectivity of h).
N has ‘twice the number of elements’ as 2N (‘half of N is even, and ‘half odd).
The source of our discomfort is that number of elements is meaningless for infinite sets. However, if we
replace this phrase with cardinality, then both statements are true!
55
The existence of a proper subset
with the same cardinality can indeed be used as a definition of infinite set (Exercise 13).
Rather than hunting for an explicit bijection, the simplest approach to these problems is often to list
the elements of a set A so that it ‘looks like’ the natural numbers, with an initial element a
1
followed
by all others in sequence:
A = {a
1
, a
2
, a
3
, a
4
, . . .} indicates a bijection g : N A : n 7 a
n
, whence
|
A
|
=
0
For instance, we could have approached our examples by listing elements in tabular form:
N n 1 2 3 4 5 6 7 8 9 10 ···
N
2
g(n) 2 3 4 5 6 7 8 9 10 11 ···
2N h(n) 2 4 6 8 10 12 14 16 18 20 ···
The required bijections are immediately visible with little need to state them explicitly. We apply this
technique to two important examples of countably infinite sets.
53
Some authors say denumerable and use countable for sets with
|
A
|
0
. Aleph is the first letter of the Hebrew alphabet.
54
This is a version of Hilbert’s Grand Hotel Problem. Imagine a hotel with an infinite number of rooms: Room 1, Room 2,
Room 3, Room 4, etc. Even if the hotel is full, by moving everyone one room down the hall, space can always be found for
an additional guest. The second example is another version, where infinitely many new guests must be accommodated.
55
We won’t pursue cardinal arithmetic in any detail, but it is completely legitimate to write 2
0
=
0
for the second
example. The first example would be 1 +
0
=
0
.
112
List the set of integers in a non-standard order, alternating positive and negative terms:
Z = {z
1
, z
2
, z
3
, z
4
, . . .} = {0, 1, 1, 2, 2, 3, 3, 4, 4, . . .}
The function g : N Z : n 7 z
n
is bijective, so we conclude:
Theorem 8.6. The integers Z are a countably infinite set.
You might feel that our argument was too quick! Is it really obvious what g is? Bijectivity is the
observation that every integer appears exactly once in our non-standard ordering. If you really want,
you can construct an explicit formula for g from a tabular representation
n 1 2 3 4 5 6 7 8 9 ···
g(n) 0 1 1 2 2 3 3 4 4 ···
= g(n) =
(
1
2
n if n even
1
2
( n 1) if n odd
and prove bijectivity using the formula. In practice, it is not worth the cost to be this explicit.
As you build up examples, you no longer have to compare directly to the natural numbers. Since
composition of bijective functions is bijective (Theorem 4.22/transitivity in Lemma 8.3),
B is countably infinite A countably infinite and g : A B bijective
For instance, the set of even integers 2Z is denumerable via the bijection g : Z 2Z : z 7→ 2z.
We use this approach to help prove the first of Cantor’s truly counter-intuitive revelations.
Theorem 8.7. The rational numbers Q are countably infinite.
Any sensible person should feel that there are far, far more rational numbers than integers, yet the
sets have the same cardinality. Bizarre!
Proof. For each pair of natural numbers a, b, place the fraction
a
b
in the b
th
row, a
th
column of an
infinite square. List the positive rational numbers by tracing diagonals in a snake-like manner and
deleting any number that has already been traced (
2
2
=
1
1
,
6
4
=
3
2
, etc.).
Since
a
b
each appears in diagonal a + b 1 and repeats are
deleted, every positive rational number appears exactly once.
We therefore obtain an enumeration
Q
+
=
1
1
,
2
1
,
1
2
,
1
3
,
3
1
,
4
1
,
3
2
,
2
3
,
1
4
,
1
5
, . . .
and conclude that Q
+
is countably infinite. Plainly this
corresponds to a bijection g : N Q
+
. To finish the proof,
extend g by defining the bijective function
h : Z Q : n 7→
g(n) if n > 0
0 if n = 0
g(n) if n < 0
1
1
.
.
.
2
1
.
.
.
3
1
.
.
.
4
1
.
.
.
5
1
.
.
.
6
1
.
.
.
7
1
.
.
.
···
1
2
2
2
3
2
4
2
5
2
6
2
7
2
···
1
3
2
3
3
3
4
3
5
3
6
3
7
3
···
1
4
2
4
3
4
4
4
5
4
6
4
7
4
···
1
5
2
5
3
5
4
5
5
5
6
5
7
5
···
1
6
2
6
3
6
4
6
5
6
6
6
7
6
···
.
.
.
which identifies the negative rationals with Z
. By Theorem 8.6, we deduce that
|
Q
|
=
|
Z
|
=
0
.
113
Other countably infinite sets appear to be even larger than Q! For example:
Cartesian products such as N × N.
The algebraic numbers A =
x C : p(x) = 0 for some polynomial p with integer coefficients
.
Every rational number is algebraic (
a
b
is a root of p(x) = bx a), but so are many irrationals
(
2 is a root of p( x) = x
2
2). Non-algebraic numbers (e.g., π and e) are termed transcendental.
Arguments for these examples are left to the exercises.
The Least Infinite Cardinal?
We introduced
0
to represent the cardinality of the ‘simplest’ infinite set N. Here is a compelling
reason why the natural numbers should indeed be considered the most simple infinite set.
Theorem 8.8. A is finite if and only if
|
A
|
<
0
.
Otherwise said, every infinite set has cardinality at least as large as the natural numbers:
0
may
therefore be considered the least infinite cardinal.
Proof. () Express the set in roster notation A = {a
1
, . . . , a
n
}. We must prove two things:
56
(
|
A
|
0
) Define f : A N by f (a
k
) = k for each k {1, 2, 3, . . . , n}. This is injective since
the distinct elements a
k
of A map to distinct integers.
(
|
A
|
=
0
) We show there are no bijections N A. Suppose g : N A and consider the set
g
{1, . . . , n + 1}
=
g(1), . . . , g(n + 1)
A
Since A has n elements, at least two of the values g(1), . . . , g(n + 1) must be equal. There-
fore g is not injective and consequently not bijective.
() See Exercise 11.
We’ll address the existence of infinite sets with cardinality larger than
0
in the next section.
Exercises 8.1. A reading quiz and practice question can be found online.
1. Refresh your proof skills by proving explicitly that the following functions are bijections:
(a) g : N N
2
: n 7 n + 1 (b) h : N 2N : n 7 2n
2. Prove that Z
≥−3
is countably infinite by constructing a bijective function g : N Z
≥−3
.
3. Prove that the set 3Z + 2 = {3n + 2 : n Z} is countably infinite.
4. Show that the set of all triples of the form (n
2
, 5, n + 2) with n 3Z is countably infinite by
providing an explicit bijection with a known countably infinite set.
5. State a bijection g : (0, 1) (4, 6) which shows that these intervals have the same cardinality.
56
The n = 0 case (A = ) works, though it feels strange: f = is a suitable injective (!) function f : N, and there
are no functions g N . It will help to think about the formal definition of function (Section 7.2)!
114
6. Prove Lemma 8.3 (revisit Theorem 4.22 on the composition of bijective functions.)
7. Prove that A B =
|
A
|
|
B
|
(show there exists an injective function f : A B).
8. (a) Prove that N ×N is countably infinite by modifying the proof of Theorem 8.7.
(b) Combine part (a) with Theorem 8.7 to prove that Q ×Q is countably infinite.
(c) Suppose A
n
is countably infinite for each n N and list elements as follows:
A
1
= {a
11
, a
12
, a
13
, a
14
, . . .}
A
2
= {a
21
, a
22
, a
23
, a
24
, . . .}
A
3
= {a
31
, a
32
, a
33
, a
34
, . . .}, etc.
Prove that
S
A
n
is countably infinite (a countable union of countable sets is countable).
Warning! The remaining exercises are significantly trickier.
9. Suppose A = . Prove that
|
A
|
|
B
|
if and only if there exists a surjective function g : B A.
(Hint: Use g to construct an injective f : A B, and vice versa)
10. Let A =
x C : p(x) = 0 for some polynomial p with integer coefficients
be the set of
algebraic numbers. We prove that A is countably infinite.
(a) Let M N. Prove that there are only finitely many choices of d N and a
0
, . . . , a
d
Z
such that M = d +
|
a
0
|
+ ···+
|
a
d
|
.
(b) Let P
M
=
a
d
x
d
+ ···+ a
1
x + a
0
: d +
|
a
0
|
+ ···+
|
a
d
|
= M
. Explain why P
M
is finite.
(c) Show that R
M
=
x C : p(x) = 0 for some p P
M
is finite by using the fact that a
degree d polynomial has at most d roots.
(d) Prove that A =
S
MN
R
M
and conclude that A is countably infinite.
11. We complete the proof of Theorem 8.8: if
|
A
|
<
0
, then A is a finite set.
We prove by contradiction. Suppose A is infinite and that
|
A
|
<
0
. Then there exists an
injective function f : A N. List the range of f in increasing order:
range( f ) = {n
1
, n
2
, n
3
, . . .} n
1
< n
2
< n
3
< ···
(a) Show that for all k N, there exists a unique a
k
A satisfying f (a
k
) = n
k
.
(b) Define g : N A by g(k) = a
k
. Prove that g is a bijection and hence obtain a contradiction.
12. Suppose C is countably infinite and let c C.
(a) Show that there exists a bijection h : N C with h(1) = c.
(b) Prove that D = C \{c} is countably infinite.
(Hint: h be as in part (a) and use g from Example 8.5 to construct k : N D)
13. (a) Suppose
|
A
|
0
. Show that there exists C A for which
|
C
|
=
0
.
(b) Prove that a set A is infinite if and only if it has a proper subset B with
|
B
|
=
|
A
|
.
(Hint: use part (a) and Exercise 12)
14. Describe an explicit bijection g : [0, 1] (0, 1), and thus demonstrate that the intervals have the
same cardinality.
(Hint: {
1
n
: n N
2
} is a countably infinite subset of (0, 1))
115
8.2 Uncountable Sets
Since Q seems so large, you might think that there couldn’t be sets with strictly larger cardinality.
But we haven’t yet thought about the real numbers. . .
Definition 8.9. A set A is uncountable if
0
<
|
A
|
. Otherwise said, there exists an injection f : N A
but no bijection g : N A.
Theorem 8.10. The interval (0, 1) of real numbers is uncountable.
We denote the cardinality of the interval (0, 1) by c for continuum. The theorem may therefore be
written
0
< c. We prove by showing that
0
c and
0
= c.
Proof. (
0
c) The function f : N (0, 1) : n 7→
1
n+1
is plainly injective:
f (n) = f (m) =
1
n + 1
=
1
m + 1
= n = m
(
0
= c) Suppose, for contradiction, that g : N (0, 1) is a bijection. Express the sequence of values
g(1), g(2), g(3), . . . as decimals:
57
g(1) = 0.b
11
b
12
b
13
b
14
b
15
b
16
···
g(2) = 0.b
21
b
22
b
23
b
24
b
25
b
26
···
g(3) = 0.b
31
b
32
b
33
b
34
b
35
b
36
···
g(4) = 0.b
41
b
42
b
43
b
44
b
45
b
46
···
g(5) = 0.b
51
b
52
b
53
b
54
b
55
b
56
···
.
.
.
where each b
ij
{0, . . . , 9}
Define a new decimal
x := 0.x
1
x
2
x
3
x
4
x
5
··· (0, 1) where x
n
=
(
1 if b
nn
= 1
2 if b
nn
= 1
Since x disagrees with g(n) at the n
th
decimal place, we see that x = g(n): that is, x is not in the
above list. However x (0, 1) and g is surjective, so x must be in the list: contradiction.
The second part of the proof is known as Cantors diagonal argument, since we compare the constructed
decimal x with the diagonal of an infinite square of integers. Since the interval (0, 1) is uncountable,
and (0, 1) R, it is immediate that the real numbers are also uncountable. Using only the ideas
developed so far (a combination of Exercises 8.1.5 and 14), we could prove directly that every interval
of finite length has cardinality c. It is easier, however, to delay this momentarily. . .
More amazingly, Cantor’s middle-third set (Example 6.18) also has cardinality c, despite seeming
vanishingly small! The details, and more, are in Exercise 12.
57
A number x (0, 1) has two decimal representations if and only if one of them terminates and the other ultimately
becomes an infinite sequence of 9’s: e.g., 0.135 = 0.1349999 ···. For the purposes of this proof, choose the terminating
decimal when it exists. We restrict to x
n
= 1, 2 later in the proof to keep away from these double representations.
116
Non-explict Comparison of Cardinalities
The following result is very useful for comparing cardinalities.
Theorem 8.11 (Cantor–Schr¨oder–Bernstein). If
|
A
|
|
B
|
and
|
B
|
|
A
|
, then
|
A
|
=
|
B
|
.
This seems like it should be obvious, but pause for a moment: it is not a result about numbers! The
theorem should be understood in the context of Definition 8.2, in which language it becomes:
If there exist injections f : A B and g : B A, then there exists a bijection h : A B
The proof is beautiful, though a little long to reproduce here; check out any elementary text on set the-
ory if you’re interested. Its usefulness is that it allows us to equate cardinalities without the explicit
construction of bijective functions; injective functions are typically much easier to conjure!
Example 8.12. Observe that the following functions are both injective (only—not bijective!):
f : (0, 1) [0, 1] : x 7 x (range( f ) = (0, 1) [0, 1])
g : [0, 1] (0, 1) : x 7
1
2
x +
1
4
(range(g) = [
1
4
,
3
4
] (0, 1))
By Cantor–Schr
¨
oder–Bernstein, the sets (0, 1) and [0, 1] have the same cardinality (c). Note how fast
this was; we didn’t have to construct an explicit bijection h : (0, 1) [0, 1], a much harder business
(see Exercise 8.1.14)
As advertised a few moments ago, the Example generalizes to cover all intervals.
Corollary 8.13. All intervals (of positive length) have cardinality c.
Proof. Let A be an interval (could be infinite length) and choose a subinterval (a, b) A. The follow-
ing functions are injective:
f : (0, 1) A where f (x) = a + (b a)x; this maps
(0, 1) onto range( f ) = (a, b) A.
ι : A R where ι(x) = x.
g : R (0, 1) where g(x) =
1
2
+
1
π
tan
1
x; this is in
fact bijective with inverse g
1
( y) = tan
πy
π
2
.
1
2 1 0 1 2
y = g(x) bijective
Putting everything together:
|
(0, 1)
|
f
|
A
|
ι
|
R
|
g
=
|
(0, 1)
|
By Cantor–Schr
¨
oder–Bernstein, all these sets have the same cardinality c.
Further examples can be found in the exercises.
117
Cantors Paradoxical Theorem
For a final punchline, we generalize Theorem 6.8 which, for finite sets A, asserted that
|
P(A)
|
= 2
|
A
|
is strictly larger than A itself. We now have the technology to attack this for infinite sets.
Theorem 8.14 (Cantor). If A is any set, then
|
A
|
|
P(A)
|
.
The main implication is that there is no largest cardinality! We can always construct a larger cardinality
set by taking the power set. For example,
|
P(R)
|
>
|
R
|
= c. Want a set with even larger cardinality?
Try P
P(R)
, or P
P(P(R))
! We can continue this process indefinitely.
Proof. If A = , the result is trivial. Otherwise, first observe that f : a 7 {a} defines an injective
function f : A P(A), whence
|
A
|
|
P(A)
|
.
To complete the argument we must show that no bijective function g : A P(A) can exist. Suppose,
for a contradiction, that g : A P(A) is bijective, and consider the set
X =
a A : a / g(a)
Tack stock for a moment, since X is hard to think about. Since g(a) is a subset of A, the condition
a ∈ g(a) is legitimate, whence X is a genuine subset of A. A simple example will hopefully help.
Example 8.15. Let A = {1, 2, 3} and define a function g : A P(A) by
g(1) = {1, 2}, g(2) = {1, 3}, g(3) =
Since 1 g(1), 2 / g(2), and 3 / g(3), we see that X = {2, 3}. Since our goal is to prove that
no bijection A P(A) can exist, it is important to note that this function g is not bijective; indeed
X / range(g) =
{1, 2}, {1, 3},
shows that this g is not surjective.
Proof Continued. By assumption, g is surjective. Since range(g) = P(A), the set X lies in range(g).
Otherwise said, X = g(a) for some a A. We ask whether a is an element of X:
a X a / g(a) (definition of X)
a / X (since X = g(a))
Look at what we have concluded: a X a / X is plainly a contradiction! We conclude that no
bijection g : A P(A) exists, and so
|
A
|
|
P(A)
|
.
Cantor’s theorem played a role in pushing set theory towards axiomatization, in part because of the
following paradox. If a ‘set’ is merely a collection of objects, we may consider the ‘set of all sets’ S. Its
power set P(S) is a set of sets, so must be a subset of S, whence
|
P(S)
|
|
S
|
. However, by Cantor’s
theorem,
|
S
|
|
P(S) )
|
, resulting in the manifest absurdity
|
S
|
|
S
|
!
The remedy is a rigorous definition of ‘set.’ Axiomatic set theory describes a small number of legitimate
ways to build sets, of which we’ve seen several in these notes: e.g., union, power set, set-builder
notation. In particular, the ‘set of all sets’ cannot be legitimately constructed.
58
58
The critical condition for preventing Cantor’s paradox is that set-builder notation {x A : P(x)} can only produce a
subset of an already existing set A. The ‘set of all sets’ would have the form {x : P(x)} where x is unrestricted.
118
Some Final Thoughts on the Limits of Proof
Throughout this course we’ve learned about some of the basic methods and concepts used by math-
ematicians. In particular, we’ve learned how to use proofs to demonstrate the truth of statements
about mathematical objects. As we finish, it makes sense to reflect on the limits of our methods.
By the early 20
th
century, the discovery of various paradoxes and contradictions (like Cantor’s) led
to a foundational crisis in mathematics. If a concept as basic as set is contradictory, how can we
have faith in any mathematical conclusion?! The result of this crisis was an effort to place all of
mathematics on a rigorous axiomatic basis by formulating a list of reasonable axioms from which all
of mathematics could be derived using basic logical reasoning. Such an axiomatic foundation ideally
would satisfy two conditions:
Consistency: No contradiction could be derived from the axioms.
Completeness: All true mathematical statements could be derived from the axioms.
All hope for such a foundation was crushed in 1931, when Kurt G
¨
odel published his famous In-
completeness Theorems which showed that no such axiomatic system could exist. Essentially, G
¨
odel
showed that any consistent axiomatic system strong enough to produce some basic arithmetic, there
are undecideable statements; neither derivable nor refutable from the axioms. Perhaps even worse, no
such system can prove its own consistency.
While the strongest aims of early 20
th
axiomatics cannot be accomplished, contemporary research
was able to provide a foundation that most modern mathematicians deem adequate for current
work. Perhaps the most popular approach is to base all of mathematics on set theory—as your stud-
ies progress, you’ll see that many of the objects you study can be formalized as sets together with
functions and relations between sets. We’ve started this work already: Chapter 7 says that func-
tions and relations are themselves sets! Numbers like 0, 1, 2,
12
19
or even π = 3.14 . . . can be thought
of as sets if one desires. In turn, set theory is often axiomatized using the ZFC axioms (short for
Zermelo–Fraenkel set theory with the Axiom of Choice).
While ZFC is subject to the limitations imposed by G
¨
odel’s theorems,
59
they have proven able to
formalize most of the mathematics actually used by current mathematicians, and have not (thus
far!) produced any inconsistencies. While there is plenty of fun to be had exploring set theory,most
modern mathematicians feel little need to dwell on the foundational issues of last century!
Exercises 8.2. A reading quiz and practice question can be found online.
1. Decide the cardinality of each set. No working is necessary.
(a) N
12
(b) Z
12
(c) ( 0, 5] (d) [2, π] Q (e) P
{R}
(f)
T
xR
+
[3
1
x
, 3 +
1
x
)
2. Find explicit bijections (thus showing that the given intervals have the same cardinality):
(a) f : [2, 3) [1, 5) (b) g : [2, 3) (1, 5] (c) h : (3, 2) R (d) j : R (1, )
(Hint: The proof of Corollary 8.13 should provide some inspiration—be creative)
3. Let B = [3, 5) (6, 10). Use the Cantor–Schr
¨
oder–Bernstein Theorem to prove that
|
B
|
= c.
(Hint: State injective functions f : (0, 1) B and g : B (0, 1))
59
Perhaps the most famous undecidable statement in ZFC is relevant to our recent discussion: the continuum hypothesis is
the claim that no set has cardinality strictly between
0
and c; that intervals are the simplest (‘smallest’) uncountable sets.
119
4. (a) Prove that f : N ×N N defined by f (m, n) = 2
m
3
n
is injective.
(b) Use part (a) and the Cantor–Schr
¨
oder–Bernstein Theorem to conclude that
|
N ×N
|
=
0
.
(c) Extend your argument to prove that, for any natural number k, |N × ···×N
| {z }
k times
| =
0
(d) Use part (b) to give an alternative proof that
|
Q
+
|
=
0
.
5. Revisit the proof of Cantor’s Theorem, and Example 8.15.
(a) Suppose g : {1, 2, 3, 4} P({1, 2, 3, 4}) is defined by
g(1) = {2, 3}, g(2) = {1, 2}, g(3) = , g(4) = {1, 2, 4}
Compute the set X =
a {1, 2, 3, 4} : a g(a)
.
(b) Repeat part (a) for g : N P(N) : n 7 {x 2N : x n}.
(Hint: Try some examples first! What is g(1)? Is 1 g(1)? What about 2 g(2)?)
6. Let I = R \Q be the set of irrational numbers.
(a) Prove that
|
I
|
c.
(b) Prove that x N = x +
2 I. Hence conclude that
0
|
I
|
.
(c) Argue that the irrational numbers are uncountable (
|
I
|
= c is harder to show).
(d) Show that the transcendental (non-algebraic) numbers are uncountable (see Exercise 8.1.10).
7. Give an example of an uncountable set I and an indexed collection {A
n
: n I} for which all
the following conditions hold:
Each A
n
is countably infinite.
If m = n, then A
m
= A
n
.
For all m, n, either A
m
A
n
or A
m
A
n
.
S
nI
A
n
is countably infinite.
8. The proof of Cantor’s Theorem makes use of a construction similar to Russell’s paradox. Let X
be the ‘set’ of all sets which are not members of themselves:
X = {A : A A}
(a) Suppose X is a set. By asking yourself if X is a member of itself, deduce a contradiction.
(The point of Russell’s paradox is that objects like X cannot be considered sets!)
(b) Russell’s paradox is one version of an ancient logical conundrum with many guises. E.g.,
A town has one barber, who cuts the hair of all townspeople, and only those
people, who do not cut their own hair: Who cuts the barber’s hair?
Can you explain the connection between this and Russell’s paradox?
9. In Exercise 6.3.14, we saw that Cantor’s middle-third set C is the set of all numbers in [0, 1] pos-
sessing a ternary expansion consisting only of 0’s and 2’s. By modifying the proof of Theorem
8.10, argue that C is uncountable.
(Exercise 12 establishes the stronger result
|
C
|
= c)
120
The final questions are more of a challenge.
10. Express a real number x (0, 1) as a decimal x = 0.x
1
x
2
x
3
x
4
. . . where we choose the terminat-
ing decimal whenever there is a choice (footnote 57). Prove that
f : (0, 1) ×(0, 1) (0, 1) defined by f (x, y) = 0.x
1
y
1
x
2
y
2
x
3
y
3
. . .
is injective. Hence conclude that
R
2
= c.
11. If A and B are non-empty sets we let A
B
denote the set of all functions f : B A.
(a) If A = {0, 1} and B = {a, b, c}, list all elements of A
B
. What is
A
B
?
(b) If A and B are finite sets, show that
A
B
=
|
A
|
|
B
|
.
(c) Let B be a set and Y B. The characteristic function of Y is χ
Y
: B {0, 1} where
χ
Y
(x) =
(
1 if x Y
0 if x / Y
Prove that Φ : P(B) {0, 1}
B
defined by Φ(Y) = χ
Y
is bijective.
(If B is finite, this provides another proof that
|
P(B)
|
= 2
|
B
|
)
12. Let x [0, 1]. A binary expansion of x is a sequence (b
n
) of zeros and ones such that
x =
n=1
b
n
2
n
The binary expansion of x [0, 1] is (almost) unique;
60
if there is a choice, take the terminating
expansion. Define a function f : [0, 1] P(N) (the set of subsets of N) by
f (x) = {n N : b
n
= 1 in the binary expansion of x}
(a) Prove that f is injective, and that, consequently, c
|
P(N)
|
.
(b) Is f surjective?
(Hint: consider the set X = {2, 3, 4, . . .} P(N ))
(c) Let C be Cantor’s middle-third set. Prove that g : P( N) C is a bijection, where
g(X) =
nX
2
3
n
(d) Use the Cantor–Schr
¨
oder–Bernstein Theorem to conclude that
|
P(N)
|
=
|
C
|
= c.
(Together with Exercise 11, this shows why we could write c = 2
0
)
60
Binary expansions are unique unless x has a terminating expansion, in which case the there is a second involving
an infinite sequence of 1’s: e.g., [0.011111 ···]
2
= [0.1]
2
. This example is beloved of computer scientists who, following
Exercise 11, might view P(N) {0, 1}
N
as the set of binary sequences/strings (x
1
, x
2
, x
3
, . . .), where each x
j
{0, 1}.
121