Introduction to Abstract Mathematics

Conrad Plaut
Contents

Preface ix

1 Logic and Set Theory 1

1.1 Basic Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Basic Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 The Real Numbers 19

2.1 Field Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Order Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Completeness Axiom . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Absolute value . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3 The Integers and Induction 39

3.1 De…nitions of N and Z (Optional) . . . . . . . . . . . . . . . . 40
3.2 Basic Properties of the Integers . . . . . . . . . . . . . . . . . 43
3.3 Applications of Induction . . . . . . . . . . . . . . . . . . . . . 50
3.4 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.5 Prime Factorization . . . . . . . . . . . . . . . . . . . . . . . . 59

4 Additional Topics 65
4.1 One-to-one and onto functions . . . . . . . . . . . . . . . . . . 65
4.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . 70
4.3 Finite Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.4 In…nite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.5 Indexed Collections of Sets (Optional) . . . . . . . . . . . . . 85

v
 Preface
A basic mathematics course such as freshman calculus generally consists of
an orderly list of theorems and applications of theorems, as well as some
intuitive ideas about why those theorems might be true, while o¤ering very
little (if anything) in the way of actual proof. This approach is necessary
for such courses because very few students who take them are destined to
actually do mathematics as opposed to simply using it. Unfortunately, basic
mathematics courses may have a residual e¤ect on students who continue
with higher mathematics courses, if the lesson learned is that the goal of a
mathematics course is to learn theorems. Learning mathematics is not about
learning theorems, it is about learning how to prove theorems. Knowing the
theorems is, of course, vitally important. But if you know how to prove a
theorem then you know more than the statement: you know precisely why the
statement is true. Knowing the proof, you are prepared to try to understand
how the proof might be changed to produce a new theorem. Moreover, within
that proof there are methods that you might use in other proofs, even proofs
of theorems that do not seem to be closely related to the one whose proof
you have just learned.
The transition from learning and applying facts and formulas to actually
understanding mathematics is often not an easy one. Many students begin a
course like this not even knowing what it means to understand mathematics,
and as a result the material can seem bewildering. However, for most stu-
dents, eventually the material “clicks”and suddenly becomes easier to learn.
This process can be hastened by taking the following steps: (1) learn pre-
cisely all de…nitions and theorems prior to the next class (2) Prior to starting
on the homework, work through all proofs learned in class until you are able
to do them yourself, without referring to the notes.
This text owes a debt to William Wade’s monograph Introduction to
Abstract Mathematics for the choice of many topics. Dr. Wade’s book is
a welcome departure from “learn-to-prove-it” texts that focus primarily on
discrete mathematics or real analysis. The goal of the present text is to
present a similar menu of traditional topics in basic algebra, analysis, and
set theory that is organized to more closely follow the axiomatic method. In
particular, the axioms for the real numbers are introduced early and topics
such as induction are derived from the axioms. The resulting topics also have
a stronger algebraic component.

ix
Chapter 1

Logic and Set Theory

In this chapter we will cover the basics of logic and set theory. We would
like to begin by reminding the reader of the axiomatic method on which
mathematics (and through it science) is based. It is impossible to de…ne
all concepts in any logical system, any more than a dictionary can de…ne all
words in a language without relying on some prior linguistic knowledge of the
user (or pictures or other non-lingual aids). After all, what words would one
use to write the “…rst” de…nition? The fact that any mathematical system
must begin with terms such as “set” that must always remain unde…ned is
actually an advantage, not a disadvantage–allowing us to develop an abstract
theory that we can apply to sets of numbers, sets of rabbits, sets of matrices,
or sets of atoms.
Likewise, not all statements in a mathematical system can be proved.
Indeed a proof is only a tool to determine that one statement follows logically
from one or more other given statements; one must start somewhere! The
starting point is a collection of statements involving the unde…ned terms,
called axioms, that are assumed to be true. Given a particular set of axioms,
a whole area of mathematics can be built up by proving statements that
follow logically from those axioms, using these statements to prove more
statements (adding new de…nitions when needed), ad in…nitum. The axioms
themselves are as few and simple and natural as possible, making it as easy
as possible to check whether they are applicable in a given situation. Even
a small number of axioms can give rise to a powerful collection of theorems.
For example, all of the calculus that you have already learned, and much that
you have not yet learned, is deduced from a small handful of axioms. While
from the standpoint of mathematics these axioms are simply assumed, and

1
2 CHAPTER 1 LOGIC AND SET THEORY

cannot be “veri…ed,”their validity in science has been more than adequately

justi…ed by the powerful applications that arise from them.
Statements that are proved in mathematics are traditionally named “lem-
mas”, “propositions”, “theorems” or “corollaries.” While there is no …xed
convention about the use of these names, a lemma is typically a statement
with a relatively simple proof that is primarily used (often frequently) to
prove other, deeper statements. A proposition is of greater importance as a
statement by itself, and a theorem is usually a statement of major depth and
importance. A corollary is always a statement that follows with only a small
amount of proof from a theorem, proposition, or lemma, but may itself be
of great importance. We also refer to lemmas, propositions, theorems, and
corollaries collectively as “theorems”.
There are di¤erent axiom sets with which one may begin, including vari-
ous axioms for set theory. For the purposes of this text we will use the axioms
for the real numbers. That is, we will assume that there exists a set called the
real numbers R with two algebraic operations (addition and multiplication)
that satisfy the properties that you have used since childhood, such as the
associative or distributive laws. We will also assume that R has an ordering
that satis…es certain familiar properties, such as the transitive law: if a < b
and b < c then a < c. Finally, we will add to the mix an axiom that may
not be at all familiar: the Completeness Axiom, which essentially allows one
to properly do calculus. All of these axioms will be carefully stated later.
The existence of a set R satisfying these axioms may actually be proved
using much more basic sets of axioms, such as the Zermelo–Fraenkel axioms
for set theory. Some of these set theory axioms are simple and natural. For
example, the “Axiom of Extensionality” essentially states that two sets are
the same if they have the same elements. Others, however, are bewildering
to the novice. The “Axiom of Regularity”states that every non-empty set x
contains some element y such that x and y do not intersect, which confounds
the naive distinction between sets and elements of sets. The elementary
nature of this text prevents us from wrestling with these foundational topics,
and we will instead simply assume basic properties from set theory, and
assume that there is a set that satis…es the axioms for the real numbers.
Beyond their applicability to science, there is another reason why the ax-
ioms for the real numbers are likely the “right”ones. If one takes a subset of
the axioms for the real numbers, then there are many di¤erent systems that
satisfy them. For example, if one considers only the axioms concerning ad-
dition, without the commutative law, then these axioms describe something
1.1 BASIC LOGIC 3

known in mathematics as a group–which is one of the basic objects studied

in what is known as modern or abstract algebra. Other subsets of the real
number axioms give rise to other general mathematical objects, such as semi-
groups, rings, …elds, totally and partially ordered sets. However, it can be
proved that the real number system is the only number system that satis…es
all of the real number axioms together. To reiterate: the real numbers can be
constructed from very basic assumptions about set theory, they are uniquely
determined by their axioms, and they have powerful applications. They are
certainly worth studying.
We will be particularly interested in certain sets of real numbers. We give
our notation for them now: The natural numbers are N := f1; 2; 3; :::g. The
integers are Z := f:::; 2; 1; 0; 1; 2; :::g and the rational numbers Q consist
of all real numbers equal to a quotient pq , where p and q 6= 0 are integers.
For the time being, in examples and exercises we will use these sets and the
properties of them with which you should be familiar. However, we will not
prove any theorems about them until we have introduced the axioms for the
real numbers. At that point you will have to “forget” everything you have
learned about the real numbers as we begin the process of reconstructing and
proving all of your knowledge using only our axioms. We won’t get very far
in this course, but along the way you will learn many techniques that will
help you in the math classes that you will take in the future.

1.1 Basic Logic

We will informally discuss the basics of logic and set theory. Strictly speaking
we will be using certain axioms from set theory, such as the “Axiom of
Extensionality” mentioned earlier, and axioms that guarantee the existence
of unions and subsets. These particular axioms are so fundamental and “self-
evident”that the beginning student might not even realize that, technically
speaking, they are necessary. Such a “naive”approach to set theory will not
lead to problems so long as we stick to the real numbers, its subsets, sets (or,
as we will often call them, collections) of such subsets, and sets constructed
in very concrete ways from the real numbers. An example of the sort of
troublemaker that we will avoid is Russell’s paradox: “the set R containing
exactly the sets that are not elements of themselves”. Either R contains
itself, or it doesn’t. If R contains itself then its own de…nition is violated.
If R doesn’t contain itself then by de…nition it does contain itself. Either
4 CHAPTER 1 LOGIC AND SET THEORY

way we have a problem. Various axioms for set theory resolve this and other
paradoxes by restricting the ways in which one may de…ne sets–prohibiting
de…nitions like the one de…ning R. However, nothing that we will do in this
text comes close to violating the rules of restriction of set theory.
If A and B represent statements, then the statement “A and B” is true
precisely if A and B are both true. For example, if A is the statement “in
the 20th century a meteor hit the earth”and B is the statement “in the 20th
century millions of people died,”both of which are true, then the statement
“in the 20th century a meteor hit the earth and millions of people died” is
true. (Our tendency to connect these two statements and read a cause-and-
e¤ect relationship into this statement is not logical, and the mathematics
student needs to learn to be very careful to avoid this and other kinds of
illogic.)
Did you notice that we actually used the word “and” to de…ne the word
“and”? We are able to get away with this because you already have some
idea of what the word means. If we wanted to be more careful we could
de…ne “and”using what is known as a “truth table”, which looks something
like this:
B
An T F

T T F
F F F
The table de…nes when statements connected by “and”are true or false.
For example, if A is true and B is false, then “A and B”is seen to be false,
since there is an entry of “F” in the row with a “T” to the left and in the
column with an “F” at the top. Rather than relying on your knowledge of
the word “and”, the truth table relies on the ability to read a chart, which
is pretty hard to explain without using the concept of “and”. So we will
dispense with truth tables (except for a couple of exercises). A student who
tries to rely on truth tables to understand statements will not make it very
far anyway.
The statement “A or B” is true precisely if A, B, or both A and B are
true. For example, the statement “that animal is brown or that animal is a
cow” is true if the animal is a brown cat, a green cow, or a brown cow, but
is false if the animal is a black sheep. The latter example shows how one
negates an “or”statement. The negation of the statement “A or B”is “not
A and not B”(in the previous example, not brown and not a cow). Likewise
1.1 BASIC LOGIC 5

the negation of the statement “A and B”is “not A or not B”.

Logic has two quanti…ers, “for all”and “there exists”. There are of course
logically equivalent grammatical variations of these quanti…ers, such as “for
every” and “for some”, respectively. “For all” means for every one, without
exception, and “there exists” means for at least one (maybe many–or even
all). The negation of a “for all” statement is always a “there exists” state-
ment, and vice versa. For example, the negation of “all of my pencils are
yellow”is “there exists one of my pencils that is not yellow.”(This doesn’t,
of course, exclude two non-yellow pencils!) The negation of “some French
movies are boring”is “all French movies are not boring”. Note that “for all”
is a kind of “super and” while “there exists” is a kind of “super or” in the
following sense. Consider statements A and B. The statement “A and B”
is true precisely if all of the statements in question (A and B) are true. The
statement “A or B” is true precisely if there exists a statement (among A
and B) that is true. While “and”and “or”can connect only two statements,
“for all” and “there exist” have no such restrictions. For example, if we let
P (i) be the statement 1=i 1=2, where i is a natural number, then we could
write “P (2) is true and P (3) is true and P (4) is true...”but it is much simpler
to write “P (i) is true for all natural numbers i 2”.
The statement “if A then B” is referred to as an implication, where A
is the hypothesis and B is the conclusion. The statement “if A then B” is
false exactly when A is true and B is not true. For example, the statement
“if a car is in lot B then the car is red”is false only if there is a car in lot B
that is not red. In particular, it is true if the hypothesis is “vacuous”in the
sense that the parking lot is empty! This bothers some students at …rst, but
it really is consistent: if the only way to show the above statement is false
is to produce a nonred car in lot B then why should it matter whether the
failure to do so is the result of an empty parking lot? It is also important
to remember that an implication is true whenever the hypothesis is false–
regardless of whether the conclusion is true. For example, the statement “if
a is even then 3a is even”is true even though 3a is odd when a is odd. This
discussion can be summarized by stating that the negation of “if A then B”
is “A and not B”.
Very often implications are equivalent to “for all” statements. For ex-
ample, the above statement “if a is even then 3a is even” is equivalent to
the statement, “for all even a, 3a is even.” The negation of this statement
is “there exists some even a such that 3a is odd,” which makes more sense
grammatically than “a is even and 3a is odd.”
6 CHAPTER 1 LOGIC AND SET THEORY

Getting back to the general statement “if A then B”, which may also be
stated “A implies B”or “B only if A”, there are two associated statements,
the converse statement “if B then A” and the contrapositive statement “if
not B then not A”. For example, given the statement “if x = y then x2 = y 2 ”,
the converse is “if x2 = y 2 then x = y” and the contrapositive is “if x2 6= y 2
then x 6= y.”The contrapositive of a given statement is true if and only if the
given statement is true; more succinctly, a statement and its contrapositive
are logically equivalent. Proving or disproving one proves or disproves the
other. On the other hand, there is generally no logical relationship between
a statement and its converse. In the preceding example (assuming x and
y are real numbers) the original statement is true, but its converse is false.
Proving the converse of a statement rather than a statement is one of the most
common abuses of logic, and is used routinely in politics and advertising.

Exercise 1.1 Write a truth table for each of the following:

1. A or B

2. If A then B.

Exercise 1.2 Negation of a truth table is simply carried out by exchanging

the T s and F s in the main part of the table (not the left column and top
row!). Negate the truth table for “A and B” and show that it is identical to
the truth table for “not A or not B”.
If both “A implies B” and “B implies A” are true, then we say that A
and B are (logically) equivalent; we may also express this as “A if and only
if B”or “A i¤ B”.
The previously stated basic rules for negation of statements are few and
simple, but actually negating complex statements can take some practice.
Consider, for example, the statement
1
“For every n 2 N there exist " > 0 and > 0 such that n .” (1.1)
"
which negates as “There exists an n 2 N such that for every " > 0 and > 0,
1
"
<n .”Why did we negate “ 1" n”, but not “" > 0”or “ > 0”? Why
didn’t we change the “and” to an “or”? Note that the symbol “ ” stands
for “greater than or equal to”and so the negation of “ 1" n ”is “ 1" is not
greater than n and not equal to n ” which leaves as the only possibility
1.1 BASIC LOGIC 7

“ 1" < n ”. Negation of complicated statements is one of the most di¢ cult
but important tasks in elementary logic, but with a little practice, it can
become fairly instinctive, as it must be to properly do mathematics.
Note that negating a statement means more than simply declaring that
the statement, or some particular part, is not true. For example consider
the statement “If x > 3 then for every y < 3, y < x.”Here is an incomplete
negation of the statement: “There exists some x > 3 such that it is not true
that for every y < 3, y < x.” If you were planning to use this statement in
a proof, you would still need to …gure out what it means for the last part
to not be true. A complete negation changes the “for every” to a “there
exists”: “There exists some x > 3 such that there exists some y < 3 such
that y x.”This statement may now be further simpli…ed by combining the
existence statements into one: “There exist x and y such that x > 3, y < 3,
and y x.” You should now compare this statement with the original, and
observe that the original is true and its negation, as must be the case, is
false.

Exercise 1.3 Completely negate each of the following statements. To the

best of your ability, based on your prior knowledge, state whether each state-
ment below is true or false. You do not need to supply a proof.

1. 2 < 3 4 Hint: Write out what this means with appropriate usage of
“and” and “or”.
2. For every n > M there exists some " > 0 such that M + " < n.
3. There exists some integer n such that n r for every real number r.
4. For every real number r there exists some integer n such that n r.
5. There exist a real number r and an integer n such that n r.

Exercise 1.4 For each of the following, write down the negation, converse
and contrapositive. To the best of your ability, based on your prior knowledge,
state whether each statement and its converse are true or false. You do not
need to supply a proof!

1. If x > 3 and x < 1 then x = 2.

2. If every green balloon is red and every red balloon is blue, then every
blue balloon is green.
8 CHAPTER 1 LOGIC AND SET THEORY

3. If n and m are integers then there exists some rational r such that
n < r < m.

4. If " > 0 then there exists some > 0 such that + " = 1.

There are certain commonly used symbols that represent basic compo-
nents of logic. “For all” is normally written as “8,” “there exists” as “9”,
“such that” as “•”, “if A then B” as “A ) B”, “A if and only if B” as
“A , B”, “A or B”as “A_B”, and “A and B”as “A^B”. For example, the
statement (1.1) is abbreviated as “(8n 2 N)9 (" > 0 ^ > 0) • ( 1" n )”.
The parentheses are included for clarity. Often the “•” symbol is not used;
the presumption being that the phrase following a “there exist” phrase is
the “such that” phrase. This makes the statement harder to parse at …rst,
but one advantage of doing this is that the process of negation is simpli…ed
(try it!), because the “such that” doesn’t have to be relocated. With the
exception of arrows for implications, this simpli…ed notation will rarely be
used in this text, but every mathematics student should be familiar with it.

1.2 Basic Set Theory

We write “x 2 X”to express “x is an element of the set X”and “x 2 = X”to
express the negation of this statement. We will generally use capital letters
to represent sets and small letters to represent elements of sets (in contrast
with the Axiom of Regularity mentioned earlier). Given sets A and B, the
union of A and B is de…ned to be A [ B := fx : x 2 A or x 2 Bg. One
reads the de…nition of this set as “the set of all x such that x 2 A or x 2 B”.
The intersection of A and B is de…ned by A \ B := fx : x 2 A and x 2 Bg,
and the complement of B in A (more brie‡y “A take away B”) is de…ned
by AnB := fx : x 2 A and x 2 = Bg. The empty set, which is the set with
no elements, is denoted by ?. If A \ B = ? then A and B are said to be
disjoint. We say that A is a subset of B (written A B) if whenever x 2 A,
x 2 B. We say that A is a proper subset of B if A B and there exists some
x 2 B such that x 2 = A. We denote this by A B. If X is a set and A is a
subset of X, we de…ne the complement of A in X by Ac := fx : x 2 X and
x2 = Ag. Note that by de…nition, Ac = XnA. (Some texts use the symbol
“ ”to mean proper subset and “ ”to mean subset, but this terminology is
less common.)
1.2 BASIC SET THEORY 9

For basic set theory de…nitions and proofs it is sometimes useful to use
Venn diagrams, which represent sets by circles and allow one to test hypothe-
ses to help determine whether statements are true. For example, here are
the Venn diagrams for A \ B, A [ B, and A \ B \ C.

Figure 1.1: Basic Venn Diagrams

One might de…ne A [ B to be the set that contains all elements that are
in A and all elements that are in B. This corresponds to the fact that when
one makes the Venn diagram for A [ B, one shades both A and B–a fact that
has the potential to create confusion among beginning students. After all,
the union is de…ned above using an “or” statement–and here we are using
an “and” statement! The di¤erence between these two de…nitions is subtle
but important. The de…nition using “or” de…nes the union in terms of a
property that determines precisely when an individual element is in A [ B,
rather than de…ning the makeup of the set as a whole. The former is much
easier to work with. As the reader may readily test, using the latter in any
proof invariably involves immediately translating into the former.
To show two sets are equal, it is often convenient to show that one is a
subset of the other, and vice versa. We will illustrate this by showing that if A
and B are disjoint then AnB = A. We will begin by showing that AnB A.
Let x 2 AnB. By de…nition x 2 A and x 2 = B. In particular, x 2 A, which is
what we needed to prove. To show that A AnB, suppose that x 2 A. If x
were also an element of B we would have x 2 A\B = ?, which is impossible.
Therefore x 2= B. Since we already had x 2 A this shows that x 2 AnB. The
above proof that x 2 = B is an example of a proof by contradiction, in which
one assumes the negation of what one wishes to prove, and then shows that
10 CHAPTER 1 LOGIC AND SET THEORY

this negation logically implies a false statement and therefore itself must have
been false. The usefulness of proof by contradiction is one of many reasons
why the mathematics student must be good at negating statements. Proofs
by contradiction are particularly useful when the conclusion of a statement
involves negatives.

Exercise 1.5 Prove that for all sets A and B, A \ B A A [ B. So

there are really two statements to be proved: A \ B A and A A [ B.

Exercise 1.6 Completely negate the statement: A B. Hint: Your state-

ment should start with, “There exists some x such that...”

Exercise 1.7 Write out what A 6= B means. Hint: Your statement should
start with “There exists some x such that...”
We refer to a statement like A B as an “inclusion”; the inclusions
proved in the previous exercise are so basic that they will often be used with-
out referring back to the exercise–for example, look for this in the proofs
of the next lemma and de Morgan’s law below. Rather than writing some-
thing like x 2 A and therefore x 2 A [ B we will often shorten this to
x 2 A A [ B.
The student should notice that certain kinds of proofs often begin in the
same way; they have a standard “opening line”. For example, to prove that
a set A is a subset of a set B (no matter how complicated these sets may
be), the “opening line” is “Let x 2 A.” Then the strategy of the proof is to
prove that x 2 B. Often, elementary proofs can be worked out simply by
starting with a standard opening line and then asking the right questions at
each stage–questions like: “What is the de…nition of....”or “What theorems
may be applied in this situation?”
Elementary set theory is completely analogous to elementary logic, and
basic statements in logic have equivalents in set theory, and vice versa. Note
the similarity of the symbols for “and”and “intersect”, and “or”and “union”.
For example, the fact that the negation of an “and” statement is an “or”
statement is expressed in set theory by one of de Morgan’s laws:

An(B \ C) = (AnB) [ (AnC) (1.2)

We will only prove the inclusion . Let x 2 An(B \ C). By de…nition x 2 A
and x 2
= B \ C. That is, it is not true that x 2 B and x 2 C, which means
1.2 BASIC SET THEORY 11

x2= B or x 2= C. When a proof involves an “or”statement it is often useful to

consider each of the two statements as a separate case. For the present proof
suppose …rst that x 2 = B. Since we already have x 2 A, then by de…nition
x 2 AnB, and therefore x 2 (AnB) [ (AnC). In the preceding argument, if
we simply replace the letter “B”by the letter “C”then the exact same proof
will show that x 2 AnC, and therefore x 2 (AnB) [ (AnC). Rather than
wasting time writing this down we may simply state that the proof of the
case x 2= C is “similar”. While this is certainly a time-saver that you should
use when appropriate, there is always the risk that a cursory consideration
will suggest that a proof is “similar”when in fact there is a subtle but crucial
di¤erence.

Exercise 1.8 Prove the opposite inclusion ( ) above and the second de Mor-
gan law:
An(B [ C) = (AnB) \ (AnC) (1.3)

There are other statements that we will use without going through the
proofs, mainly because they reduce to statements in logic that are best
checked using truth tables. Statements we will need are A \ B = B \ A,
A \ (B \ C) = (A \ B) \ C and the identical statements with every “\”
replaced by “[”. These rules are often referred to as the commutative and
associative laws for unions and intersections, since they are clearly analogous
to the rules with those names for addition and multiplication of real num-
bers. It follows (although the proof is a tedious inductive argument that we
will skip) that the order of parentheses and sets themselves is irrelevant for
any combination of unions or any combination of intersections of sets. For
example, it is unambiguous to write A \ B \ C. Mixing intersections and
unions is a di¤erent story, however; for example we will see below that it is
not generally true that (A \ B) [ C = A \ (B [ C).
Although one can prove that a statement is false by showing that it
logically implies another statement already known to be false, often the best
and simplest way to show that a statement is false is to provide a concrete
counterexample. For example, to see why it is false that (A \ B) [ C =
A \ (B [ C) for all sets A, B, C, let A = f1g, B = f2g = C. Then
(A\B)[C = f2g, but A\(B [C) = ?. Remember: in order for a statement
to be true, it must be true for all situations in which they hypotheses are
valid. Therefore, to show a statement is false one simply need show there
exists one situation in which it is not true.
12 CHAPTER 1 LOGIC AND SET THEORY

Exercise 1.9 Let A and B be sets with B A. Prove that An(AnB) = B.

Give an example to show that the statement is not true if we do not assume
that B A.

Exercise 1.10 Consider the following statement: If A B then there is an

x 2 A such that x 2 B.

1. Prove or disprove the statement.

2. Write down the negation and contrapositive of the statement.

3. Prove or disprove the converse of the statement.

Exercise 1.11 Let A and B be sets. Prove that AnB and BnA are disjoint.
A common elementary mistake in trying to disprove a statement is to
point out that a particular attempt at a proof fails to work. This is like
trying to prove that it is impossible to drive from place P to place Q by
showing that one particular road from P leads to a dead end! Nonetheless,
the failure of an attempt at a proof, if carefully analyzed, can sometimes lead
to a concrete counterexample.
Another common mistake is to give a “counterexample”that is not con-
crete. For example, let’s “disprove” the statement: x2 = 1 has no real
solution. Let x and y be real numbers such that y = 2x and y = x2 + 2x + 1.
Then we have 2x = x2 + 2x + 1 or x2 + 1 = 0, or x2 = 1. Since x is a real
number, the statement is false. The error, of course, is that the graphs of
the real functions y = 2x and y = x2 + 2x + 1 do not intersect, so no such x
and y exist. Trying to …nd concrete real x and y with those properties would
quickly have exposed the error.
Yet another frequent error is to try to prove a statement by using a
speci…c example. Students will some times try to get away with this error
by hiding it within a proof by contradiction. Here as an example (thanks
to a previous student) of an incorrect proof of the true statement that if m
and n are odd integers then m + n is an even integer. Suppose not. Let
m = 1 and n = 3. Then m + n = 4 is even, a contradiction. A careful
inspection reveals the error. The “suppose not” should be followed by the
correct negation: There exist odd m and n such that m + n is not even.
The fact that 1 + 3 is even certainly doesn’t contradict this statement. The
point is this: unless a statement concerns only …nitely many situations, each
1.2 BASIC SET THEORY 13

of which you can verify, then you will not be able to correctly prove it with
…nitely many examples, let alone one.
We have the following relations involving both unions and intersections
(called the set theory distributive laws) for all sets A; B; C:

A \ (B [ C) = (A \ B) [ (A \ C) and A [ (B \ C) = (A [ B) \ (A [ C) (1.4)

Exercise 1.12 Prove the distributive laws for sets.

Example 1.2.1 We will prove or disprove the following statement: A B

if and only if AnB = ?. This is an “if and only if” statement. If it is
true, then we need to prove both implications. To disprove it we need only
provide a counterexample to one of the two implications (the “and”in “if and
only if” negates to an “or”). Drawing a Venn diagram suggests that perhaps
the statement is true, so we’ll try to prove it, starting with: If A B then
AnB = ?. If not then there is some x 2 AnB. That is, x 2 A and x 2 = B.
But since x 2 A and A B, x 2 B, a contradiction. For the converse,
suppose that AnB = ?. Let x 2 A. Since AnB = ?, it is not true that
x 2 AnB. This means x 2 = A or x 2 B. We already know that x 2 A, so this
means x 2 B, which …nishes the proof that A B.

Figure 1.2: Disjoint Union Lemma

Lemma 1.2.2 (Disjoint Union Lemma) If A and B are sets then

1. A [ B = (AnB) [ (A \ B) [ (BnA) where any two of the sets on the

right side of the equation are disjoint.
14 CHAPTER 1 LOGIC AND SET THEORY

2. A = (A \ B) [ (AnB) and if B A then this formula reduces to

A = B [ (AnB).

Proof. Let x 2 A [ B. Suppose …rst that x 2 A. Then x 2 B or x 2 = B.

In the …rst case, x 2 A \ B, and in the second case x 2 AnB. In any
event, x 2 (AnB) [ (A \ B) [ (BnA). The proof of the case when x 2 B
is similar, which proves A [ B (AnB) [ (A \ B) [ (BnA). The other
inclusion is an exercise. We will next check that (AnB) \ (A \ B) = ?. If
x 2 (AnB) \ (A \ B) this would mean x 2 AnB, which implies x 2 = B. But
we also have x 2 A \ B, which implies x 2 B, a contradiction. Similarly
(BnA) \ (A \ B) = ?, and B=A and A=B are disjoint by Exercise 1.11. The
proof of the second statement is an exercise.

Exercise 1.13 Finish the proof of the Disjoint Union Lemma.

Exercise 1.14 Prove or disprove for all sets A; B:

1. A [ B = B if and only if A B

2. AnB = ? if and only if A = B

3. If C is any set and C \ A = C \ B and C [ A = C [ B then A = B.

Exercise 1.15 Prove that A B if and only if A B and A 6= B.

Let X and Y be sets. The cartesian product of X and Y is X Y :=
f(x; y) : x 2 X and y 2 Y g. The elements of a cartesian product are
called ordered pairs; the order of the elements in the pair is essential, and
this distinguishes the ordered pair (x; y) from the set fx; yg, in which order
is unimportant. In particular, the cartesian product is not “commutative”;
X Y and Y X are in general di¤erent sets. The cartesian product is one
of the most basic and important ways to construct a new set from existing
sets. For example, as the reader knows, the cartesian (or euclidean) plane is
the cartesian product of the real line with itself.
When proving inclusions of cartesian products, it is important that the
“opening line” calls elements what they are: ordered pairs. For example,
let’s prove that if A B then A C B C. Let (x; y) 2 A C. This
means x 2 A and y 2 C. Since A B, x 2 B. So x 2 B and y 2 C; by
de…nition, (x; y) 2 B C.
1.2 BASIC SET THEORY 15

Figure 1.3: (A B)n(C D)

The following is the “standard picture” for deciding about basic set
theoretic questions involving cartesian products, in this case illustrating
(A B) n (C D).

Exercise 1.16 Using diagrams like the above one, sketch the following:

1. (A B) \ (C D)

2. (A \ C) D

3. (A [ C) (B \ D)

Exercise 1.17 Sketch the following subsets of the cartesian plane R R.

Hint: Start by plotting a few concrete points, and then try to …gure out what
the “boundaries” of the set are.

1. f0g (0; 1)

2. [0; 2] ( 1; 1)

Exercise 1.18 Prove that for any set A, A ? = ?.

16 CHAPTER 1 LOGIC AND SET THEORY

Exercise 1.19 Prove that for nonempty sets A and B, A B=B A if

and only if A = B.

When deciding whether an inclusion involving cartesian products is true,

it is often useful to sketch a picture of the corresponding statement, using
cartesian products of intervals in the plane. Of course the picture doesn’t
consitute a proof, but it may help decide if the statement is true–and if not
suggest a counterexample.

Exercise 1.20 Prove or disprove the following, for any sets A; B; C; D (use
a sketch to help you decide whether each statement is true or false).

1. (A \ B) (C \ D) = (A C) \ (B D)

2. (A [ B) (C [ D) = (A C) [ (B D)

1.3 Functions
De…nition 1.3.1 Let X and Y be sets. A function from (or on) X to (or
into) Y is a subset f of X Y such that

1. For every x 2 X there is some (x; y) 2 f and

2. If (x; y) and (x; z) are in f then y = z.

Without further ado (except for a couple of exercises that you may well
…nd annoying!) we will adopt the standard notation for functions, writing
f : X ! Y and y = f (x) rather than (x; y) 2 f . The …rst condition in the
de…nition is simply the requirement that X be the domain of the function, i.e.
that f be de…ned at every point in X. The second condition is the familiar
requirement that a function be single-valued in the sense that if f (x) = y
and f (x) = z, then y = z. The set of all y 2 Y such that y = f (x) for some
x 2 X is called the range of f .

Exercise 1.21 Prove that the empty set is a function de…ned from the empty
set into itself. This is a particularly uninteresting function and as a result
we will generally only consider functions with nonempty domains.
1.3 FUNCTIONS 17

De…nition 1.3.2 If f : X ! Y is a function and A X we de…ne f (A) =

fy 2 Y : y = f (x) for some x 2 Ag, called the image of A. If B Y , we
1
de…ne f (B) = fx 2 X : f (x) 2 Bg, called the inverse image of B.

Example 1.3.3 Let f (x) = sin x. Then f 1 (f0g) = fn : n 2 Zg, and

f ([0; 2 ]) = [0; 1]. In addition, f 1 ([ 1; 1]) = R.
1
Exercise 1.22 For any function f , prove that f (?) = ? and f (?) = ?.

Exercise 1.23 Let f (x) = x2 . Determine the following sets (no proof needed):
f (f1; 1g), f 1 ((0; 1)), f (f 1 (f 1g)), f 1 (f (f 1g)).

Exercise 1.24 Let f : X ! Y be a function and A X. By de…nition it

is always true that if x 2 A then f (x) 2 f (A). Prove or disprove: If x 2
=A
then f (x) 2
= f (A).

Exercise 1.25 Let f : X ! Y be a function and B Y . By de…nition

it is always true that if x 2 f 1 (B) then f (x) 2 B. Prove or disprove: If
x2 = f 1 (B) then f (x) 2
= B.

Example 1.3.4 We will prove that f (A \ B) f (A) \ f (B). Let y 2

f (A \ B). By de…nition there exists some x 2 A \ B such that f (x) = y.
Since x 2 A, y 2 f (A) and since x 2 B, y 2 f (B). That is, y 2 f (A)\f (B).
Is the reverse inclusion true? Here is a false proof: Let y 2 f (A) \ f (B).
Since y 2 f (A) there is some x 2 A such that f (x) = y. Likewise there is
some x 2 B such that f (x) = y. Since x 2 A and x 2 B, x 2 A \ B and
hence y 2 f (A\B). The problem of course is we have used the same notation
“x”when writing out the meaning of y 2 f (A) and y 2 f (B), and there is no
reason why we should be able to pick the same x in each case. For example, if
f (x) = x2 and A = f0; 1g and B = f0; 1g then f (A \ B) = f (f0g) = f0g,
while f (A) \ f (B) = f02 ; 12 g \ f02 ; ( 1)2 g = f0; 1g. In Section 4.1 we will
de…ne a property of functions that allows us to prove the opposite inclusion.

Example 1.3.5 As for inverse images of sets and intersections we have

f 1 (A \ B) = f 1 (A) \ f 1 (B). In fact, x 2 f 1 (A \ B) , f (x) 2
A \ B , f (x) 2 A and f (x) 2 B , x 2 f 1 (A) and x 2 f 1 (B) ,
x 2 f 1 (A) \ f 1 (B). This proof illustrates another way to prove “P if and
only if Q”: Show that P is equivalent to another statement, which is equiv-
alent to another, and so on, …nally reaching a statement that is equivalent
18 CHAPTER 1 LOGIC AND SET THEORY

to Q. However, in doing such a proof one needs to be very careful that both
implications are easily proved at each step.

Example 1.3.6 Let f : X ! Y be a function. We will prove that for any

B Y , f (f 1 (B)) B. Let y 2 f (f 1 (B)). By de…nition of f (f 1 (B))
there exists some x 2 f 1 (B) such that f (x) = y. Now by de…nition of
f 1 (B), y = f (x) 2 B. Is it always true that f (f 1 (B)) = B? If you
have answered Exercise 1.23 correctly then you know that these sets are not
equal. We will de…ne in Section 4.1 a property that will allow us to prove the
opposite inclusion.

Exercise 1.26 Prove that if f : X ! Y is a function and y 2 Y , then

f 1 (fyg) = fx 2 X : f (x) = yg, and give an example of a function f :
f0; 1g ! f0; 1g such that f 1 (f0g) = ?.
1
Exercise 1.27 Let f : X ! Y be a function. Prove that A f (f (A)) for
every A X.
We list now list various statements involving images and inverse images
of functions:

f (A [ B) = f (A) [ f (B) and f (A \ B) f (A) \ f (B) (1.5)

1 1 1 1 1 1
f (A [ B) = f (A) [ f (B) and f (A \ B) = f (A) \ f (B) (1.6)
1 1 1
f (AnB) = f (A)nf (B) and f (A)nf (B) f (AnB) (1.7)

Exercise 1.28 Prove the statements (1.5-1.7) that were not proved earlier.
Chapter 2

The Real Numbers

2.1 Field Axioms

The axioms in this section are familiar to most students from before high
school. They are quite natural. Many of them, such as the distributive
and associative laws, can be observed in simple concrete situations, such
as counting apples, and have been understood and accepted for thousands
of years. Others, such as the existence of 0, or the existence of additive
inverses, which leads to negative numbers, have been readily accepted only
more recently. After all, even if you accept that one can physically have
0 apples, 5 apples is a little harder to visualize. However, whether or
not 5 apples makes physical sense, we now know that negative numbers
are extremely useful in many situations. Rather than denying their existence
generally, as some mathematicians and scientists (and religious leaders!) have
tried to do in previous centuries, we simply recognize that, in the process of
translating from an application to mathematics, solving the problem, and
translating back, we must be on the lookout for extraneous solutions, or
solutions that don’t make sense in terms of the original problem.
A …eld is a set F having two operations + and (addition and multipli-
cation) satisfying the following axioms:

1. (Associative Laws) (a + b) + c = a + (b + c) and a(bc) = (ab)c for all

a; b; c 2 F

2. (Commutative Laws) a + b = b + a and ab = ba for all a and b in F

19
20 CHAPTER 2 THE REAL NUMBERS

3. (Additive and Multiplicative Identities) There exist elements 0 and 1

in F with 1 6= 0, such that a + 0 = a and 1 a = a for all a 2 F

4. (Additive and Multiplicative Inverses) For all a 2 F there is some

a 2 F such that a + ( a) = 0 and if a 6= 0 there exists some a 1 2 F
such that aa 1 = 1

5. (Distributive Law) a(b + c) = ab + ac for all a; b; c 2 F.

Formally speaking, the operations are functions from the cartesian prod-
uct F F into F, but we won’t use such formalities here (any more than we
used the formal de…nition of function as a set of ordered pairs). Although
there are many important …elds, in this text we will be mainly concerned
with the rational numbers and real numbers. From the above …ve axioms
can be deduced all the algebraic theorems that the reader has used since
childhood. We will prove many of those theorems here and in subsequent
sections. The idea of uniqueness has a fairly important role in mathematics,
and we will begin with some basic uniqueness results.

Proposition 2.1.1 For all a; b in a …eld, the equation a+x = b has a unique
solution x.
By now basic algebra has become fairly “automatic” to the reader, and
he or she might give the following argument

a+x=b (2.1)
0 + x = ( a) + b
x = b + ( a)

Does this mean that x really is a solution to our original equation? Does this
show that x is unique? Let’s …rst consider the question of whether b + ( a)
is actually a solution. To check this, we replace x by b + ( a) in the left
side of the original equation and reduce it to b using the commutative law,
associative law, the additive inverse, and the additive identity:

a + (b + ( a)) = a + (( a) + b) = (a + ( a)) + b = 0 + b = b

Is this solution unique? Suppose that we have two solutions x; x0 of a+x = b.

This implies a + x0 = a + x. We may add a to each side (and use the
associative law) to obtain 0 + x0 = 0 + x, which by the additive identity
2.1 FIELD AXIOMS 21

implies that x = x0 . So there is exactly one solution to a + x = b and that

solution is b+( a). This not only proves the proposition, but tells us exactly
what the solution is. This situation is better than what happens with other
kinds of equations (including di¤erential equations) in which one may prove
that an equation has a solution (even a unique one) via a proof that doesn’t
actually tell you what the solution is.
Applying Proposition 2.1.1 to the equation a + x = a we see that 0 is the
unique additive identity. More formally stated:

Lemma 2.1.2 If b 2 F has the property that for some a 2 F, b + a = a then

b = 0.

Proof. The number 0 is a solution to the equation x + a = a, and since b is

also a solution, b = 0.
Likewise, applying the proposition to a + x = 0 we see that each a has a
unique additive inverse. That is, if b 2 F satis…es a + b = 0 then b = a. In
fact, we could have replaced the two axioms concerning the additive inverse
and identity by a single one asserting the existence of a unique solution to
all equations of the form a + x = b (see Exercise 2.7 below). These facts
give us a new way to view the statements (2.1). First note that the top
statement implies the middle one. In fact, we get the middle one by adding
a to each side of the top one and using the additive identity. Now the
second line implies the third line, using the additive identity. This proves
“If a + x = b then x = b + ( a),” which is the uniqueness of the solution.
Going from bottom to top, the last line implies the middle line by adding 0,
and the top line follows from the middle one by adding a to each side (and
using the associative and commutative laws). This proves the statement “If
x = b + ( a) then a + x = b”, which shows that b + ( a) is in fact a solution.
So the “downwards” logic is uniqueness of the solution and the “upwards”
logic is the existence of a solution.
The statements (2.1) give no indication of which way the logic goes, and
this is a serious omission in general. Consider, for example, the following
“proof”that 1 = 2.

1=2 (2.2)
1 0=2 0
0=0
22 CHAPTER 2 THE REAL NUMBERS

This example plays on the common (and logically incorrect) strategy learned
in high school algebra of starting with the statement that one wants to verify,
and manipulating it algebraically to obtain a true statement. In high school
algebra this plan generally worked because the algebraic manipulation always
produced logically equivalent statements. However, we will more and more
consider steps that do not produce logically equivalent statements, and in
these cases the strategy is clearly backwards. To prove a statement one must
start with something known to be true and deduce the statement, not the
other way around. In the above example the …rst line implies the second line,
which implies the third line (see Lemma 2.1.3 below)–but this only serves to
illustrate that a false statement can logically imply a true statement! Of
course the second statement does not imply the …rst; in order to go this way
one would have to multiply by the multiplicative inverse of 0, and our axioms
do not provide for such a thing. From this point on, all arguments of this
sort, which we will refer to as “parallel” arguments because they involve a
list of statements in parallel, must have an indication of which way the logic
goes. The argument (2.1) should be

a+x=b
, 0 + x = ( a) + b
, x = b + ( a)

and the argument (2.2) should be

1=2
)1 0=2 0
,0=0

Exercise 2.1 State and prove a theorem about the existence and uniqueness
of solutions of equations of the form ax = b for a; b; x in a …eld. This can
be used to prove uniqueness of the multiplicative identity and multiplicative
inverses. Hint: Be careful about a = 0.

Lemma 2.1.3 For any a 2 F, 0 a = 0.

Proof. Using the multiplicative identity, distributive law, and additive iden-
tity we have

(0 a) + a = (0 a) + 1 a = (0 + 1) a = 1 a = a.
2.1 FIELD AXIOMS 23

That is, 0 a is a solution to x + a = a and the proof is …nished by Lemma

2.1.2.

Lemma 2.1.4 If a; b 2 F and ab = 0 then a = 0 or b = 0.

Proof. If not, then a 6= 0 and b 6= 0 and in particular a 1 exists. Multiplying
each side of ab = 0 by a 1 and applying Lemma 2.1.3 plus a couple of axioms
we have
0 = a 1 0 = a 1 ab = b
which is a contradiction.
The next statement gives some beginning students trouble; they claim
no proof is necessary because the “minus signs cancel”. But what does this
mean? We haven’t de…ned a notion of “cancel” or even “minus sign” as an
object in itself. Really, “minus signs cancel” is nothing but a translation of
the statement we need to prove into words that we haven’t de…ned! In the
words that we have de…ned, we need to prove that the additive inverse of the
additive inverse of a is equal to a. The strategy again uses uniqueness.

Lemma 2.1.5 For any a 2 F, ( a) = a.

Proof. Since a + ( a) = 0 (by de…nition of the additive inverse), a is a
solution to the equation x + ( a) = 0. Since ( a) is also a solution,
uniqueness …nishes the proof.

Exercise 2.2 Consider the statement: For any a 2 F, ( 1) a = a.

1. Prove the statement using a “parallel” argument starting with 0 = 0

and showing this implies ( 1) a = a. Hint: Work it “backwards”
reducing ( 1) a = a to 0 = 0, then justify each step in reverse.

2. Prove the statement using the uniqueness of a.

3. Use the statement to show that for b 2 F, (a + b) = ( a) + ( b) and

(a)( b) = (ab).

Exercise 2.3 State and prove analogs of Lemmas 2.1.2 and 2.1.5 for the
operation of multiplication. Hint: Be careful to show that a 1 6= 0 when
a 6= 0.
1
Exercise 2.4 Prove that for non-zero a; b 2 F, (ab) = a 1b 1.
24 CHAPTER 2 THE REAL NUMBERS

1
Exercise 2.5 Prove that 0 = 0 and 1 = 1 using uniqueness.

Exercise 2.6 Prove that for any a 6= 0, (a 1 ) = ( a) 1 .

Exercise 2.7 Suppose we are given that a + x = b has a unique solution for
all a; b2 F. Use this fact, and only the associative and commutative laws,
to show that there exists an additive identity. Hint: Let 0a be the unique
solution to a + x = a. Next show that for any b 2 F, b + 0a is a solution to
a + x = a + b. You may not use additive inverses in the proof!
We will now introduce the customary notation that you have used since
childhood. We are not proving anything here, but just giving a convenient
way to write certain things. First, we may denote b + ( a) by b a. We
really should check that this notation works the way we expect. For example,
using various axioms and exercises we see that the distributive law works as
expected:

a(b c) = a(b + ( c)) = ab + a( c)) = ab + (ac) = ab ac

Similarly we denote ab 1 by ab when a; b 2 F and b 6= 0. We will check that

the usual methods for multiplying and adding fractions are valid. First, the
commutative law and Exercise 2.4 show that
a c 1 1 1 ac
= ab cd = (ac) b 1 d 1
= (ac) (bd) = .
b d bd
Next, using the distributive law we have
a c 1 1 1 a+c
+ = ab + cb = (a + c)b = .
b b b
x 1
Finally, since x
= xx = 1 for any nonzero x 2 F, we see that

a c ad cb ad + cb
+ = + = .
b d bd bd bd
1
Exercise 2.8 Prove that for any a 6= 0 in F, a
= a 1.

Exercise 2.9 Prove that for a; b 2 F, ( ab ) = b

a
.
a c ad cb
Exercise 2.10 Prove the formula b d
= bd
.
2.2 ORDER AXIOMS 25

One theorem that is often omitted from elementary texts is the fact
that sums and products of any length are independent of arrangement of
parentheses–e.g. a(b(cd)) = (ab)(cd) for any a; b; c; d 2 F. As it turns out,
this is not so easy to prove. For one thing, because it applies to products of
arbitrary length, the proof requires the principle of mathematical induction,
which we will learn about later. Even with induction the proof, while not
deep, is very tedious. We refer the reader to a more avanced text on abstract
algebra for the proof. But we do leave the reader with the following exercise
that gives a small taste of the general proof:

Exercise 2.11 Prove that for a; b; c; d 2 F a(b(cd)) = ((ab)c)d.

At this point we have proved almost all of the basic algebraic rules that
you have learned previously, and from now on we will use these rules without
speci…c reference to this section, and (except perhaps on a test!) you will
not be required to state every axiom or theorem that you use for algebraic
manipulations. That is, you may revert back to doing basic algebra as you
did in calculus.

2.2 Order Axioms

If F is a …eld it may also satisfy additional axioms, called the Order Axioms
(there are …elds that do not satisfy them). From now on we assume that
there is a subset of F F, membership of which will be denoted by a < b,
such that the following axioms are satis…ed for all a; b; c 2 F:

1. (Transitivity) If a < b and b < c then a < c.

2. (Trichotomy) Exactly one of the following is true: a < b, b < a or

a = b.

3. (Additive Property) If a < b then a + c < b + c.

4. (Multiplicative Property) If a < b and c > 0 then ac < bc.

From these three axioms and the algebraic axioms follow the basic “pre-
calculus”facts concerning inequalities and algebraic operations that the reader
has learned previously. We will prove several of them below. We also use
the following notation: a > b means the same thing as b < a. Moreover,
26 CHAPTER 2 THE REAL NUMBERS

a b means a < b or a = b, with similar meaning to a b. We say that a is

positive if a > 0 and negative if a < 0.

Lemma 2.2.1 For any a 2 F, if a < 0 then a > 0.

Proof. By the additive property, ( a) + a < ( a) + 0, which is equivalent
to the inequality we need.
We next prove the familiar ordering of 0, 1, and 1.

Lemma 2.2.2 0 < 1.

Proof. One of our axioms is that 1 6= 0, so the trichotomy tells us that
either 1 > 0, which is what we want to show, or 1 < 0. Suppose that 1 < 0.
Then by Lemma 2.2.1, 0 < 1. We may now use the multiplicative property
to see that
0 = 0 ( 1) < ( 1)( 1) = 1
which is a contradiction.

Exercise 2.12 Prove that if a > 0 then a < 0, and in particular 1 < 0.

Exercise 2.13 De…ne 2 := 1 + 1 and prove that 2 > 1.

Exercise 2.14 Prove that if a < b and c < d then a + c < b + d.

For any a 2 F, de…ne a2 := a a.

Exercise 2.15 Prove that if a 6= 0 then a2 > 0.

Exercise 2.16 Prove that if 0 < a < 1 then 0 < a2 < a.

The multiplicative property tells us that multiplication by a positive num-
ber does not change an inequality. The familiar rule for multiplication by
negative numbers may now be proved:

Lemma 2.2.3 If a < 0 and b < c then ab > ac.

Proof. Since a < 0, a > 0 by Lemma 2.2.1 and we have ( a) b < ( a) c.
Adding ab + ac to each side …nishes the proof.

Corollary 2.2.4 If a < 0 and b > 0 then ab < 0.

1 1
Lemma 2.2.5 If a > 1 then 0 < a < 1. In particular, 0 < 2
< 1.
2.3 COMPLETENESS AXIOM 27

Proof. If a 1 < 0 then 1 = a 1 a < 0, a contradiction, so a 1

> 0. Now we
may multiply each side of a > 1 by a 1 to obtain 1 > a 1 .

Lemma 2.2.6 If > 0 then there exists some " such that 0 < " < .

Proof. Let " := 2 . Multiplying 0 < 12 < 1 through by > 0 …nishes the
proof.
A very common method for showing that a = b is to show both a b
and b a. Then by the trichotomy, the only possibility is a = b. A useful
basic technique for showing that a b is given by the following exercise.

Exercise 2.17 Let a; b 2 F.

1. Show if a b + " for every " > 0 then a b. Hint: Suppose not and
choose " < a b.

2. Prove or disprove: If a < b + " for every " > 0 then a < b.

At this point we have proved almost all of the basic rules that you have
learned concerning algebraic operations and inequalities. You will prove a
little more in the next exercise, but to be complete we would have to consider
many similar variations on these results. We will simply declare all such
theorems as “similar” to these and use them without further reference. As
mentioned at the end of the last section, once this section is …nished you may
in subsequent homework do basic steps involving inequalities as you did in
calculus, without citing axioms or theorems.

Exercise 2.18 Let x; y; z; w 2 F.

1. Prove that if x y and z w then x + z y + w.

2. Prove that if 0 < x y and 0 < w < z then xw < yz.

2.3 Completeness Axiom

The real numbers have one …nal axiom, but before stating it we need some
preliminaries. We continue to assume that F is an ordered …eld.
28 CHAPTER 2 THE REAL NUMBERS

De…nition 2.3.1 A nonempty subset A of F is bounded above if there exists

some M 2 F (called an upper bound of A) such that x M for all x 2 A.
If there exists an upper bound s of A such that s M for all upper bounds
M of A then s is called a supremum (or sup–with a long “u”) of A. If s is a
supremum of A and s 2 A then s is called a maximum of A. . Lower bound,
in…mum and minimum are de…ned similarly. A subset that is bounded above
and below is simply called bounded.
It is important to remember that the supremum of a set A has two prop-
erties: (S1) sup A is an upper bound for A and (S2) if M is an upper bound
for A then sup A M . For this reason a supremum is sometimes called a
least upper bound of A.

Lemma 2.3.2 If A 6= ? is a subset of F then if sup A exists, it is unique.

Proof. Suppose that s and s0 are suprema of A. Then s0 is an upper bound
of A by condition S1 above, and by condition S2, s s0 . But a similar
argument shows s0 s and so s0 = s.

Notation 2.3.3 Since we now know that the supremum s of A, if it exists, is

unique, we may give it a name that only depends on the set A. We will denote
the supremum of A by sup A and the maxumum which, being the supremum,
is unique if it exists, will be denoted by max A.

Example 2.3.4 Suppose that A = fx; yg is a subset of F and suppose that

x y. Then y is an upper bound for A. Now suppose that M is any upper
bound for A. Then since y 2 A, y M . By de…nition, y = sup A, and since
y 2 A, y = max A.

Exercise 2.19 Prove that if A F is nonempty and M is an upper bound

of A such that M 2 A then M = max A. A similar statement holds for lower
bounds and minima (you don’t need to prove it).
The …nal axiom for the real numbers states:

Axiom 2.3.5 (Completeness) If A is a nonempty subset of F that is bounded

above, then A has a supremum.
It is possible to prove using only the axioms of set theory that there exists
a unique ordered …eld that satis…es the Completeness Axiom, which is what
we call R, the set of real numbers. From this point on we will no longer
2.3 COMPLETENESS AXIOM 29

consider ordered …elds except R and Q. The completeness axiom in some

sense “…lls in the
p holes” in the rational numbers
p Q. For example, we will
show later that 2 is not rational, but that 2 does exist in R. First there
are natural questions concerning how in…ma and suprema interact with basic
set theory operations.

Lemma 2.3.6 Suppose that A; B are subsets of R such that A 6= ?, A B

and B is bounded above. If M is an upper bound for B then M is an upper
bound for A, and sup A sup B. Similar statements hold for lower bounds
and in…ma.
Proof. First note that since A is non-empty, so is B and therefore sup B
exists. Suppose M is an upper bound for B and let x 2 A. Since A B,
x 2 B and therefore x M , which proves M is an upper bound for A. Since
sup B is an upper bound for B, sup B is an upper bound for A. By Property
S2, sup A sup B.
The above proof illustrates a simple but useful technique. If you are ever
called upon to prove that sup A x for some real set A and number x, all
you have to do is prove that x is an upper bound for A. This method will
come in handy for some of the exercises below.

Example 2.3.7 We will show that if A; B are nonempty subsets of R that

are bounded above, and A \ B 6= ? then
sup(A \ B) minfsup A; sup Bg.
Note that since A \ B A A \ B is bounded above by Lemma 2.3.6. Suppose
that sup A sup B; the proof of the opposite inequality is similar. So we
need to prove that sup(A \ B) sup A, i.e. we need to prove that sup A
is an upper bound of A \ B. Let x 2 A \ B. Then x 2 A and therefore
x sup A by S1, which proves sup A is an upper bound for A \ B and hence
sup(A \ B) sup A.

Exercise 2.20 Let A; B be as in the previous example. Show by concrete

example that it is possible that sup(A \ B) < minfsup A; sup Bg. Hint: To
make an example you need only two numbers in each of A and B.

Exercise 2.21 Prove: Let A; B be nonempty sets of real numbers that are
bounded above. Then
sup (A [ B) = max fsup A; sup Bg .
30 CHAPTER 2 THE REAL NUMBERS

The following lemma formalizes what the reader may have already in-
stinctively realized: that there are elements of A that are arbitrarily close to
sup A. This “analytical description”of the supremum is extremely useful.

Lemma 2.3.8 (Approximation Property for the Supremum) Let A be a non-

empty set of real numbers that is bounded above. Then s = sup A if and only
if

1. s is an upper bound of A and

2. for every " > 0 there exists some x 2 A such that x > s ".

There is a similar statement for the in…mum.

Proof. First suppose that s = sup A. Then by de…nition s is an upper
bound of A. If the second condition is false then there exists some " > 0
such that for all x 2 A, x s ". But then s " is an upper bound of A and
s " < s = sup A, a contradiction. Conversely, assume the two conditions
above. If s 6= sup A then by de…nition of the supremum, there exists some
upper bound M of A such that M < s. Let " := s M > 0. Then there is
some x 2 A such that x > s " = s (s M ) = M , which contradicts the
fact that M is an upper bound of A.

Exercise 2.22 Write down and prove the corresponding statement for in-
…ma to Lemma 2.3.8.
The Approximation Property makes it easy to check some concrete ex-
amples. Recall that real bounded intervals are de…ned by

(a; b) := fx 2 R : a < x < bg

[a; b] = fx 2 R : a x bg
(a; b] = fx 2 R : a < x bg
[a; b) := fx 2 R : a x < bg

Example 2.3.9 Consider …rst the interval [0; 1). By de…nition, 1 (and any
real number M > 1) is an upper bound of [0; 1). Now let " > 0. If " > 21
then x := 12 2 (0; 1] and x > 1 ". If " 12 then since " > 0 by Lemma 2.2.6
we may choose some positive < ". Let x := 1 > 1 ". Since > 0, we
1
also have x < 1. Since < " 2
we have x = 1 > 1 " 1 12 = 12
2.3 COMPLETENESS AXIOM 31

and therefore x 2 [0; 1). Therfore we have veri…ed the second condition of
the Approximation Property and shown that sup[0; 1) = 1. Note that 1 is not
a maximum since it is not in [0; 1), but by a similar argument 1 = max[0; 1].

Exercise 2.23 Prove that for any real interval (a; b), a = inf(a; b). Of
course similar statements apply to in…ma and suprema of the various other
bounded intervals.

Exercise 2.24 Let A R be nonempty and bounded above, with s :=

sup A 2
= A. Show that if x 2 A then there is some y 2 A such that y > x.
Write down but do not prove the corresponding statement for the in…mum.
The statement of the next Theorem, that positive real numbers have
unique positive square roots, is well-kown to the student. What is more
important is the proof of the theorem, which involves many important tech-
niques that are used very frequently in analysis. An important step is to be
sure that you can work out this proof entirely on your own. While this may
seem at …rst like a daunting task, note that you should not try to memorize
the proof, but rather think about the very natural parts that the proof breaks
into. Each of these parts is, by itself manageable.
Among the important techniques you will see in the next proof: Reducing
the problem to a case that is simpler to work out and easily implies other
cases, “throwing away” or simplifying terms to make inequalities easier to
work out, and chosing positive numbers such as " that are smaller than two
or more di¤erent numbers in order to give " several useful properties. We
can do the latter as a result of Lemma 2.2.6. The proof below, as written,
is longer than it needs to be because it includes discussion of how one might
solve it for the …rst time. Much of the work in solving problems in analysis
involves …nding appropriate estimates for numbers that make things work.
Actually …nding those estimates is the hard part, and the proof below gives
some hints about how that process works.

Theorem 2.3.10 For any a > 0, in R there is a unique real number s > 0
such that s2 = a.
Proof. To simplify matters we will …rst suppose that a > 1. We will see later
why this is useful, but for now simply note that we are interested in squaring
numbers, and inequalities. The number 1 is signi…cant because if x is positve
then x2 < x or x2 > x according to whether x < 1 or x > 1. We will show
32 CHAPTER 2 THE REAL NUMBERS

that the desired number s is the supremum of the set A := fx > 0 : x2 < ag;
that is, s is the least positive number having a square a.
Of course we need to start with showing that sup A exists. Note that
1 2 A 6= ?. We will show that a is an upper bound for A. In fact, if x > a
then since a > 1, x2 > a2 > a. That is, if x > a then x 2 = A, which is the
contrapositive of what it means for a to be an upper bound of A. Therefore
sup A exists (and in fact sup A 1).
We will show that s2 = a by eliminating the two other possibilities.
Suppose …rst that s2 < a. We will prove that there exists some " > 0 such
that (s + ")2 < a. That is, s + " 2 A and s + " > s, a contradiction to S1. We
will do as you have done at least since high school: start with (s+")2 < a and
try to “solve” for an inequality involving ". However, you now know that,
in the end, the logic must go backwards, since we are starting with what we
are trying to prove. Expanding gives us s2 + 2s" + "2 < a. The left side
is a quadratic expression in ", and your …rst impulse might be to use the
Quadratic Formula and try to work out the inequality that way. But there
is a small (but fatal) problem: the Quadratic Formula involves square roots,
and we can’t use square roots to prove that square roots exist! Wouldn’t life
be simpler if the "2 were just "? Then we could do some algebra to obtain
s2
" < a2s+1 . Since the latter quantity is positive (by assumption a > s2 ) we
s2
could certainly choose " so that 0 < " < a2s+1 . Now working backwords, this
implies that s + 2s" + " < a, while what we need is s2 + 2s" + "2 < a. Now if
2

"2 were smaller than ", then s2 + 2s" + " < a would imply s2 + 2s" + "2 < a
and we would be …nished. But we can accomplish this as long as we make
sure " < 1. Having done the calculation, we now clean the whole thing up
and write down the “slick”version:n o
s2
Let " > 0 be less than min 1; a2s+1 . Since " < 1, "2 < " and

(s + ")2 = s2 + 2s" + "2 < s2 + "(2s + 1)

a s2
< s2 + (2s + 1) < a.
2s + 1
Next suppose that s2 > a. Taking a hint from what we just did, we would
like to …nd an " > 0 such that (s ")2 > a. But we need to be a little more
careful, and this time also choose " < s so that s " > 0. If we do this then
we get our contradiction: According to the Approximation Property there
should be some x 2 A such that x > s ". But if x > s " > 0, then
x2 > (s ")2 > a, which means x 2 = A.
2.3 COMPLETENESS AXIOM 33

Let’s start as in the previous case: Expanding gives us s2 2s" + "2 > a.
We again want to get rid of the square. Since we are dealing with the opposite
inequality this time, we want to make the quantity s2 2s" + "2 smaller, not
larger, for our next inequality. The easiest way to do this is to just throw
"2 away! That is, since "2 > 0, if we have s2 2s" > a then certainly
2
s2 2s" + "2 > a. Finally s2 2s" > a reduces to " < s 2s a ; the latter
quantity is positive since s2 > a, and we have our starting point. Here is the
“slick”version: n 2 o
2
Since s 2s a > 0, we may choose " such that 0 < " < min s; s 2s a . Now

s2 a
(s ")2 = s2 2s" + "2 > s2 2s =a
2s
and as previously argued we obtain a contradiction.
If a = 1 then take s = 1. If a < 1 then a1 > 1 and by what we proved
above there is some c such that c2 = a1 . Let s := 1c and we obtain s2 = c12 = a.
For uniqueness note that if 0 < x < s then x2 < s2 = a and likewise if
x > s then x2 > a, so in either case x2 6= a. p
As usual we will denote the number s in the above proposition by p a
1=2
or
p a . It follows from the …eld and order axioms that if a < b then a <
b. With more e¤ort one can prove the existence of nth roots of positive
numbers exist. But we turn now to more basic properties of the supremum
and consequences of completeness. As we have stated earlier, there is only
one complete ordered …eld, namely R. Although some of the theorems below
are true for possibly non-complete ordered …elds, we from now on we will
only work with the real numbers.

De…nition 2.3.11 If A R de…ne A := fx : x 2 Ag. A is called the

re‡ection (or negation) of the set A.

Exercise 2.25 Let A R. Prove that ( A) = A.

The statement of the next lemma comes in a form that is common in
mathematics. “Resp.”is an abbreviation of “respectively”and the lemma is
really two statements in one. The …rst statement involves completely igoring
the parenthetical parts: “If A R is nonempty and M is an upper bound
for A then M is a lower bound for A.” The second statement involves
replacing the words preceding the parentheses by those inside: “If A R
is nonempty and M is a lower bound for A then M is an upper bound
34 CHAPTER 2 THE REAL NUMBERS

for A.” In general the two statements must each be proved, but it often
happens (as it does below) that the two statements have similar proofs.

Lemma 2.3.12 If A R is nonempty and M is an upper (resp. lower)

bound for A then M is a lower (resp. upper) bound for A. In particular,
if A is bounded above then inf( A) exists and inf( A) = sup A.

Proof. First note that if a 2 A then a 2 A, so A is nonempty. Let

x 2 A. By de…nition, x 2 A, so x M , which implies x M . The
proof of the respective statement is similar. Now suppose L is any lower
bound for A. By a similar argument, L is an upper bound for A. By
de…nition of supremum, L sup A, which implies L sup A. That is,
sup A satis…es the de…nition of inf( A).

Exercise 2.26 Prove that if A R is nonempty and bounded below then

inf A exists and inf A = sup( A).

2.4 Absolute value

For any x 2 R we de…ne the absolute value of x to be jxj = x if x 0 and
jxj = x if x < 0.

Exercise 2.27 Prove that the absolute value is positive de…nite: This means
that jxj 0 for all x 2 R, and jxj = 0 if and only if x = 0.

Exercise 2.28 Prove that jxyj = jxj jyj for all x; y 2 R.

Inequalities of sums, however, are not so cleanly behaved:

Proposition 2.4.1 (Triangle Inequality) For any x; y 2 R we have

jx + yj jxj + jyj

The proof of the triangle inequality involves a series of steps, the …rst of
which is the following useful lemma:

Lemma 2.4.2 For all x 2 R and M 0, jxj M if and only if M x

M . The same statement holds if every “ ” is replaced by “<”.
2.4 ABSOLUTE VALUE 35

Proof. Suppose that jxj M . According to the de…nition of absolute value,

there are two cases to be considered: First suppose that x 0. Then jxj = x
and we have M < 0 x M . If x < 0 then x = jxj M and therefore
x M . We have M x < 0 M .
For the converse, suppose that M x M . Again we need to check
cases. If x 0 then jxj = x M . If x < 0 then x M and jxj = x M .
The last statement is an exercise.

Exercise 2.29 Rewrite the proof of Lemma 2.4.2 to show that the statement
is true when every “ ” is replaced by “<”.
To prove the triangle inequality, note that for any x, jxj jxj. Applying
the above lemma we have jxj x jxj. We may obtain a similar inequality
for y, and adding these inequalities together gives us (jxj + jyj) x + y
jxj + jyj. Applying the lemma one more time gives the triangle inequality.
Note that the lemma has completely saved us from considering cases; without
the lemma we would have to go through a total of at six cases involving x,
y, and x + y.
The triangle inequality is an extremely powerful tool, one of the most
important theorems in mathematics. It is true in a variety of settings–you
will have seen it if you have studied vector spaces. In fact the above trian-
gle inequality is a special case of the triangle inequality for vector spaces–
considering R is a one-dimensional real vector space. In higher dimensions
the vectors involved clearly form a triangle, hence the name of the theorem.
In R the three points x; y; x + y still form a triangle, but it is ‡attened in a
one-dimensional space.

Exercise 2.30 Prove that if x; y; z 2 R, then jx + y + zj jxj + jyj + jzj.

A similar inequality holds for any number of terms, and we will refer to any
such inequality as the triangle inequality.
In general one may apply the triangle inequality as follows: jx yj =
jx + ( y)j jxj + jyj. However, there is another version of the triangle
inequality that is often useful:

Exercise 2.31 Prove that for any x; y 2 R, jx yj jxj jyj. Hint: Apply
the triangle inequality to jy + (x y)j.

Exercise 2.32 Prove that for all x; y 2 R, jx + yj = jxj + jyj if and only if
xy 0. Hint: Square each side of the equation.
36 CHAPTER 2 THE REAL NUMBERS

The absolute value of a real number is really a measure of its “size”–or

how far away from 0 it is. The fact that it is non-negative makes it very easy
to work with. Inequalities of the form jxj M are widely used in science
because they control the size of the quantity x. For example, in engineering
problems one is allowed a certain amount of error or tolerance. A resistor
may be marked “500 5 ohms”, meaning the actual value is in somewhere
between 495 and 505 ohms. But for actual computations, for example to
determine whether a given circuit requires a resistor with a tolerance of 5
ohms or 1 ohm, it is often easier to work with the correpsonding positive
error, 5 or 1. In a common problem, one is given a formula and each of the
independent variables may have its own tolerance; the goal is to bound the
tolerance of the dependent variable (i.e., what is the tolerance of the value
of the function given the tolerances of the inputs). The next two examples
illustrate this (albeit with a single variable).

Example 2.4.3 Show that if jxj 5 then jx2 + 2x + 1j 36 . By the

2 2
triangle inequality we have jx + 2x + 1j jx j + j2xj + j1j, so we need to
control the …rst two terms. We have j2xj = j2j jxj 10 and jx2 j = jxj2 25.
Putting this all together gives the inequality we needed.

Example 2.4.4 Show that if jx + 1j 3 then jx2 + 3x + 2j 12. If we try

the method of the previous example then we can write
x2 + 3x + 2 x2 + j3xj + 2 (2.3)
To control x2 we apply Lemma 2.4.2 and various order axioms:
jx + 1j 3) 3 x+1 3) 4 x 2) 4 x 4
which leads to jxj 4 and x2 16. This is obviously too big–the remaining
terms the inequality 2.3 will only make it even larger! This illustrates the fact
that one can sometimes “go too far” with the triangle inequality, especially
when there are both negative and positive quantities involved. For example,
when x = 4, x2 = 16 but 3x = 12. So the 12 “cancels” a good bit of the
16, making the value of the function smaller. But when we use the triangle
inequality, we take the absolute value of 3x, so rather than subtracting 12 we
are actually adding it, and our estimate is far too large. So we start over,
observing that jx2 + 3x + 2j = jx + 2j jx + 1j. Now we may more e¤ectively
use the triangle inequality to get
jx + 2j jx + 1j + 1 4
2.4 ABSOLUTE VALUE 37

Combining these we get jx + 2j jx + 1j 12. This estimate is actually the

best possible, since the value of this function at 2 is 12.

Exercise 2.33 Prove that if jxj 2 then jx2 1j 3 jx + 1j.

Exercise 2.34 Suppose that jx 1j 2.

1. Prove that jx3 2x2 + x 2j 10 jx 2j.

2. Prove or disprove jx3 2x2 + x 2j < 10 jx 2j.

Exercise 2.35 Prove or disprove: Suppose jx3 x2 + x + 3j > jx + 1j. Then

jx2 2x + 3j > 1.
Chapter 3

The Integers and Induction

The natural numbers are, in some sense, the “oldest” numbers, since those
are the numbers that we count with. Human beings have given the natural
numbers have been given many names and symbols over the millenia, but
the numbers themselves, regardless of their names, are uniquely determined
by the axioms for the real numbers. Given the task of de…ning the natural
numbers, one might suggest the following. Certainly 1 is a natural number,
so is 1 + 1, which we have named 2. Since we are interested in counting,
we also want to include 1 + 1 + 1, which we have given the name 3, and so
on. Unfortunately, “and so on” is not mathematically precise. In fact, to
make a concept like this precise we need something known as the Principle
of Mathematical Induction, which we will study later. In fact, this principle
depends on the properties of the natural numbers, and we don’t want to
engage in circular reasoning by using properties of the integers to de…ne the
integers. The way to get around this problem (pun unintended) is to de…ne
the natural numbers to be the “smallest”subset of R that contains 1 and is
closed under addition. Being “closed under addition”simply means that the
sum of two natural numbers should again be a natural number. We still need
to make rigorous sense of the notion of “smallest” such set, but this is not
too hard, and doesn’t use the properties of the natural numbers that we are
trying to de…ne. The formal de…nition is given in the …rst section, which is
optional. The proofs in that section involve somewhat specialized methods
that won’t be used later in this text, and the properties of the integers that
are needed in the sequal are summarized at the beginning of Section 3.2. It
is recommended that math majors at some point work through the proofs
in this section to see for once and for all that all of the theorems in this

39
40 CHAPTER 3 THE INTEGERS AND INDUCTION

text really do follow only from the basic axioms for set theory and the real
numbers.

3.1 De…nitions of N and Z (Optional)

The purpose of this section is to de…ne the natural numbers and the inte-
gers, and prove two important theorems about them. The …rst main theo-
rem, called the Well-ordering Principle, is of fundamental importance, and
is equivalent to the Principle of Mathematical Induction that we will study
later. The second main theorem, which will be used constantly without refer-
ring directly to it, is simply the statement that the integers are closed under
addition.

De…nition 3.1.1 A subset X of R is said to be closed under addition if for

all x; y 2 X, x + y 2 X. If X is closed under addition and contains 1 then X
will be called (for lack of a better word) supernatural. The natural numbers
N are de…ned to be the set of all x 2 R such that for any supernatural set X,
x 2 X.
That is, the natural numbers consist of those real numbers that lie in
every supernatural set. This de…nition may seem strange at …rst, but the
next lemma will clarify what N is.

Lemma 3.1.2 N is supernatural, and if A R is any supernatural set then

N A.
Proof. First of all, 1 is by de…nition contained in every supernatural set,
so 1 2 N. To prove that N is closed under addition we need to show that
if x; y 2 N and B is any supernatural subset of R then x + y 2 B. But by
de…nition of N, x; y 2 B, and since B is closed under addition, x + y 2 B.
Now suppose that A R is supernatural. If x 2 N then by de…nition of N,
x 2 A. That is, N A.
This lemma explains the appropriateness of the word “supernatural”(de-
spite its otherworldly connotations): the pre…x “super” refers to something
larger or beyond. For example, in mathematics a “superset” of a set A is a
set B such that A B. The natural numbers are, according to the lemma,
contained in every supernatural set.
3.1 DEFINITIONS OF N AND Z (OPTIONAL) 41

Corollary 3.1.3 If E is a subset of N and E is supernatural then E = N.

That is, N has no proper subset that is supernatural.
Corollary 3.1.3 provides a strategy for proving statements about N. Sup-
pose that one wishes to prove that every element of N has some property
P . De…ne E to be the set of all natural numbers having property P . If one
then shows that E is supernatural then E = N, so every element of N has
property P . We will use this method in the next two lemmas.

Lemma 3.1.4 If n 2 N then n = 1 or n 2. In particular N is bounded

below by 1 and (1; 2) \ N = ?.
Proof. Let E := fn 2 N : n = 1 or n 2g N. If we show that E is
supernatural then N = E by Corollary 3.1.3, and the lemma follows. By
de…nition, 1 2 E. Moreover, if m; n 2 E then m; n 1, so m + n 2. Since
m; n 2 N, m + n 2 N, so m + n 2 E.

Lemma 3.1.5 If n 2 N and n 6= 1 then n 1 2 N.

Proof. Let E := fn 2 N : n = 1 or n 1 2 Ng. As in the previous
proof we need only show E is supernatural. First, 1 2 E by de…nition.
Suppose that m; n 2 E. If m = 1 then (m + n) 1 = n 2 N. If m 6= 1
then by de…nition of E, m 1 2 N. But N is closed under addition and
(m + n) 1 = (m 1) + n 2 N.

Exercise 3.1 Show that if A and B are supernatural subsets of R then A\B
is supernatural.
The proofs of the next statements depend on the Completeness Axiom.
The next theorem is a preliminary version of the Gap Theorem in the special
case of the natural numbers.

Lemma 3.1.6 For all n 2 N, (n; n + 1) \ N = ?.

Proof. Let E := fn 2 N : (n; n + 1) \ N 6= ?g. If the proposition were not
true then E would be nonempty. Since (1; 2) \ N = ?, 1 2 = E and so E is
bounded below by 2. Let i := inf E 2. By Lemma 2.3.8 (using " = 1)
there exist some n 2 E such that n < i + 1. By de…nition of E, there is
some m 2 (n; n + 1) \ N. Since both m; n 2, Lemma 3.1.5 implies both
m 1 and n 1 are in N, and since m 1 2 (n 1; n) \ N, n 1 2 E. But
n 1 < (i + 1) 1 = i, a contradiction.
42 CHAPTER 3 THE INTEGERS AND INDUCTION

Theorem 3.1.7 (Well-ordering Principle) Every non-empty subset of N has

a minimum.
Proof. Let A N be non-empty. Then inf A := i 1. By Lemma
2.3.8 there is some n 2 A such that i n < i + 1. If i = n 2 A then
i is a minimum and we are done. Otherwise, i < n and we may apply
Lemma 2.3.8 with " := n i > 0. So there is some m 2 A such that
i m < i + (n i) = n < i + 1 m + 1. But then m < n < m + 1, which
contradicts Lemma 3.1.6.

De…nition 3.1.8 The integers Z are de…ned to be Z : = f0g [ N [ N.

Exercise 3.2 Prove

1. If n 2 Z then n 2 Z.

2. N = fn 2 Z : n > 0g

The next proposition is deceptively simple to state. The proof is more

di¢ cult than it may seem at …rst because showing that a number is a natural
number is, at this point, not very easy. For example, if m; n 2 N with m > n,
why is it true that m n 2 N? Right now we have only two theorems that
we can use to show that something is a natural number: the fact that N
is supernatural and Lemma 3.1.5. But Lemma 3.1.5 only concerns the case
n = 1, and we can’t directly use the fact that the natural numbers are closed
under addition, since m n = m + ( n) and n is not a natural number.
Our proof will use both Lemma 3.1.5 and the Well-ordering Principle.

Proposition 3.1.9 Z is closed under addition.

Proof. We will …rst show the following Claim 1: if a 2 Z then a 1 2 Z.
If a > 1 then by Lemma 3.1.5, a 1 2 N. If a = 1 then a 1 = 0 2 Z. If
a = 0 then a 1 = 1 2 N. If a < 0 then the only possibility is a 2 N,
so a 2 N and a + 1 2 N. Therefore a 1 = ( a + 1) 2 N.
To prove the proposition we need to show that if m; n 2 Z then m+n 2 Z.
If m = 0 or n = 0 then obviously m + n 2 Z. So we can …nish the proof by
showing that for m; n 2 N, the following combinations are in Z: (1) m + n,
(2) m n , (3) m n, and (4) m + n. The …rst case is simply the fact that
N is closed under addition. For the second case, m n = (m + n) 2 N.
The last two cases are similar, so we will only prove (3) by proving that the
3.2 BASIC PROPERTIES OF THE INTEGERS 43

set A := fn 2 N : m n 2= Zg is empty. If not, by the Well-ordering Principle

A has a minimum k. By Claim 1, 1 2 = A and so k > 1. Since k = min A,
k 12 = A, but by Lemma 3.1.5, k 1 2 N. By de…nition of A, this means
that a := m (k 1) 2 Z. But now Claim 1 implies m k = a 1 2 Z,
which contradicts k 2 A.

Theorem 3.1.10 (Gap Theorem) For all n 2 Z, (n; n + 1) \ Z = ?.

Exercise 3.3 Prove the Gap Theorem. Hint: The case when n > 0 is simply
Lemma 3.1.6. For n = 0, prove it by contradiction using Lemma 3.1.4. Prove
the case n < 0 by contradiction and negating numbers to use the cases already
considered.

3.2 Basic Properties of the Integers

The proofs in this section, and hence all of the remaining theorems in this
text, will use only the following facts from the previous section. Except for
the Well-ordering Principle, we will usually not explictly give reference to
these facts in the remainder of the text.

1. Z = f0g [ N [ N

2. N = fn 2 Z : n > 0g = fn 2 Z : n 1g

3. Both N and Z are closed under addition.

4. The Well-ordering Principle: if A N is non-empty then A has a

minimum.

Throughout most of the world, the integers have been given speci…c names
that facilitate calculation. Probably for no other reason than the fact that
humans normally have ten …ngers on which to count, the most popular system
is what is now known as the decimal system, requiring only ten symbols that,
as you well know, are repeated to represent larger values. One can check using
mathematical induction (which we will study later) that the whole numbers
represented by our decimal system are closed under addition and contain
only numbers that can be obtained by adding 1 to itself some number of
times, and so the results of the previous section show that the numbers that
we represent in this way must be precisely the natural numbers (and together
44 CHAPTER 3 THE INTEGERS AND INDUCTION

with their negatives, the integers). In other words, we have nothing to fear
from a logical standpoint by working with integers as we have always done.
Perhaps more important than the actual base 10 that we use (other cul-
tures have used bases 5, 8, 12, and 20), is the Hindu-Arabic placement system
that allows us to add and multiply numbers with ease. Compare our modern
system, for example, with that of the Romans. While it is possible to add
and multiply Roman numerals, the algorithms (which the Romans may or
may not have used) are exceedingly tedious and render serious algebra vir-
tually impossible–something which could well have contributed to the fact
that science in the Roman Empire was never well-developed.
The next theorem (at least when a > 0) was in e¤ect assumed as an axiom
by the ancient Greeks, who considered it as self-evident. However, the Greeks
also lacked a numerical system that facilitated algebra, and Archimedes (who
was killed by a Roman soldier), would not have stated in such analytical
terms the principle that is now named after him. To the Greeks, positive real
numbers were considered as magnitudes or lengths, while natural numbers
were used for counting. The statment below would be understood in more
concrete, geometric terms: given two (positive!) lengths a and b, if enough
segments of length a are placed end-to-end, then these segments together
would be longer than a segment of length b. From a physical standpoint this
statement seems completely obvious, and it may come as a surprise that there
is no way to prove it mathematically without using the somewhat abstract
Completeness Axiom.

Figure 3.1: Archimedean Principle

Theorem 3.2.1 (Archimedean Principle) For every a; b 2 R such that b > 0

there exists a natural number n such that nb > a.
3.2 BASIC PROPERTIES OF THE INTEGERS 45

Proof. If b > a then we are done, letting n = 1. Otherwise, the set E of all
m 2 N such that mb a contains 1 and is therefore non-empty. In addition,
a
any m 2 E satis…es m b
, and so E is bounded above by ab . Therefore
s := sup E exists. By Lemma 2.3.8 (use " := 1) there exists some m 2 E
such that m > sup E 1. Now n := m + 1 is a natural number that is greater
than sup E, which implies that n 2= E. But by de…nition that means nb > a,
which is what we wanted to prove.

Corollary 3.2.2 The natural numbers are not bounded above. In other
words, for every real number r there is some natural number n such that
n > r.

Proof. Suppose that M were an upper bound for N. By the Archimedian

principle there is some natural number n such that n = n 1 > M , a con-
tradiction. In other words, any r 2 R cannot be an upper bound for N. By
de…nition that means there is some n 2 N such that n > r.
Frequently, beginning mathematics students, if given the problem of prov-
ing that the natural numbers are not bounded above, will attempt to prove
this “obvious”fact without using the completeness axiom. But any attempts
to prove boundedness of the natural numbers without using completeness are
doomed to fail because there exist so-called non-Archimedean ordered …elds,
which satisfy all the real number axioms except completeness. In such a …eld
one may de…ne N in the same way that we did in the previous section, but the
Archimedean principle and unboundedness of the natural numbers are false.
As esoteric as such ordered …elds may seem at …rst, they have proved to be
quite important in advanced areas of mathematics such as number theory.

Example 3.2.3 The Archimedean Princple gives us a way to mathematically

verify the in…ma or suprema of certain sets, which previously we could only
guess at. For example, if A := f nn 1 : n 2 N and n 2g, then we might
well guess, using some calculus, that inf A = 1. To prove it, note that since
n 1 < n, nn 1 > 1 for all n 2 and therefore 1 is a lower bound for A.
Now suppose 1 were not the in…mum of A; that is, there is some other lower
bound m > 1 of A. To get a contradiction we will …nd some nn 1 2 A such
that nn 1 < m () n < mn m () n > mm 1 . Since m > 1, the right side
is positive, and the Archimedean Principle (or the fact that N is not bounded
above) tells us that there exists some n such that n > mm 1 > 1, and hence
that nn 1 < m.
46 CHAPTER 3 THE INTEGERS AND INDUCTION

1
Exercise 3.4 Let A := 1 n2
: n 2 N . Find sup A and inf A and prove
that your answer is correct.

Exercise 3.5 Let A R be non-empty and bounded above. Prove that s =

sup A if and only if s is an upper bound of of A and for every n 2 N there
exists some x 2 A such that x > s n1 .

Theorem 3.2.4 (Well-ordering Principle for the Integers) If A is a non-

empty subset of Z that is bounded below (resp. above), then A has a minimum
(resp. maximum).
Proof. We will only prove the case for the minimum; the other statement is
similar. Let M be a lower bound for A. If M is a positive lower bound then
we are …nished by the Well-ordering Principle, since in that case A N.
Suppose M 0. The strategy is to “shift” A by adding a large enough
natural number n to the elements of A, to get a new set B N. We then
apply the Well-ordering Principle and “shift” the resulting minimum back
by subtracting n. Here are the details: By the previous corollary there is
some n 2 N such that n > M ; so n < M is a lower bound for A. De…ne
B := fm + n : m 2 Ag Z. For any k 2 B, k = m + n for some m 2 A,
and therefore k M + n. that is, M + n > 0 is a lower bound for B and
B N. The Well-ordering Principle implies that B has a minimum K 2 B.
By de…nition, K n 2 A and similar to what we proved above, K n is a
lower bound of A. According to Exercise 2.19, K n is the minimum of A.

The next corollary is kind of a counterpoint to the “Gap Theorem”proved

in the last section, which states that there are no integers between n and n+1
when n is an integer. This tells you, in a sense, how “sparse”the integers are.
The corollary below says, on the other hand, that when two real numbers are
separated by a length of more than 1 then there must be in integer somewhere
between them.

Corollary 3.2.5 If a; b 2 R satisfy b > a + 1 then there is an integer n such

that a n < b.
Proof. Let E := fm 2 Z : m ag. Since the integers are not bounded
above, E is nonempty. Moreover, a is a lower bound of E and hence E has
a minimum M 2 E Z by Theorem 3.2.4. We have a M since M 2 E.
Now suppose that M > a + 1. Then M 1 2 Z and M 1 > a + 1 1 = a,
which implies M 1 2 E, a contradiction. That is, M a + 1 < b.
3.2 BASIC PROPERTIES OF THE INTEGERS 47

Theorem 3.2.6 (Principle of Induction) Let fP (n)g be a collection of state-

ments for all n 2 N such that

1. P (1) is true and

2. for every n 2 N, if P (n) is true then P (n + 1) is true,

then P (n) is true for all n.

Proof. Suppose P (n) is not true for some n. Let A := fn 2 N : P (n) is
not trueg. Then A is non-empty and hence by the Well-ordering Principle
A has a minimum m. This means m 2 A, so m 2 N and P (m) is not true.
Moreover, since P (1) is true, m > 1 (according to the second property at the
beginning of this section). That is, m 1 is a positive integer, hence a natural
number, and m 1 2 = A. By de…nition of A, P (m 1) is true. But then by
the second assumption of this theorem, P (m) is true, a contradiction.
Proofs that use the Principle of Induction are known as inductive proofs,
and they may be used in a great variety of situations. Assumption 1 of the
theorem is often called the base case, and Assumption 2 is often called the
inductive step. The inductive step involves assuming P (n), which is called
the inductive hypothesis, and using it to prove P (n + 1). The inductive step
may seem to be a strange thing to have to prove, but here is an analogy
that illustrates how it works. Suppose that there is a ladder that is in…nitely
long. If you know that you can reach the …rst rung of the ladder, and you
know that if you are on any particular rung then you can always reach the
next rung, then you can climb to any rung. The proof, in these terms, is
essentially this: If there were some rung you couldn’t reach then there would
be a …rst rung that you couldn’t reach. That …rst unreachable rung is not
the …rst rung, so there is one below it that, by de…nition is reachable. But
then by assumption you could reach the supposedly unreachable rung.
Our …rst application will be to prove that the integers are closed under
multiplication:

Theorem 3.2.7 If m; n 2 Z (resp. N) then mn 2 Z (resp. N).

Proof. We will …rst suppose that n 2 N and prove the theorem by induction.
For this proof we will let P (n) be the statement that mn 2 Z. P (1) is the
statement m 1 2 Z, which is true since m 2 Z. Now suppose that P (n)
is true, that is, mn 2 Z. Then P (n + 1) is the statement m(n + 1) 2 Z.
48 CHAPTER 3 THE INTEGERS AND INDUCTION

But m(n + 1) = mn + m 2 Z by the inductive hypothesis and the fact that

Z is closed under addition. This …nishes the proof when n 2 N. If n = 0
then mn = 0 2 Z. If n < 0 then n 2 N and by what we already proved,
m( n) 2 Z. But then mn = (m( n)) 2 Z. Finally, if both m and n
happen to be natural numbers then mn is positive, hence a natural number.

We will next address integer powers of real numbers. We do this via a

method of iterated de…nition that is closely related to induction. For any real
number a we de…ne a1 = a, and in general we de…ne an+1 = an a. It follows
from the Principle of Induction that in this way we have de…ned an for every
natural number n. We can now check the powers rule: We proceed by …xing
m and doing induction in n. If n = 1 then by our iterative de…nition

am an = am a1 = am a = am+1 = am+n .

Now suppose that the statement is true for some n 1. Then

am an+1 = am an a = am+n a = am+n+1 = am+(n+1) .

For the remaining integer powers we need to assume that a 6= 0. We then

de…ne a0 = 1 and an = a 1 n for n < 0. We need to be a little careful since now
we have two potential meanings for a 1 , namely the multiplicative inverse of
a and what we have just de…ned. But note that our new de…nition says that
a 1 = a (1 1) = a1 , which is our alternative expression for the multiplicative
inverse of a. Moreover we have the following:
n 1
Exercise 3.6 Prove that for a 6= 0 and n 2 N, a = an
.

Theorem 3.2.8 Let m; n 2 Z and a 6= 0. Then am an = am+n .

Proof. We have already checked the case when m and n are natural numbers.
The remaining possibilities must be checked individually. If m = 0 then

am an = a0 an = 1 an = an = a0+n = am+n

and n = 0 is similar. If both m and n are negative then we have

1 1 1 1
am an = m n
= ma n
= (m+n)
= am+n .
a a a a
For opposite signs we might as well take n < 0 and m > 0. If m + n = 0 then
m = n and the statement becomes a n an = a0 = 1, which is just Exercise
3.2 BASIC PROPERTIES OF THE INTEGERS 49

3.6. If m + n > 0 then m is the sum of positive numbers m + n and n, so

the case considered above (both positive powers) and Exercise 3.6 give

am an = am+n a n n
a = am+n .

The case when m + n < 0 is an exercise.

Exercise 3.7 Finish the last case of Theorem 3.2.8.

Corollary 3.2.9 Let m; n 2 Z and a be a non-zero real number. Then

(am )n = amn .

Exercise 3.8 Prove the above Corollary. Hint: Start with the case when n
is a natural number.
At this point we are faced with the task of verifying many statements
that are true but will be very tedious to check. For example, if a > 0 then
an > 0 for all n 2 Z. Or if a; b 6= 0 then (ab)n = an bn for all n 2 Z. Or
the generalized distributive law: a(b1 + + bn ) = ab1 + + abn . Or if
b1 ; :::; bn > 0 then b1 + +bn > 0, and so on... All of these statements simply
extend axioms and theorems that were stated for just two numbers, to any
n numbers. For example, the statement that if a > 0 then an > 0 is simply
an extension of the multiplicative law for inequalities. The proofs of these
statements are all basic proofs by induction that involve no serious new ideas
beyond what are used in the exercises and examples in this section, and you
will no doubt be relieved to know that we have no intention of going through
them all. From now on we will take all such statements without additional
proof.
We conclude this section with the formal de…nition of the set of rational
numbers, Q, and some of its properties.

De…nition 3.2.10 The rational numbers Q consist of all real numbers of

the form pq , where p; q 2 Z and q 6= 0.

Exercise 3.9 Prove that Q is closed under addition and multiplication. Hint:
If you use induction for anything then you are working too hard!

Exercise 3.10 (Density of Rationals) Prove that for any two real numbers
r1 < r2 there exits a rational number pq such that r1 < pq < r2 , using the
following steps.
50 CHAPTER 3 THE INTEGERS AND INDUCTION

1. Show that there exists some q 2 N such that q(r2 r1 ) > 2.

2. Show that there exists some p 2 Z such that qr1 < qr1 + 1 p < qr2 ,
and …nish the proof.

3.3 Applications of Induction

Induction has many applications in both pure and applied mathematics. In
particular, induction is heavily used in computer science. Here is an example
of an inductive proof, made famous by the story that the mathematician
Gauss, as a schoolboy, used the resulting equation to make short work of the
assignment of a tyrannical schoolmaster: to add the numbers from one to
100.
Pn n(n+1)
Example 3.3.1 We will prove that for all n 2 N, i=1 i = 2
. The
P1 1(1+1)
base case is simply i=1 i = 2 , which is equivalent to 1 = 1 and hence
P
true. To show the inductive hypothesis we must assume that ni=1 i = n(n+1) 2
P
is true and use this equation to prove that n+1 i=1 i = (n+1)(n+2)
2
is true. Often
the best strategy with a summation of this sort is to start with the summation,
split o¤ the last term, substitute using the inductive hypothesis, and do some
algebra to obtain the other side of the equation. In this case we have

X
n+1 X
n
n(n + 1) n2 + n + 2n + 2 (n + 1)(n + 2)
i= i+(n+1) = +(n+1) = =
i=1 i=1
2 2 2

Pn
The formula (n+1)(n+2)
2
is called the closed form of the sum i=1 i. The
advantage of the closed form is clear from Gauss’s tale. Even in modern
times, from the standpoint of computing, it is obviously advantageous to be
able to compute the sum of a large collection of numbers using the closed
form rather than using a large number of iterated sums.
P
Exercise 3.11 Prove that ni=1 i2 = n(n+1)(2n+1)
6
for all natural numbers n.
Hint: To save time and trouble, at an appropriate point factor out (n + 1).

Example 3.3.2 Sometimes you can use existing formulas to avoid using in-
duction. For example, using the previous exercise, along with the distributive
3.3 APPLICATIONS OF INDUCTION 51

and associative laws:

X
n X
n X
n
n(n + 1)(2n + 1)
2 2
2i 1 =2 i 1= n
k=1 k=1 k=1
3

Example 3.3.3 We will prove that n 2n for all natural numbers n. For
n = 1 we have 1 21 . For the inductive step, suppose that n 2n . Then
n n n n n+1
n+1 2 +1 2 +2 = 2 2 = 2 . The …rst inequality uses the inductive
hypothesis, and the second uses the fact that 1 2n for all n, which we will
now prove, also by induction. The base case is 1 2. Suppose that 1 2n .
Then 2n+1 = 2n + 2n 1 + 2n > 1, since 2n > 0.
The Principle of Induction has closely related forms that are also useful.
For example, there is no reason why the base case needs to be n = 1. Suppose
that we replace Condition 1 with Condition 10 that P (n0 ) is true for some
integer n0 , and assume Condition 20 : for every natural number n N , if
P (n) is true then P (n + 1) is true. Then it follows from essentially the same
proof that P (n) is true for all n n0 . Another variation is the so-called
Principle of Strong Induction, in which the inductive step becomes: if P (k)
is true for all k n then P (n + 1) is true. The proof is nearly the same as
the proof of the regular Principle of Induction.
We will use strong induction later. Induction can also be run backwards
and/or with skips–for example when proving that a statement is true for all
even natural numbers rather than all natural numbers. In the latter case the
inductive step is to show that if P (n) is true for some even n then P (n + 2) is
true. Again, the proof is similar to that of the original Principle of Induction.

Exercise 3.12 Prove that n2 2n for all natural numbers n except n = 3.

P
n
Exercise 3.13 Prove that (2k + 1) n3 for all natural numbers n 2
k=1
in two di¤erent ways: one way directly using induction and the other using
Example 3.3.1.
We will next consider the very important Binomial Theorem. Recall that
n
k
:= k!(nn! k)! , where n! may be de…ned iteratively as follows: 0! := 1, and
for any n 0, (n + 1)! = n!(n + 1). The quantity nk is called the “choose
function”, and is spoken as “n choose k”. It is de…ned for non-negative
integers n and k when 0 k n. The name refers to the fact that it
52 CHAPTER 3 THE INTEGERS AND INDUCTION

represents the number of possible ways to choose k socks from among n

socks, something that is normally encountered in an elementary course in
probability. The choose function satis…es the following equation
n+1 n n
= + . (3.1)
k k 1 k
In fact,
n n n! n!
+ = +
k 1 k (k 1)!(n + 1 k)! k!(n k)!

kn! n!(n + 1 k)
= +
k(k 1)!(n + 1 k)! k!(n k)!(n + 1 k)
n!k + n!(n + 1 k) n+1
= =
k!(n + 1 k)! k

Exercise 3.14 Prove 2n < n! for all natural numbers n 4.

n!
Exercise 3.15 Prove that nk (n k)!
for all 0 k n. Hint: Simplify the
right side and compare terms.
Equation (3.1) is also the basis for the construction of Pascal’s triangle.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

One starts with a 1 at the top, and each row begins and ends with a 1. An
entry in a given row is obtained by adding the entries above, and to the left
and right of, the given entry. If one starts counting with row 0 at the top,
3.3 APPLICATIONS OF INDUCTION 53

and the left most slot in each row is slot 0, then according to Formula 3.1, the
k th slot in the nth row is nk . According to the Binomial Theorem, proved
next, the rows in Pascal’s triangle allow one to read o¤ the coe¢ cients of a
binomial. For example, (a + b)3 = 1 a3 + 3 a2 b + 3 ab2 + 1 b3 .

Theorem 3.3.4 (Binomial Theorem) For all a; b 2 R and n 2 N,

n
Xn
n k n k
(a + b) = a b
k=0
k
Proof. The proof is by induction in n. This base case is easily checked.
Suppose that the formula holds for some n. Then
!
Xn
n
(a + b)n+1 = (a + b)n (a + b) = ak bn k (a + b)
k=0
k
Xn
n k+1 n Xn
n k n
k k+1
= a b + a b
k=0
k k=0
k
In order to combine these sums (using the distributive law) we need to have
matching powers of a and b for the same value of k in each sum. This is
accomplished using an “index shift” in the …rst sum, essentially replacing k
by k 1. Since k originally went from 0 to n, we accomplish the same thing
with k 1 by letting k go from 1 to n + 1. Another way to work this out
is using a “substitution”not unlike substitution that was learned concerning
integration. Start by letting m = k+1, so k = m 1. Now make substitutions
in the entire …rst sum, including the limits of the sum (remember changing
the limits of integration when doing substitution
Pn+1 nin amde…nite integral?).
n (m 1)
After making all the replacements we get m=1 m 1 a b . Now the
variable m is just a counting variable–we can replace it by k if we wish
(remember the idea of “dummy variable”from integration?). That is,
Xn
n k+1 n X
n+1
n
k
a b = ak b n (k 1)
.
k=0
k k=1
k 1
Now to get the starting and ending values of k to match in both sums we
separate out the k = n + 1 term of the new …rst sum and the k = 0 term of
the second sum. This leaves us with
Xn
n Xn
n k n k+1
n+1 n+1 k n+1 k
(a + b) =a + a b + a b + bn+1
k=1
k 1 k=1
k
54 CHAPTER 3 THE INTEGERS AND INDUCTION

X
n
n n
= an+1 + + ak b n k+1
+ bn+1
k=1
k 1 k

X
n
n+1 X
n+1
n+1 k n
n+1 k n k+1 n+1 k+1
=a + a b +b = a b
k=1
k k=0
k

by Equation (3.1). This completes the inductive step and the proof.
Note that if a and b are non-negative then each of the terms in the right
side of the binomial equation is also non-negative. In particular, one can
obtain many useful inequalities by “throwing away”some of these terms.

Example 3.3.5 If a; b 0 and n 2 then (a + b)n = an + nan 1 b +

nP2
n k
k
a b k an + nan 1 b. In e¤ect we are “throwing away” all terms but
k=0
the last two; all of those terms are non-negative because a and b are non-
negative, and the choose function is always positive. Note that if a; b > 0 we
get (a + b)n > an + nan 1 b for n 2, since all of the terms that are thrown
away are positive. However, this inequality is not true for n = 1; in fact in
this case (a + b)n = a + b = an + nan 1 b. This point illustrates that one must
be careful when throwing away terms in the Binomial Theorem–one must be
sure that n is large enough that those terms actually exist!

Example 3.3.6 One can also sometimes use clever choices of a and b to get
equations P
and inequalities. For example, by letting a = b = 1 one obtains
that 2 = nk=0 nk .
n

Exercise 3.16 Prove that for all natural numbers n, 2n + 3n 5n in two

di¤erent ways: one way using the Binomial Theorem, and the other way
without using the Binomial Theorem.

Exercise 3.17 Prove that for all natural numbers n and a > 0, (a + 1)n
an + n(n 1)(n
6
2) n 3
a . For which n may one replace the “ ” by “>”?

Exercise 3.18 Prove that n! nn for all n 2 N. Hint: Prove it by induction

and use the Binomial Theorem in the inductive step.
3.4 DIVISIBILITY 55

3.4 Divisibility
An integer a is said to divide an integer b if b = ac for some integer c. We
write a j b. We also say that an integer b is divisible by a and a is a divisor
or factor of b. For example, an integer is even, by de…nition, if it is divisible
by 2. If a j b and a is positive and not equal to 1 or b then a is said to be
a proper divisor of b. If c divides both a and b then c is said to be a common
divisor of a and b.

Exercise 3.19 Prove the following:

1. 1 divides every integer.

2. Every integer divides itself and 0:

3. 0 only divides 0.

4. If a and b are integers and a j b then aj b.

Lemma 3.4.1 Suppose a; b 2 N and a j b. Then a b and if a is a proper

divisor, a < b.
Proof. We may write b = ac for some integer c, which, since b and a are
positive, must be a natural number. Since c 1, b a. If a is a proper
divisor then a 6= b, so c > 1, so b > a.

Corollary 3.4.2 If a and b are integers, a j b and b j a then a = b.

Proof. If either a or b is 0 then both must be 0 by Exercise 3.19. If a; b 2 N
then by Lemma 3.4.1 a b and b a, so a = b. If a < 0 and b > 0 then
a j b and b j a and we are done by the previous case. The other cases are
similar.
Since we have already observed that 1 divides any integer we have:

Corollary 3.4.3 The only integers that divide 1 are 1.

Exercise 3.20 Prove that if a; b; c 2 Z, a j b and a j c then a j (mb + nc) for

any integers m; n.

De…nition 3.4.4 For any a 2 Z, let aZ := fn 2 Z : a j ng.

56 CHAPTER 3 THE INTEGERS AND INDUCTION

Note that by de…nition aZ = fn 2 Z : n = ka for some k 2 Zg. Put

another way, aZ is obtained by multiplying every integer by the number
a, which helps explain the notation. For example, 0Z = f0g, 1Z = Z and
2Z = f:::; 4; 2; 0; 2; 4; :::g. As is traditional, we will refer to 2Z as the set
of even integers.

Lemma 3.4.5 For any a 2 Z, aZ is closed under addition and multiplica-

tion. In particular, the sum and product of even integers is even.

Proof. Let x; y 2 aZ. By de…nition, x = am and y = an for some integers

m; n. Then x + y = am + an = a(m + n). Since m + n 2 Z, by de…nition
x + y 2 aZ. Moreover, xy = aman = a(man), and since man 2 Z, xy 2 aZ.

Remark 3.4.6 Beginning students often attempt to do proofs involving di-

visibility by dividing. That is, they use implicitly the following “de…nition”
of divisibility: a j b if and only if ab is an integer (this is equivalent only when
a 6= 0, which also leads to additional special cases when using this de…nition).
This strategy is always a mistake–not because it can’t work, but because it is
almost always more complicated (needlessly so), and generally leads to er-
rors. For example, let’s start a proof using this method that aZ is closed
under multiplication when a 6= 0. Let x; y 2 aZ. Then xa and ay are integers.
To …nish, we need to show that xy a
is an integer. Many students don’t bother
to do this, which is incorrect, and when pressed about it, don’t know what
to do because there is no a2 in the denominator. With a little thought you
should be able to …gure out what to do, but as a general rule: dividing never
makes these proofs any easier, so if you …nd yourself doing it, go back and
use the proper de…nition.

Exercise 3.21 Show that if x 2 aZ then x 2 aZ.

Exercise 3.22 Let a; b 2 Z. Show that a j b if and only if bZ aZ.

De…nition 3.4.7 An integer m 2 Z is called odd if m = 2k + 1 for some

k 2 Z.

Proposition 3.4.8 If m is an integer then m is either even or odd (never

both).
3.4 DIVISIBILITY 57

Proof. We will …rst show by induction that every natural number is even
or odd. Note that 1 = 2 0 + 1 is odd. Now suppose n is even or odd. If n
is even then n = 2k with k 2 Z. By de…nition, n + 1 = 2k + 1 is odd. If n
is odd then n = 2m + 1 with m 2 Z. But then n + 1 = 2m + 2 = 2(m + 1),
which is even since m + 1 2 Z. Now 0 = 2 0 is even. If m 2 N then
m 2 N, which means m is even or odd. If m = 2k + 1 for some k 2 Z
then m = 2( k 1) + 1 is odd by de…nition. If m is even then the proof
is similar. Finally, suppose that m 2 Z were both even and odd. This
would mean that for some k; n 2 Z, 2k + 1 = m = 2n. This implies that
1 = 2(n k), i.e. 2 j 1, which contradicts Corollary 3.4.3.

Exercise 3.23 Prove that every natural number is odd or even using the
Well-ordering Principle instead of induction. Hint: If some natural number
were neither odd nor even then the set of all such numbers would not be
empty.

Exercise 3.24 Prove that the product of odd numbers is odd and the sum of
odd numbers is even.

Exercise 3.25 Prove by contradiction that if a2 is even then a is even.

Exercise 3.26 Prove that 2n + 1 is divisible by 3 for all odd integers n 1

using two methods of induction:

1. Write n = 2k + 1 and do induction starting with k = 0.

2. For the inductive step show that if the statement is true for some n 1
then it is true for n + 2 (rather than n + 1).

Exercise 3.27 Prove that the sum of any k consecutive odd integers is divis-
ible by k. Hint: You may avoid induction in the following way: Write the …rst
odd number as 2(m + 1) + 1 for some m 2 Z, the second as 2(m + 2) + 1, and
so on. Now express this as a summation from 1 to k and use the distributive
and other laws, plus Exercise 3.3.1.
By now you know that every pair of natural numbers has a greatest
common divisor, and probably found the GCD of speci…c numbers in early
math classes by …rst …guring out the prime factorization of the two numbers.
What likely was not learned in elementary math classes was that the greatest
common divisor of a and b has the form d = am + bn, where m and n are
58 CHAPTER 3 THE INTEGERS AND INDUCTION

integers. At …rst it might not seem at all obvious that there is any common
divisor of this form, or that a number in this form should have anything to
do with divisibility.

Theorem 3.4.9 (Greatest Common Divisor) If a and b are integers then

there is a common divisor d of a and b that has the following properties:

1. d = am + bn, where m and n are integers,

2. d is non-negative,

3. every common divisor of a and b divides d, and

4. if c is a common divisor of a and b then c d.

The divisor d is called the greatest common divisor of a and b, denoted

GCD(a; b).

Proof. We will only consider the case a; b 0; the other cases are an exercise.
We may also assume a b. If a = 0 then we may take d := b = a 0 + b 1,
since b divides both b and 0 = a. Let k := a + b; we will prove the …rst part
by strong induction in k. If k = 0 then a = 0, a case checked above. Suppose
the theorem has been proved for all i such that 0 i k, and let 0 a b
satisfy a+b = k +1. Again, the case when a = 0 is proved so we may suppose
a 1. Consider the two non-negative integers a and c := b a. We have
a + c = b = k + 1 a k since a 1. By the strong inductive hypothesis
there is some d = ar + (b a)n with r; n 2 Z that is a common divisor of a
and b a. Since d divides a and b a, it also divides b = a + (b a) (Exercise
3.20). So d is a common divisor of a and b, and is of the form d = am + bn
with m = r n 2 Z. It is possible that d is negative, but note that since
d is a common divisor of a and b, so is d. Since d = a( m) + b( n),
by replacing d by d if d < 0, we can be sure that d is non-negative. The
third part follows from the …rst part and Exercise 3.20. Finally, if a common
divisor c is non-positive, c d because d is non-negative. If c is positive then
c d by Lemma 3.4.1.

Exercise 3.28 Prove the remaining cases in the above proof. Hint: Don’t
redo the entire proof; use the case a; b 0 that was proved.
3.5 PRIME FACTORIZATION 59

Corollary 3.4.10 Let r 6= 0 be a rational number. Then r = m n

where m
and n are integers having greatest common divisor 1. Such a fraction is said
to be in reduced form.
Proof. Since r is rational, r = ab where a; b 2 Z are nonzero. Now let
d = GCD(a; b). So a = md and b = nd where a; b; d are integers with
r = ab = md
nd
= mn
. Now GCD(m; n) = 1, since otherwise we could write
m = ck and n = jk where c; j; k are integers with k > 1. That in turn would
mean that kd is a common divisor of both a and b, but kd does not divide d
by Corollary 3.4.2 (since k > 1), a contradiction.
We conclude this section with a theorem that was promised in the last
chapter, which we are …nally ready to prove.
p
Theorem 3.4.11 2 is not rational.
Proof. Suppose not–that is, there is some rational r > 0 such that r2 = 2.
2
We may assume r = ab where GCD(a; b) = 1. Then ab2 = 2 ) a2 = 2b2 .
Therefore a2 is even. By Exercise 3.25, a is even. We write a = 2k, where k is
an integer. Then we have 4k 2 = a2 = 2b2 ) b2 = 2k 2 . By the same argument
b is even. But then a and b have a common divisor of 2, a contradiction.

3.5 Prime Factorization

The study of primes and divisibility goes back more than 2000 years, at least
to the ancient Greeks (and perhaps the ancient Egyptians), who managed
to study these concepts without having a well-developed system of algebra.
As mentioned earlier, numbers were considered as magnitudes and not as
quantities that could be abstractly added and multiplied. The lack of alge-
bra severely limited the ancient Greek mathematicians; it is remarkable that
they accomplished as much as they did in number theory using essentially
geometric concepts. The symbiotic relationship between algebra and geom-
etry that these ancient mathematicians unknowingly pioneered persists to
this day. For example, the ancient Greek geometric problems of trisecting
an angle, squaring the circle, and doubling a cube using only a compass and
straightedge were only solved in the nineteenth century after being trans-
lated into algebraic problems that could be solved using methods from the
theory of …elds. In the other direction, the seventeenth century number the-
ory problem known as Fermat’s Last Theorem (that xn + y n = z n has no
60 CHAPTER 3 THE INTEGERS AND INDUCTION

integer solutions for n 3) was only solved in the late twentieth century by
Andrew Wiles using, in part, methods from hyperbolic geometry.
The next theorem is simply a formalization (and extension to real num-
bers) of what happens when one does long division–dividing one number a
by a divisor d to obtain the quotient q with remainder r smaller than the
divisor d. Despite the name, the Division Algorithm is not really an algo-
rithm (which would provide concrete steps for …nding q and r) but rather an
existence and uniqueness theorem.
The Division Algorithm can be considered as a re…nement of the Achime-
dian Principle. Recalling the viewpoint of the ancient Greeks, the Archime-
dian Principle means that for positive lengths d and a, there is some n 2 N
such that if n segments of length d are placed end to end, their length will
surpass that of a. The Division Algorithm then takes the largest number q
of segements of length d that do not surpass a. So qd is not longer than than
a, but adding one more segment of length d goes past a. That means the
di¤erence r := a qd is less than d. The proof simply makes this argument
precise, while allowing the possibility that a and/or d might not be positive.
The theorem also includes the very important assertion of uniqueness of r
and q.

Figure 3.2: Division Algorithm

Theorem 3.5.1 (Division Algorithm) If a and d 6= 0 are real numbers then

there exist a unique integer q and a unique real number r such that 0 r < jdj
and a = qd + r. Moreover, if a and d are integers then r is a non-negative
integer, and d divides a if and only if r = 0.
Proof. Consider the set E := fm 2 Z : m jdj ag. Then E is bounded
a
above by jdj . By the Archimedean Principle there is an n 2 N such that
n jdj a and hence n jdj a, so n 2 E 6= ?. By Theorem 3.2.4, E has
3.5 PRIME FACTORIZATION 61

a maximum w 2 E; i.e., w jdj a. Let r := a w jdj 0. Now w + 1 2 = E,

so (w + 1) jdj > a ) r := a w jdj < jdj. We have a = w jdj + r, so to …nish
existence we need only let q := w when d > 0 or q := w when d < 0. For
uniqueness, suppose we have q 0 and r0 with 0 r0 < jdj and q 0 d + r0 = a. We
may suppose that r > r0 , and hence 0 < r r0 < jdj. Since q 0 d + r0 = qd + r
we have r r0 = d(q 0 q). This means that d, and hence jdj, divide r r0 .
But this is impossible by Lemma 3.4.1. So r = r0 . We then have q 0 d = qd
and since d 6= 0 we may conclude that q 0 = q. The …nal statement is just
a consequence of the fact that r = a qd, and the integers are closed with
respect to addition and multiplication.

Exercise 3.29 Use the Division Algorithm to give another (much shorter)
proof that every integer is either even or odd (never both). What is the
corresponding statement concerning divisibility by 3?

Exercise 3.30 Show that in the Division Algorithm, if a > 0 then r a.

Hint: What happens if d a?

Exercise 3.31 Prove that if a; b > 1 are natural numbers then ab + 1 is not
divisible by a or b.
A natural number p is called prime if p > 1 and p has no proper divisors.
For example, 2 is prime, by Lemma 3.4.1, and obviously is the only even
prime. Likewise 3 is prime since the only possible proper divisor of 3 is 2,
and 2 2 = 4 > 3. Clearly 4 is not prime. The fact that 5 is prime may
be checked by simply trying all possible products of 2; 3; 4. In fact, checking
whether a given number is prime is always a …nite process, but even though
there are more e¢ cient ways of …nding factors than simply checking all the
possibilities, for large numbers this process can take a long time. Since
primes play a signi…cant role in coding theory, it is important to develop
fast methods of …nding large primes. These days, such algorithms lie in the
province of computer science.
The most basic theorem concerning primes is also taught in elementary
school: that every natural number is uniquely a product of prime numbers.
We will …rst show that any integer greater than one is a product of primes
(including the case when the number itself is prime–i.e. it is a “product”
of one prime), using strong induction. We have already observed that 2 is
prime. Suppose that we have shown that for all k such that 2 k n, k is
a product of primes. Either n + 1 is prime, in which case we are …nished, or
62 CHAPTER 3 THE INTEGERS AND INDUCTION

it is not. If n + 1 is not prime then we may write n + 1 = ab, where a; b are

non-negative integers, neither of which is 1 or n + 1. According to Lemma
3.4.1, we must have that both a and b are less than n + 1, hence less than
or equal to n. We may now apply the (strong) inductive hypothesis to write
a = p1 pm and b = q1 qd , where each pi and qi is a prime. But then
n + 1 = ab = p1 p m q1 qd is a product of primes.
What is more di¢ cult to prove is that this factorization is unique.

De…nition 3.5.2 For a natural number a 2, a prime factorization of a is

a product p1 pk = a such that each pi is prime and p1 p2 pk .
Given any natural number a 2, we have already shown that we may
write a = p1 pk , where each pk is prime. Initially it is possible that
these primes are not in increasing order, but through …nitely many steps we
may re-order them to obtain a prime factorization. (If you really want to be
thorough, prove it by induction!) The purpose of ordering the primes in this
way is to allow us to state a uniqueness theorem for writing a natural number
as a product of primes. For example, we may write 6 = 2 3, or 6 = 3 2.
In some sense these products are “di¤erent”, but not in an interesting way.
Only the …rst one satis…es our de…nition of prime factorization, and it is the
only way to write 6 as a product of primes in increasing order. As we will
see below, ordering the primes in this way also helps to organize proofs. The
next theorem is sometimes called the Fundamental Theorem of Arithmetic.

Theorem 3.5.3 (Unique Factorization Theorem) Every natural number a

2 has a unique prime factorization.
Proof. We have already shown that every natural number has some prime
factorization (once we have re-ordered the primes!). If uniqueness is false
then by the Well-ordering Principle there is a smallest a 2 such that
a = p1 pk = q1 qn , pi pi+1 , qi qi+1 for all i, each pi and qi is prime,
and pi 6= qi for some i. In fact, p1 6= q1 , since otherwise p2 pn = q2 qn < a
would not have a unique prime factorization, a contradiction. By switching
letters if necessary we may assume p1 < q1 qi so p1 6= qi for all i. By the
Division Algorithm we may write q1 = qp1 + r, where 0 r < p1 and (since
0 < p1 < q1 ), q is a natural number. Moreover, since p1 and q1 are integers,
so is r, and since q1 is prime, r 6= 0. We have
q1 rq2 qn
p2 pk = q n = q q2 qn +
p1 p1
3.5 PRIME FACTORIZATION 63

where
rq2 qn
m := = p2 pk q q2 qn
p1
is an integer, hence (because r > 0), a natural number. Let w := p1 m =
rq2 qn 2 N. Since r < p1 < q1 , w < q1 q2 qn = a. We can write one prime
factorization for w by replacing m by its prime factorization in p1 m. This
prime factorization of w contains p1 . On the other hand, we can replace r by
its prime factorization in rq2 qn . But p1 doesn’t divide r since r < p1 , and
p1 6= qi for all i. So this other prime factorization of w doesn’t contain p1 .
That is, w < a does not have a unique prime factorization, a contradiction.

Corollary 3.5.4 If a 2 N and p is a prime such that p j a then the prime

factorization of a contains p as one of its factors.
Proof. Since p j a we may write a = pn, where n 2 N. If n = 1 then a = p
is the prime factorization of a. If n 2 then n has a prime factorization
n = p1 pk . Now a = pn = pp1 pk , and re-ordering the factors (putting p
in its proper place if p > p1 ) must be the unique prime factorization of a.

Corollary 3.5.5 If a; b 2 N and a; b 2 then the factors in the prime

factorization of ab consist of precisely one prime for each prime in the prime
factorizations of a and b.
Proof. Given the prime factorizations a = p1 pk and b = q1 qn , ab must
have as its unique prime factorization a re-ordering of ab = p1 pk q 1 qn .

Corollary 3.5.6 Suppose that p 2 N, p 2. Then p is prime if and only if

and p has the following property: If a; b 2 N and p j ab then p j a or p j b. In
particular, if p j a2 then p j a.

Exercise 3.32 Prove the above corollary. Hint: for one implication prove
that p is prime by contradiction.
p
Exercise 3.33p Prove that if a 2 N then either
p m
a 2 N (i.e. a is a “perfect
square”) or a is irrational. Hint: Assume a = n in reduced form, suppose
p
n > 1, let q be a prime number that divides n, and modify the proof that 2
is irrational.
Chapter 4

Additional Topics

4.1 One-to-one and onto functions

De…nition 4.1.1 A function f : X ! Y is called one-to-one (or 1-1, or an
injection) provided the following holds: If f (x) = f (y) for some x; y 2 X
then x = y. The function f is called onto (or a surjection) if for every
y 2 Y there exists some x 2 X such that y = f (x), i.e. if Y is the range of
X. A function that is both 1-1 and onto is called a bijection (or one-to-one
correspondence).

Exercise 4.1 Translate the de…nitions of 1-1 and onto into the notation for
a function as a set of ordered pairs, as in De…nition 1.3.1.

Exercise 4.2 Completely negate the following statement: The function f :

X ! Y is a bijection.

Lemma 4.1.2 If f : X ! Y is a function then f is onto if and only if

f (X) = Y .

Proof. Suppose that f is onto. By de…nition it is always true that f (X) Y ,

so we need to prove that Y f (X). Let y 2 Y . Since f is onto there is
some x 2 X such that f (x) = y. But by de…nition y 2 f (X).
Now suppose that f (X) = Y . To show that f is onto we let y 2 Y .
Since Y = f (X), y 2 f (X). By de…nition there exists some x 2 X such that
f (x) = y. But this is precisely what we needed to show to prove f is onto.

65
66 CHAPTER 4 ADDITIONAL TOPICS

Lemma 4.1.3 If f : X ! Y is 1-1 then f (A \ B) = f (A) \ f (B).

Proof. Recall that in Example 1.3.4 we showed that f (A\B) f (A)\f (B),
and gave a false proof of the opposite inclusion, which is not true in general.
Now that f is assumed to be 1-1, we can now “repair”this false proof. Let’s
continue from the word “Likewise” in the Example 1.3.4: Likewise there is
some z 2 B such that f (z) = y. Since f (z) = y = f (x) and f is 1-1, z = x.
Since z 2 B, this means x 2 A \ B and by de…nition y 2 f (A \ B).

Lemma 4.1.4 Let f : X ! Y be a function. Then f is onto if and only of

for every set B Y , f (f 1 (B)) = B.
Proof. Suppose f is onto. Since we proved B Y , f (f 1 (B)) B in
1
Example 1.3.6, we need only show B f (f (B)). Let y 2 B. Since f is
onto there exists some x 2 X such that f (x) = y. Since y 2 B, by de…nition,
x 2 f 1 (B). But then by de…nition, y 2 f (f 1 (B)).
For the converse, suppose that f (f 1 (B)) = B for every B Y . Let
y 2 Y . To use the hypothesis, we need some set B, and the simplest set to try
(which has anything to do with y) is B := fyg. We have y 2 B = f (f 1 (B)),
which means that there is some x 2 f 1 (B) such that f (x) = y. But x 2 X,
which proves that f is onto.

Example 4.1.5 We will show that f : X ! Y is 1-1 if and only if for each
y 2 Y , f 1 (fyg) is either empty or contains a single element. Suppose that
f is 1 1 and there are two di¤erent elements a; b 2 f 1 (fyg). By de…nition
this means f (a); f (b) 2 fyg, which means f (a) = y = f (b). Since f is 1-1,
a = b, a contradiction. Now suppose that for each y 2 Y , f 1 (fyg) is either
empty or contains a single element. If f (a) = f (b) = y then by de…nition
a; b 2 f 1 (fyg). Since the latter set has at most one element, a = b, which
proves that f is 1-1.

Lemma 4.1.6 A function f : X ! Y is 1-1 if and only if for every set

A X, f 1 (f (A)) = A.

Exercise 4.3 Prove the above lemma. Hint: To show that f is 1-1, suppose
f (x) = f (y) and consider the set A := fxg.

Exercise 4.4 Under which assumption, 1-1 or onto, is it true that f (A)nf (B) =
f (AnB)? (Prove your answer.)
4.1 ONE-TO-ONE AND ONTO FUNCTIONS 67

Exercise 4.5 Let F be a …eld and let y 2 F.

1. Prove that the function f : F ! F de…ned by f (x) = x+y is a bijection.

2. What about the function f (x) = xy?

1
3. Find a domain and range such that the function g(x) = x is a bijec-
tion.

We will now consider an important concept that you, to a limited extent,

learned about in calculus. In basic calculus courses, the meaning of important
concepts, if it is ever considered at all, is generally quickly pushed aside and
forgotten as the student focuses on a sea of repetitive exercises that produce
answers but not understanding. You may well recall how to “…nd the inverse”
of functions by “swapping x and y” and then solving for y. This is a task
that is, in reality, almost always impossible. Even so, your calculus text
probably included a large number of specially concocted problems to keep
you busy. You probably also learned about inverse trigonometric functions
and perhaps that the exponential in logarithmic functions are inverses of one
another. However, the concept of inverse functions is much more far reaching
than the simple calculations you were previously asked to do.

De…nition 4.1.7 Let f : X ! Y be a function. A function g : Y ! X is

called an inverse to f if

1. For all x 2 X, g(f (x)) = x and

2. For all y 2 Y , f (g(y)) = y.

Exercise 4.6 Let f : X ! Y be a function with inverse g and B Y . Show

that f 1 (B) = g(B).

Exercise 4.7 Prove that if f : X ! Y is a function with inverse g then f

is an inverse of g.
In general, functions do not have inverses, but the next theorem charac-
terizes exactly when f does have an inverse, namely when f is a bijection.
The theorem also states that when f has an inverse g, g is unique. This
means that any function that satis…es the de…nition of inverse to f must ac-
tually be g. The proof of this theorem involves actually de…ning the inverse
68 CHAPTER 4 ADDITIONAL TOPICS

function g, and in doing so an important step is introduced when de…ning

any function: showing that it is “well de…ned”. We will illustrate this by
trying to de…ne a function that is not well-de…ned, and in doing so give a
false proof that the function f : R ! [0; 1) de…ned by f (x) = x2 has an
inverse g. Let y 2 [0; 1). Since f is onto there exists some x 2 R such
that f (x) = x2 = y. De…ne g : [0; 1) ! R by g(y) := x. By de…nition,
f (g(y)) = f (x) = x2 = y and g(f (x)) = g(x2 ) = g(y) = x, so g is an inverse
to x. Now you probably recall from calculus that f fails the “horizontal line
test”, i.e. it is not 1-1 and so cannot have an inverse. What have we done
wrong? Let’s go back to the part where we use the fact that f is onto, and
the statement that “there exists some x 2 R such that f (x) = x2 = y.”The
problem is that in general there is more than one possible choice for x, e.g.
if y = 1 then we could let x = 1 or x = 1. So we have not precisely de…ned
what g should be, i.e. g is not “well-de…ned”. We could be more careful
and, for example, always choose the non-negative x. This would give us a
well-de…ned function since there is only one such choice, but g would not be
an inverse because, for example, f (g( 1)) = 1. By now you should suspect
that the proof that g is well-de…ned depends on f being 1-1, and that will
indeed be true in the proof below. At any rate, when de…ning a function,
if possible choices are made as part of the de…nition (in this case choosing
one of the values of x given by the “there exists”statement), one must check
that another choice will not a¤ect the de…nition of the function.

Theorem 4.1.8 Let f : X ! Y be a function. Then

1. f has an inverse if and only if f is a bijection, and

2. if f has an inverse then the inverse is unique.

Proof. Suppose …rst that f is a bijection. We want to prove that f has an

inverse g : Y ! X. We will have to actually de…ne what g is–in other words,
given y 2 Y , state what g(y) 2 X should be. We actually have very little
information, which paradoxically makes it easy to decide what to do. We
have only one assumption that has anything to do with y 2 Y , and that is
the fact that f is onto. This tells us that there exists some x 2 X such that
f (x) = y. We will de…ne g(y) := x. We need to check that g is well-de…ned.
Suppose that x0 2 X satis…es f (x0 ) = y (so it would be a legitimate choice for
g(y), according to our de…nition). Since f (x0 ) = y = f (x) and the function
f is 1-1, x0 = x.
4.1 ONE-TO-ONE AND ONTO FUNCTIONS 69

Now that we have de…ned g, we need to check the two conditions to see
that it is an inverse of f . Let x 2 X. If y = f (x) then by de…nition of g,
g(y) = x. Therefore g(f (x)) = g(y) = x, proving the …rst condition. For
the second condition, let y 2 Y and suppose that x = g(y). (Note that
we are starting over with a new part of the proof, and the current x and
y have nothing to do with those in the previous part. We could have used
completely di¤erent letters, but in a complex proof one might well run out of
letters, so you should get used to re-using letters once a particular argument
is …nished.) By de…nition of g, f (x) = y and we have f (g(y)) = f (x) = y.
Therefore g is an inverse of f .
We next show that if f has an inverse g, then f is bijective. Let x; x0 2 X
be such that f (x) = f (x0 ). Since g is an inverse,

x = g(f (x)) = g(f (x0 )) = x0

which proves that f is 1 1. Let y 2 Y . Since g is de…ned on all of Y , g(y)

is de…ned. Since g is an inverse, f (g(y)) = y, which shows that f is onto.
Finally we need to show that g, if it exists, is unique. Suppose that h
were another inverse of f . Let y 2 Y . Then f (g(y)) = y = f (h(y)). But
since f is 1-1 this means that g(y) = h(y) and therefore g and h are the same
function.

Exercise 4.8 Prove that the inverse of a bijection is a bijection.

Notation 4.1.9 Let f : X ! Y be a function. If f is a bijection then since

we we have shown that the inverse of a function is unique, we are free to
give it a speci…c name that depends only on f , and we will denote it by f 1 .
By uniqueness we can refer to f 1 as “the” inverse of f . There are some
notational concerns. We already have de…ned f 1 (A) when A Y and this
set is de…ned whether or not f is a bijection. On the other hand, f 1 by
itself, doesn’t make sense unless f is bijective. If f is bijective, we really
have potentially two meanings for f 1 (A), namely the inverse image of A
with respect to f , and the image of A with respect to f 1 . But according to
Exercise 4.6, these two sets are one and the same.

Exercise 4.9 Prove that if f : X ! Y is a bijection then for any y 2 Y ,

f 1 (fyg) = ff 1 (y)g.
70 CHAPTER 4 ADDITIONAL TOPICS

Exercise 4.10 Let f : X ! Y be a surjective function and g : Y ! X be

a function such that for all x 2 X, g(f (x)) = x. Show that f is a bijection
and g = f 1 .

De…nition 4.1.10 Given functions f : X ! Y and g : Y ! Z, we de…ne

the composition of f and g to be g f : X ! Z, where (g f )(x) = g(f (x))
for all x 2 X.

Example 4.1.11 Let f : X ! Y and g : Y ! Z be functions. We will

show that if g is 1-1 and g f is onto then f is onto. Let y 2 Y . Then
z := g(y) 2 Z. Since g f is onto there exists some x 2 X such that
g(f (x)) = z = g(y). Since g is 1-1, y = f (x), which is what we needed to
prove to show f is onto.

Exercise 4.11 Let f : X ! Y and g : Y ! Z be bijections. Show that

(g f ) 1 = f 1 g 1 . Hint: By uniqueness you need only prove that the two
conditions in the de…nition are satis…ed.

Exercise 4.12 Let f : X ! Y and g : Y ! Z be functions. Show that if

both f and g are 1-1 (resp. onto) then g f is 1-1 (resp. onto).

De…nition 4.1.12 Let X be a nonempty set. The identity function idX :

X ! X is the function de…ned by idX (x) = x.
That is, this function “identi…es” each point in X with itself. It is easy
to check that idX is a bijection. Now suppose f : X ! Y is a bijection.
Then we can translate the two conditions for f 1 using the de…nition of the
identity function: f f 1 (y) = f (f 1 (y)) = y = idY (y); that is, f f 1 = idY .
Likewise, the …rst contition is equivalent to f 1 f = idX .

4.2 Equivalence Relations

De…nition 4.2.1 Let X and Y be sets. A relation R on X Y is a subset
of X Y . A relation on X X will simply be called a relation on X.
Although we did not yet call them relations, you have already seen two of
them in this course: functions and the order relation L in the order axioms.
In each case, these particular relations had additional properties, and we used
di¤erent notation from the standard notation for ordered pairs. For example,
4.2 EQUIVALENCE RELATIONS 71

for functions we used the notation y = f (x) rather than (x; y) 2 f and for the
order relation we used a < b rather than (a; b) 2 L. These di¤erent notations
are of no mathematical consequence any more than it is of mathematical
consequence to use g to describe a particular function rather than f . Each of
those notations precisely describes the idea of an ordered pair: two elements,
with a distinguished order. But each alternate notation is not only much
more familiar than the ordered pair notation, it also somehow contributes
to understanding the concepts and to practical use of those concepts. For
example, if we were to write a b2 + 1 < 2b in ordered pair notation, it
would look like a = b2 + 1 or (a; b2 + 1) 2 L, and (b2 + 1; 2b) 2 L. Notation
is the linguistic interface between mathematic and human beings, and good
choice of notation can greatly facilitate understanding. On the other hand,
poor facility with notation can bring down even an otherwise very capable
student.
For relations in general we will (except for one exercise below) use notation
similar to that used for the order relation. So rather than (x; y) 2 R we
will write xRy. With this notation we will now introduce one of the most
important kinds of relation:

De…nition 4.2.2 A relation R on a nonempty set X is called an equivalence

relation if the following properties are satis…ed:

1. (Re‡exive) For all x 2 X, xRx.

2. (Symmetric) If xRy, for x; y 2 X, then yRx.

3. (Transitive) If xRy and yRz, for x; y; z 2 X, then xRz.

Often we will denote an equivalence relation with they symbol .

For example the order relation < on R is transitive, but is not re‡exive
or symmetric. In fact, by the trichotomy, 1 < 1 is not true, and 2 < 3 but
it is not true that 3 < 2. Similarly the relation is re‡exive and transitive,
but still not symmetric. Finally, the relation = is in fact an equivalence
relation (really this is built into the axioms of set theory). But there would
be no point in de…ning equivalence relations if = were the only one. In fact
equivalence relations are ubiquitous in mathematics, and we will learn only
about a few in this text.
72 CHAPTER 4 ADDITIONAL TOPICS

Note that by symmetry there are variations on the transitive law that are
also true. For example, if is an equivalence relation, it is true that if x y
and z x then z y. We will use such variations without further reference.

Example 4.2.3 On R, de…ne xRy to mean jx yj 1. This relation is

re‡exive, since for any x 2 R, jx xj = 0 1. The relation is symmetric:
If jx yj 1 then jy xj = jx yj 1. But the relation is not transitive.
In fact, j0 1j = 1 and j1 2j = 1 but j0 2j = 2 > 1.

Example 4.2.4 On the collection of all sets, de…ne ARB to mean that A \
B = ?. This relation is not re‡exive, since f1g \ f1g =
6 ?. It is symmetric:
If A \ B = ? then B \ A = ?. It is not transitive since f1; 2g \ f3g = ?
and f3g \ f2g = ? but f1; 2g \ f2g =
6 ?.

Exercise 4.13 For each of the following relations, prove or disprove each
condition: re‡exive, symmetric, and transitive.

1. On R, xRy means x2 = y 2 .

2. On the set of all people, de…ne P RQ to mean that P and Q have at

least one biological parent in common. What if we de…ne P RQ to mean
that P and Q have the same biological parents?

3. On the set of all cities in the world, de…ne CRD to mean that it is not
possible to drive from C to D.

4. On the collection of all sets, de…ne ARB to mean that AnB = ?.

5. On the set of all ordered pairs of real numbers, (x1 ; y1 )R(x2 ; y2 ) means
x1 x2 and y1 y2 .

6. On the set of all ordered pairs of real numbers, (x1 ; y1 )R(x2 ; y2 ) means
x1 x2 or y1 y2 .

Exercise 4.14 Let X be a set.

1. Rewrite the meaning of re‡exive, symmetric, and transitive using the

ordered pair notation ((x; y) 2 R) for a relation R on X.

2. Using the ordered pair notation for functions, show that the identity
function idX is an equivalence relation on X.
4.2 EQUIVALENCE RELATIONS 73

3. Show that if R is an equivalence relation on X that is also a function,

then R is the identity function idX .

Exercise 4.15 Let R be a relation de…ned on a set X such that R is re‡exive

and satis…es the following “twisted transitive law”: For all x; y; z 2 X, if xRz
and xRy then yRz. Prove that R is an equivalence relation.

De…nition 4.2.5 Let X be a set with equivalence relation . For any x 2 X

the equivalence class of x is the set de…ned by

x := fy 2 X : x yg

Since is symmetric, x := fy 2 X : y xg. The next theorem that makes

it easier to determine equivalence classes.

Theorem 4.2.6 Let X be a set with equivalence relation . For any x; y 2

X, if x \ y 6= ? then x = y.
Proof. First of all, let w 2 x \ y; so x w and y w. Now suppose z 2 x. By
de…nition x z. By the transitive and symmetric laws, z w and hence z y,
which means z 2 y. This proves that x y, and by a similar proof y x.
Note that by the re‡exive law x 2 x for every x, and therefore:

Corollary 4.2.7 Let X be a set with equivalence relation . If y 2 x then

x = y.

De…nition 4.2.8 If X is a set, a partition of X consists of a collection P

of non-empty subsets of X such that the following hold:

1. For every x 2 X there is some A 2 P such that x 2 A.

2. If A; B 2 P and A \ B 6= ? then A = B.

In other words, the partition P divides the entire set X into a collection
of subsets such that if any two di¤erent sets in the collection do not intersect.
We have already observed that each element of X is in its own equivalence
class. From Theorem 4.2.6 we obtain:

Corollary 4.2.9 Let X be a set with equivalence relation . The set of

equivalence classes of X forms a partition of X.
74 CHAPTER 4 ADDITIONAL TOPICS

Exercise 4.16 For sets A and B, de…ne A B to mean that there is a bijec-
tion f : A ! B. Prove that is an equivalence relation. This equivalence
indicates that the two sets are, in some sense “the same size”. We will study
it further in the next section.

Exercise 4.17 Let X be a set with a partition P. De…ne a relation on X

by x y means there is some A 2 P such that x; y 2 A. Prove that is an
equivalence relation and the equivalence classes of are precisely the sets in
P.

Exercise 4.18 Let f : X ! Y be a function. De…ne a relation on X by

x y means f (x) = f (y).

1. Prove that is an equivalence relation.

1
2. Prove that for any x 2 X, x = f (ff (x)g).

One of the most important equivalence relations is the following. For

m; n 2 Z and k 2 N, we say m n(mod k) (read “m is equivalent to n
mod k”) if m n is divisible by k. We will check that this is an equivalence
relation. First, for any m 2 Z, m m = 0 k, so m m(mod k). If
m n(mod k) then m n = sk for some s 2 Z. But then n m = ( s)k
where s 2 Z, so n m(mod k). Finally, suppose that m n(mod k) and
n j(mod k). Then m n = rk and n j = sk for some integers r; s. We
have
m j = m n + n j = rk + sk = (r + s)k
and since r + s2 Z this shows that m j(mod k).

De…nition 4.2.10 We will denote the set of equivalence classes mod k by

Zk .
What are the equivalence classes for this equivalence relation? Let’s …rst
consider some speci…c values of k.

Example 4.2.11 For k = 1, m n(mod 1) means that 1 j (m n). Since 1

divides every integer, this means that m n(mod 1) for all m; n 2 Z. That
means Z1 consists of precisely one set: all of Z. For k = 2, m n(mod 2)
means that m n = 2a for some a 2 Z. Let’s start with the equivalence class

0 = fm : m 0 = 2a for some a 2 Zg
4.2 EQUIVALENCE RELATIONS 75

which is precisely the set of all even integers. On the other hand,

1 = fm : m 1 = 2a for some a 2 Zg

and since this means m = 2a+1, 1 consists precisely of the set of odd integers.
Since we already know that every integer is odd or even, every integer must
be in one of these two equivalence classes, so the entire set of equivalence
classes must consist of f0; 1g.

Theorem 4.2.12 For any k 2 N, Zk = f0; :::; k 1g, and no two of these
equivalence classes are the same.
Proof. We know from the Division Algorithm that for any integer m we
may write m = qk + r, where 0 r < k. Since r is an integer, this means
that the only possibilities are r = 0; :::; k 1. But then m r = qk, which is
divisible by k, so m r(mod k). That is, m = r. So m must be one of the
equivalence classes 0; 1; :::; k 1. Now if m 2 a \ b, where a; b 2 f0; :::; k 1g
then by de…nition of the equivalence classes we could write m = q1 k + a and
mq2 k + b, with q1 ; q2 2 Z and 0 a; b < k. If a 6= b this would violate
uniqueness in the Division Algorithm. Therefore no two of the equivalence
classes f0; :::; k 1g intersect, and since they form a partition, no two are
equal.

Corollary 4.2.13 For any k; m 2 N, m = 0 in Zk if and only if k j m.

Example 4.2.14 Consider Z5 = f0; 1; 2; 3; 4g. Given n 2 Z, to determine

n, simply subtract the largest multiple of 5 that is less than or equal to n; if
r is the remainder then n = r. For example, 6 = 1 and 35 = 0, and 2 = 3.
We may de…ne two algebraic operations on Zk using the operations on Z.
First, we de…ne x + y = x + y. While this de…nition looks very natural and
seems at …rst to be OK, we have to be very careful to check that it is well
de…ned. For example, in Z4 , we have 6+15 = 21. On the other hand, we know
that 6 = 2 and 15 = 3, and so we can compute the same sum as 2+3 = 5. But
5 = 1 = 21, so we don’t actually get a di¤erent answer. In general, we need
to prove the following: If x = w and y = z then x + y = w + z. Using the
de…nition of equivalence mod k we have x w = nk and y z = mk for some
m; n 2 Z. But then (x + y) (w + z) = x w + y z = nk + mk = (m + n) k
and therefore x + y = w + z.
76 CHAPTER 4 ADDITIONAL TOPICS

Exercise 4.19 De…ne an operation of multiplication on Zk by x y = x y.

1. Prove that this operation is well-de…ned.
2. Prove that the two operations of + and on Zk satisfy all the axioms
for a …eld except possibly the existence of multiplicative inverses.
3. Show by checking all possibilites that 2 has no multiplicative inverse in
Z4 and so Z4 is not a …eld.
4. Show that in Z4 it is possible that x y = 0, but x 6= 0 and y 6= 0.
Exercise 4.20 Show that Z3 is a …eld by …nding a multiplicative inverse for
each non-zero element.
Why is it true that Z3 is a …eld and Z4 is not? As we will see in the
next section, the di¤erence amounts to the fact that 3 is prime but 4 is not.
For now we can consider the question of when the statement of Lemma 2.1.4
holds in Zk .

Lemma 4.2.15 If p is prime and a; b 2 Z with ab = 0 in Zp then a = 0 or

b = 0.
Proof. If ab = 0 then by de…nition ab = pk for some k 2 Z. By de…nition
p j ab and by Corollary 3.5.6, p j a or p j b. If p j a then a = pm for some
m 2 Z, and so a = 0; the proof when p j b is similar.

Exercise 4.21 Prove that if k 2 is not prime then there exist some a; b 2
Z such that ab = 0 in Zk but a 6= 0 and b 6= 0. In other words, Lemma 2.1.4
holds in Zk precisely when k is prime. From this one may conclude that Zk
is not a …eld when k is not prime.

4.3 Finite Sets

Unlike proofs of the main theorems in previous sections, many of the proofs
in this section are more ad hoc in nature, involving methods that are not so
broadly used. If time does not permit going into the details, a good “working
knowledge” of …nite sets may be obtain by simply learning the de…nitions,
the quite natural statement of Theorem 4.3.5, and its corollaries–particularly
the Pigeonhole Principle. The algebraic theorems at the end of the section
are nice applications, and important statements in their own right.
4.3 FINITE SETS 77

De…nition 4.3.1 Let f : X ! Y be a function and A X. The restriction

of f to A is the function f jA : A ! Y de…ned by f jA (x) = f (x) for all
x 2 A.

Therefore the restriction of f is simply f itself with its domain reduced

to the set A. You have already used restrictions, whether or not you used
the name. For example, when solving a problem like: …nd the maximum of
f (x) = x2 + 3 on the interval [1; 5] what you are actually doing is …nding
the maximum of f j[1;5] . As trivial as the idea of restriction seems at …rst,
it is often useful to consider the restriction of a function as a function in
its own right, which may have very di¤erent properties from the original.
For example, the function f we just considered has no maximim, but as you
learned in calculus, the continuous function f j[1;5] does have a maximum.
For notational simplicity we will often rename f jA in proofs.

Lemma 4.3.2 If f : X ! Y is an injection and A f then f jA is an

injection.

Proof. Let g := f jA . Let x; y 2 A be such that g(x) = g(y). By de…nition,

f (x) = g(x) = g(y) = f (y) and since f is 1-1, x = y, which proves g is 1-1.

Note that it de…nitely is not true that the restriction of an onto function
is onto. For example, if f : R ! R is the identity function f (x) = x, then f
is a bijection. But, for example, f j[0;1] : [0; 1] ! R has range [0; 1] and so is
certainly not onto R.
A related de…nition is that of the corestriction of f : X ! Y . We know
from Lemma 4.1.2 that f is onto if and only if f (X) = Y . The corestriction
of f is simply the function f : X ! f (X). That is, rather than reducing
the domain as we do with a restriction, we are reducing the set into which
the function goes, so that it is the same as the range. Since the corestriction
does not involve any changes in the domain or values of the function f , we
won’t use any special notation for it. In fact, we are mainly interested in the
fact that if f is an injection then the corestriction of f is a bijection, since by
de…nition we are forcing f to be onto. In the future we will simply express
this as “f is a bijection onto f (X)”.

De…nition 4.3.3 We say that sets non-empty sets A and B have the same
cardinality if there exists a bijection from A onto B. If A is empty we say
78 CHAPTER 4 ADDITIONAL TOPICS

that A is …nite with cardinality c(A) = 0. If A has the same cardinality as a

set f1; 2; :::; ng then we say A is …nite with cardinality c(A) = n.
Since the identity function from f1; :::; ng is a bijection, it follows that
c(f1; :::; ng) = n. From Exercise 4.16 it follows that having the same cardi-
nality is an equivalence relation, and by de…nition the equivalence class of
f1; 2; :::; ng is the collection of all sets A such that c(A) = n. Therefore if A
is …nite with c(A) = n and f : A ! B is a bijection then B is …nite with
cardinality n.
Suppose f : A ! f1; :::; ng is a bijection. As is common practice (and
you have likely already seen this notation involving sequences in calculus) we
will write ai := f 1 (i). Since f is a bijection, every element of A is uniquely
expressed in this way; that is, A = fa1 ; :::; an g. In e¤ect the bijection f
“counts” the elements of A. There are n! possible bijections from A to
f1; :::; ng. To see this, note that there are n possible choices for the “…rst”
element a1 , n 1 possible choices for the “second” element a2 , and so on.
The fact that there are so many possible bijections makes proofs of even
the most basic theorems somewhat complicated. As was true when we …rst
introduced the axioms for the real numbers, we need to be careful not to jump
immediately to conclusions that seem “obvious”but really require some proof
involving our de…nition. In fact, many of the statements that we will prove
seem “obvious”and therefore will at least be easy to remember! This includes
the next lemma:

Lemma 4.3.4 If A is …nite and B A then B is …nite with c(B) c(A).

Proof. If A = ? then B = ?, which is …nite. Otherwise A = fa1 ; :::; an g
for some n 2 N; we will prove the statement by induction on n. A = fa1 g
then the only possibilites for B are A and ?, both of which are …nite with
cardinality 1. Suppose we have proved the statement for some n 1, and
let A = fa1 ; :::; an+1 g. If B = A then we are done. Otherwise there is some
am 2 AnB, where 1 m n + 1. De…ne a function g : A ! f1; :::; n + 1g
by g(aj ) = f (aj ) if j 2= fm; n + 1g, g(am ) = n + 1 and g(an+1 ) = m. It is
an exercise to prove that g is 1-1. Moreover, if h := g jB then by Lemma
4.3.2 h is injective, and by construction h : B ! f1; :::; ng. By the inductive
hypothesis, h(B) f1; :::; ng is …nite with c(h(B)) n. But h is a bijection
onto h(B) and therefore c(B) = c(h(B)).

Exercise 4.22 Prove that the function g in the proof of Lemma 4.3.4 is a
4.3 FINITE SETS 79

bijection.
We will now see exactly how the “algebra”concerning …nite cardinalities
works. The next statement should seem reasonable, since when we count
the elements of A and B separately we “double count” any elements in the
intersection. However, the proof is again somewhat tedious.

Theorem 4.3.5 Let A and B be …nite sets. Then A [ B and A \ B are

…nite, and c(A [ B) = c(A) + c(B) c(A \ B). In particular, if A and B are
disjoint then c(A [ B) = c(A) + c(B).
Proof. If A = ? then A [ B = B and A \ B = ? so the equation becomes
c(B) = 0 + c(B) + 0, which is true. A similar argument proves the case
when B = ?, so we may assume both A and B are nonempty. We …rst
suppose that A and B are disjoint; we need to show that A [ B is …nite and
c(A [ B) = c(A) + c(B). Let f : A ! f1; :::; ng and g : B ! f1; :::; mg
be bijections. De…ne a function h : A [ B ! f1; :::; n; n + 1; :::; n + mg as
follows. If x 2 A de…ne h(x) = f (x). If x 2 B de…ne h(x) = n + g(x). Since
A \ B = ?, this function is well de…ned (any x is either in A or B but not
in both). We will check that this function is a bijection. Suppose …rst that
h(x) = h(y). If both x; y 2 A, then f (x) = h(x) = h(y) = f (y) and since f is
1-1, x = y. If both x; y 2 B, then n + g(x) = h(x) = h(y) = n + g(y), which
implies g(x) = g(y) and again x = y. But there are no other possibilities.
For example if x 2 A and y 2 B then h(x) n but h(y) > n, so h(x) 6= h(y).
To show h is onto, let z 2 f1; :::; n; n + 1; :::; n + mg. If z 2 fn + 1; :::; n + mg
then z = n + j for some j 2 f1; :::; mg. Since g is onto there is some x 2 B
such that g(x) = j. But then h(x) = n+j = z. The proof when z 2 f1; :::; ng
is similar (and easier).
To …nish the proof we note that by Lemma 4.3.4 AnB, A \ B, and BnA
are all …nite. The Disjoint Union Lemma (Lemma 1.2.2) allows us to write
A [ B = (AnB) [ (A \ B) [ (BnA)
where any two of the sets on the right are disjoint. This allows us to apply
the case we just considered to get
c(A [ B) = c(AnB) + c(A \ B) + c(BnA)
= [c(AnB) + c(A \ B)] + [c(BnA) + c(A \ B)] c(A \ B)
We may now apply The Disjoint Union Lemma again to conclude that this
last quantity is equal to c(A) + c(B) c(A \ B).
80 CHAPTER 4 ADDITIONAL TOPICS

Corollary 4.3.6 If A is …nite and B is a proper subset of A then c(B) <

c(A).

Exercise 4.23 Prove Corollary 4.3.6. Hint: Use Theorem 4.3.5 and the
Disjoint Union Lemma.
For the next corollary we need to consider unions of …nitely many sets.

De…nition 4.3.7 For sets A1 ; :::; An , de…ne

A1 [ [ An := fx : x 2 Ai for some 1 i ng
The intersection of …nitely many sets may de…ned similarly, replacing “for
some” by “for all”.

Pn 4.3.8 If A is a …nite set and fA1 ; :::; An g is a partition of A then

Corollary
c(A) = i=1 c(Ai ).
Proof. The proof is by induction. For n = 1, A = A1 and the equation
reduces to c(A) = c(A1 ), which is true. Suppose that we have proved the
corollary for some n 1, and let fA1 ; :::; An+1 g be a partition of A. Let
B = A1 [ [An . Then Pn 1 ; :::; An g is a partition of B, and so by the inductive
fA
hypothesis, c(B) = i=1 c(Ai ). Now B \ An+1 = ? and A = B [ An+1 . That
is, fB; An+1 g is a partition of A. By Theorem 4.3.5 we get
X
n+1
c(A) = c(B) + c(An+1 ) = c(Ai )
i=1

Corollary 4.3.9 If f : X ! Y is a function between …nite sets with c(X) =

c(Y ) > 0 then f is onto if and only if f is 1-1. In particular, f is a bijection
if it is 1-1 or onto.
Proof. Suppose that f is onto. By Exercise 4.18 and Corollary 4.2.9 we
know that the sets f 1 (fyg) are a partition of X, and therefore
X
n
1
n = c(X) = c(f (fyg)) (4.1)
i=1

Since each of the sets f 1 (fyg) has cardinality at least 1, the equation 4.1
implies each must have cardinality exactly 1. That is, f 1 (fyg) contains
4.3 FINITE SETS 81

a single element, which means f is 1-1 (see Example 4.1.5). Now suppose
that f is 1-1. Then f is a bijection onto its image B := f (X) Y , so
c(B) = c(X) = c(Y ). Corollary 4.3.6 now implies that f (X) cannot be a
proper subset; i.e., f (X) = Y , so f is onto.

Exercise 4.24 Prove that a …nite union of …nite sets is …nite. That is, if
A = A1 [ [ An and each Ai is …nite then A is …nite.

Exercise 4.25 Prove that every …nite subset of real numbers has a maxi-
mum.
The following statement seems almost too simple to be useful, but it is
heavily used in discrete mathematics and computer science. The name comes
from the following interpretation: Suppose there are n pigeons and fewer than
n holes. If each pigeon is placed in a hole then at least two pigeons will share
a hole.

Corollary 4.3.10 (Pigeonhole Principle) If f : X ! Y is a function be-

tween non-empty …nite sets and c(Y ) < c(X) then for some x; y 2 X,
f (x) = f (y).

Exercise 4.26 Prove the Pigeonhole Principle. Hint: Prove the contraposi-
tive and use the fact that f is onto f (X) Y .
The next two exercises are applications of the Pigeonhole Principle. The
trick is …guring out what are the “pigeons” and what are the “holes”. For
the …rst one, note that we can now give a more precise interpretation of the
choose function nk . It is the number of distinct subsets of cardinality k that
are contained in a set of cardinality n.

Exercise 4.27 Prove that if A f1; :::; 9g with c(A) = 6 then there exist
x; y 2 A such that x + y = 10. (Note that x and y may not be di¤erent!)
Hint: Two of the “holes” are f3; 7g and f5g.

Exercise 4.28 Let A Z have c(A) = 16. Prove that there exist at least
two di¤erent elements m; n 2 S such that m n(mod 12).
We conclude this section with some algebraic applications.

Theorem 4.3.11 For k 2 N with k 2, Zk is a …eld if and only if k is

prime.
82 CHAPTER 4 ADDITIONAL TOPICS

Proof. If k is not prime then according to Exercise 4.21, Zk is not a …eld.

Suppose that k is prime. According to Exercise 4.19 we need only show
every m 2 Zk with m 6= 0 has a multiplicative inverse. Consider the function
f : Zk ! Zk de…ned by f (n) = mn. Suppose that f (a) = f (b) for some a; b 2
Zk . This means that ma = mb. Now m(b a) = ma mb = ma mb = 0.
According to Lemma 4.2.15, m = 0 or b a = 0. Since m 6= 0 by assumption,
it must be that b a = 0 or a = b. This proves that f is 1-1. By Corollary
4.3.9, f is also onto. Then for some c 2 Zk , 1 = f (c) = mc. But this is
precisely what it means for c to be the multiplicative inverse of m.
Note that the above proof is purely and existence proof and doesn’t pro-
vide any good way to actually …nd the multiplicative inverse. The next
theorem goes at least back to Euclid. If a set A is not …nite we say it is
in…nite.

Theorem 4.3.12 There are in…nitely many primes.

Proof. Suppose there were …nitely many primes p1 ; :::; pk . Let p := p1
pk + 1. By the division algorithm, for any i we may only write p = pi q + r in
exactly one way when 0 r < pi . But we already have one such expression
when q is the product of all pj when j 6= i and r = 1. So it cannot be that
pi j p, since this would be an expression with remainder 0. That is p cannot
have a prime factorization using the primes p1 ; :::; pk .

4.4 In…nite sets

In the previous section we de…ned “in…nite” sets to be those that are not
…nite. Historically, “in…nity” was considered as something that was essen-
tially larger than everything, and could not be understood by the …nite,
mortal mind. Therefore the idea that in…nity can not only be studied, but
actually comes in “di¤erent sizes”, was a bit of a shock to the mathematical
world. In the 19th century Georg Cantor proved not only that the natural
numbers and the real numbers do not have the same cardinality, but that are
there in…nitely many in…nite cardinalities. Cantor’s work was not immedi-
ately embraced by the mathematics community, which had su¤ered from the
improper in‡uences of religion and philosophy since the time of the ancient
pythagoreans–who went so far as to worship some numbers and thought all
numbers must be ratios. According to legend, in an early example of mur-
derous religious fanaticism, the Pythagoreans drowned the poor fellow who
4.4 INFINITE SETS 83
p
proved that 2 is irrational. Thousands of years later, Cantor fared only
a little better. He was vili…ed by some of his fellow mathematicians for his
radical ideas about in…nity (something that only God was supposed to be
able to understand) and was ultimately driven to madness, but his work help
paved the way to the current state of a¤airs in which mathematical ideas are
accepted based on the correctness of their proofs and not the degree to which
they don’t upset someone’s religious sensibilities.
Note that the natural numbers N cannot be …nite. In fact, if N were …nite
of cardinality n then the fact that N contains f1; :::; ng as a proper subset
would contradict Corollary 4.3.6.

De…nition 4.4.1 If A has the same cardinality as the natural numbers N,

then we say A is countably in…nite. If A is either …nite or countably in…nite
then we say A is countable. Otherwise, we say that A is uncountable.
A bijection from N to a set A is, in e¤ect, “counting” the elements of
A. After all, exactly one element is being assigned 1, a di¤erent element
is assigned 2, and so on. Therefore it makes sense to refer to a set that is
in…nite and for which no such bijection exists as “uncountable”.

Exercise 4.29 Prove that if A is countable (resp. uncountable) and f : A !

B is a bijection then B is countable (resp. uncountable).

Lemma 4.4.2 N and Z have the same cardinality.

Proof. Consider the function that takes every even natural number 2m to
m and every odd natural number 2k + 1 to k. It is easy to check that this
function is a bijection.

Exercise 4.30 Prove that every …nite set is a subset of a countably in…nite
set. Hint: If c(A) = n de…ne a bijection from A [ fn + 1; n + 2; :::g to N.

Theorem 4.4.3 The set [0; 1] R is uncountable.

Proof. The method of proof is known as a Cantor diagonal proof. We will
need to use a fact, the proof of which is beyond the scope of this course: Every
real number has a decimal expansion, and every decimal expansion represents
a real number. Therefore, the set [0; 1] consists of all decimals 0: 1 2 3 ,
where each i is an element of f0; 1; :::; 9g. Note that the decimal expansion
is not unique. Any decimal expansion that is eventually all 9’s is equal to
84 CHAPTER 4 ADDITIONAL TOPICS

a decimal expansion that is eventually all 0’s. For example 0:349999::: =

0:350000. (If you don’t believe it, try to …nd the decimal expansion of a
number between them, which must exist by Exercise 3.10.) In the proof that
follows we will be careful to avoid expansions like this. We will prove the
statement by contradiction. If the statement is false then there is a bijection
from N to [0; 1], which we can write in decimal notation as:

1 7! 0: 11 12 13 14

2 7! 0: 21 22 23 24

3 7! 0: 31 32 33 34

We will obtain a contradiction by showing that this function is not onto, that
is, by showing that there is a decimal expansion 0: 1 2 3 that is not listed
on the right side. We will construct it by “tweaking” the diagonal. If ii is
not 9 then let i := ii + 1. If ii = 9 then let i = 8. Since i 6= 0 and
i 6= ii , it is not possible that 0: 1 2 3 = 0: i1 i2 i3 i4 for any i.

Proposition 4.4.4 If A is countable and B A then B is countable.

Proof. We start by showing that any subset of N is countable. Let B N.
De…ne f : B ! N by f (n) = c([1; n] \ B). It is an exercise to show that f is
injective and if B is not …nite then f is surjective and hence bijective–which
makes B countably in…nite. If A is any countable set then there is a bijection
g : A ! N. If B A then the restriction of g to B is a bijection onto a
subset of N (Lemma 4.3.2), and therefore is countable.

Corollary 4.4.5 If B is uncountable and B A then A is uncountable.

Corollary 4.4.6 R is uncountable.

Exercise 4.31 Finish the proof of Proposition 4.4.4. Hint: Show that if
m < n in B then f (m) < f (n). If B is not …nite, prove that f is onto N by
induction.
4.5 INDEXED COLLECTIONS OF SETS (OPTIONAL) 85

Exercise 4.32 Prove that a set A is countable if and only if there is a sur-
jection : N ! A. Conclude that if B is countable and there is a surjection
from B onto a set A then A is countable. Hint: Given a surjection , de…ne
1
a function g : A ! N by letting g(x) be the smallest element of (fxg),
and show that g is 1-1.

4.5 Indexed Collections of Sets (Optional)

An indexing makes precise the idea of “labeling”a collection of sets. This is
particularly important when considering in…nite collections of sets.

De…nition 4.5.1 An indexing of a collection A of sets with indexing set

is an onto function : ! A. We normally write A rather than A = ( )
and denote the indexed collection by fA g 2 .
Thus the indexing of A “assigns”to each a unique set A in the collec-
tion A. Note that it is possible that A = A 0 when 6= 0 (i.e. the indexing
is not 1-1).

Example 4.5.2 Consider the collection f( n; n)gn2N of all real intervals

( n; n), where n is a natural number. Written more explicitly this is the
collection f( 1; 1); ( 2; 2); ( 3; 3); :::g. As another example, f[ r; r]gr2(0;1)
is the collection of all closed intervals having endpoints r; r, where 0 < r <
1.
T
Exercise 4.33 Prove that N = A, where C is the collection of all super-
A2C
natural subsets A of R.
Given an indexed collection of sets fA g 2 , we de…ne the intersection of
the collection to be
\
A := fx : x 2 A for all 2 g
2

and the union of the collection to be

[
A := fx : x 2 A for some 2 g.
2
S1
When
Tm = N (or is …nite) we will often write, for example, i=1 Ai (or
i=1 Ai ).
86 CHAPTER 4 ADDITIONAL TOPICS
S1
Example
S1 4.5.3 Let A n := [ n; n]. Then n=1 An = R. In S1fact, if x 2
i=1 An then x 2 [ n; n] for some n, and hence x 2 R, so n=1 An R.
For the opposite inclusion note that if x 2 R, x 2 [ S
n; n] for some n 2 N by
the unboundedness of N. But then by de…nition x 2 1 i=1 An .

Example 4.5.4 We will prove that for sets A and fA g 2 we have the
following distributive law:
!
[ [
A\ A = (A \ A )
2 2

S
We have x 2 A \ 2 A if and only if
[
x 2 A and x 2 A
2

, x 2 A and x 2 A for some 2

, x 2 A \ A for some 2
[
,x2 (A \ A ) .
2

Exercise 4.34 Verify that if we Thave only two sets A1 andSA2 (i.e. the
indexing set is = f1; 2g) then 2f1;2g A = A1 \ A2 and 2f1;2g A =
A1 [ A2 . Therefore our new more general de…nitions are consistent with the
old ones.

Exercise
T 4.35 Let fA
S g 2 be a collection of sets. Show that for each 0 2
, 2 A A 0 2 A .

Exercise 4.36 Find the intersections and unions of the following collections
(no need to write down a proof, but be careful about your answers!)

1. f( n; n)g1
n=1

2. f[ r; r]gr2(0;1)

3. f(0; 1i ]g1
i=1
4.5 INDEXED COLLECTIONS OF SETS (OPTIONAL) 87

Exercise 4.37 Prove the followingS generalization

T of the de Morgan law (1.3)
for arbitrary intersections An 2 A = 2 (AnA ). Formulate the ap-
propriate generalizations of (1.2) and the remaining distributive law, but don’t
bother to write down proofs unless you need extra practice.

If : ! A is an indexing with countably in…nite then there is a

bijection g : N ! . The function g : N !A is an indexing of the same
collection A with (possibly more convenient) indexing set N. Reindexing
does not, of course change the collection A in any way and we will therefore
use N as our indexing set when proving general theorems about countable
collections. Likewise if is …nite with cardinality n then we may assume
that = f1; :::; ng.

Proposition
S 4.5.5 If fAi gi2 is a countable collection of countable sets then
Ai is countable.
i2

Proof. This proof uses a kind of diagonal argument. First suppose that
every Ai is countably in…nite and = N. So there is a bijection gi : N ! Ai .
Let aij = gi (j); that
S is, Ai = fai1 ; ai2 ; ai3 ; :::g. So we may list all of the
elements of A := Ai as follows:
i2N

a11 ; a12 ; a13 ; a14 ; :::

a21 ; a22 ; a23 ; a24 ; :::

a31 ; a32 ; a33 ; a34 ; :::

We will construct a surjection f : N ! A as follows. Let f (1) = a11 ,

f (2) = a12 , f (3) = a21 , f (4) = a13 , f (5) = a22 , etc. So we are “counting”
A by going down along diagonals that start at a1j . It is possible, but very
tedious, to de…ne f more explicitly and prove it is surjective. But rather
than assigning it as an exercise, we’ll start your transition to more advanced
mathematics classes by trusting that you can do it. By Exercise 4.32, A is
countable.
88 CHAPTER 4 ADDITIONAL TOPICS

In general, every Ai is contained in a countably in…nite set A0i (if Ai is

in…nite, let A0i := Ai ; otherwise use Exercise 4.30). If is …nite then we
may take = f1; :::; mg. For every natural number i > m, let A0i := Am .
So we now have a collection fA0i gi2N that satis…es the assumption
S 0 of the
case considered above. But it is easy to check that A Ai , and so A is
i2N
countable.
Let Qn := f np : p 2 Zg. The function p ! p
is surjective from Z !Qn
n
S
1
and by Exercise 4.32 Qn is countable. But Q = f0g [ Qn and we
i=1
obtain:

Corollary 4.5.6 The set of rational numbers Q is countably in…nite.

We conclude with the following observation, which illustrates why one
must be so precise in mathematics. We have already seen that between
every two irrationals there is a rational (Exercise 3.10), and it is not hard
to prove that between every two rationals there is an irrational. These two
subsets seem to be “evenly spaced”and a casual observer might take this to
mean that there are “the same number”of irrationals as rationals. However,
since we have made precise the idea of “same number”to mean “same cardi-
nality”, which we have clearly de…ned, and carefully proved some theorems
about this concept, we can now prove that this statement is false: We know
that the rationals are countable. But since the real numbers are the union
of the rationals and the irrationals, and the real numbers are uncountable,
then the irrationals must be uncountable. It may well have been vague ar-
guments like the one above, using ill-de…ned terms to make incorrect claims
that sound reasonable and support preconceived notions, that lead many
otherwise smart people to reject the proofs of Cantor near the end of the
18th century. Unfortunately, in everyday life arguments like this still result
in wrong conclusions and bad decisions on scales from the individual to the
international. But the methods that you have learned in this course should
help you steer clear of such errors in the future–at least where mathematics
is concerned!
Index

approximation property for infs/sups, mod k, 74

30 equivalence class, 73
Archimedean Principle, 44 equivalence relation, 71
aZ, 55 even, 55, 56
base case, 47 f 1 , 69
bijection, 65 factor, 55
binomial theorem, 53 …eld, 19
bounds, upper and lower, see sets …nite, 77
functions, 16
cardinality
composition of, 70
…nite, 77
corestriction of, 77
choose function, 51
domain of, 16
closed form, 50
completeness axiom, 28 inverse, 67
composition, 70 one-to-one, 65
corestriction, 77 onto, 65
countable, 83 range of, 16
countably in…nite, 83 restriction of, 77
Fundamental Theorem of Arithmetic,
de Morgan’s laws, 10, 87 62
density of rationals, 49
disjoint union lemma, 13 Gap Theorem, 41, 43
divide, 55 greatest common divisor, 58
divisible, 55
division algorithm, 60 idX , 70
divisor, 55 identity function, 70
common, 55 image, 17
domain, 16 indexing set, 85
Induction, Principle of, 47
empty set, 8 strong, 51
equivalence inductive hypothesis, 47

89
90 INDEX

in…mum or inf, see sets restriction, 77

in…nite set, 82
injection, 65 sets
integer bounds, 28
even, 55, 56 cardinality of, 77
odd, 56 cartesian product of, 14
integers, 42 complement of, 8
closed under multiplication, 47 disjoint, 8
closed uner addition, 42 distributive laws, 13
interval, 30 in…nite, 82
inverse image, 17 intersection of, 8, 85
maximimum/minimum of, 28
maximum/minimum, see sets partition of, 73
re‡ection (negation) of, 33
N (natural numbers), 3
sup/inf of, 28
natural numbers, 40
supernatural, 40
closed under multiplication, 47
union of, 8, 85
odd, 56 square
p root, 31, 63
one-to-one correspondence, 65 2
order axioms, 25 existence of, 31
ordered pair, 14 irrationality of, 59
subset, 8
partition, 73 proper, 8
Pigeonhole Principle, 81 supernatural, 40
powers supremum or sup, see sets
integer, 48 surjection, 65
prime number, 61 symmetric, 71
in…nitely many, 82
transitive, 71
Q (rationals), 3 triangle inequality, 34
R, 28 truth table, 4
uncountability of, 83
uncountable, 83
range, 16
Unique Factorization Theorem, 62
reduced form (fraction), 59
re‡ection of a set, 33 vacuous hypothesis, 5
re‡exive, 71 Venn diagram, 9
relation, 70
equivalence, 71 well-de…ned, 68
INDEX 91

Well-ordering Principle, 42, 46

Z (integers), 3
Zk , 74