Kabankalan Catholic College

COLLEGE DEPARTMENT
City of Kabankalan, Negros Occidental
IT 104: DISCRETE MATHEMATICS

LESSON 1

Introduction and Preliminaries

Welcome to Discrete Mathematics. If this is your first time encountering

the subject, you will probably find discrete mathematics quite different
from other math subjects. You might not even know what discrete math is!
Hopefully this short introduction will shed some light on what the subject
is about and what you can expect as you move forward in your studies.

What is Discrete Mathematics?

dis·crete / dis’krët.
Adjective: Individually separate and distinct.
Synonyms: separate - detached - distinct - abstract.

Defining discrete mathematics is hard because defining mathematics is

hard. What is mathematics? The study of numbers? In part, but you
also study functions and lines and triangles and parallelepipeds and
vectors and Or perhaps you want to say that mathematics is a collection
of
tools that allow you to solve problems. What sort of problems? Okay,
those that involve numbers, functions, lines, triangles, Whatever your
conception of what mathematics is, try applying the concept of
“discrete” to it, as defined above. Some math fundamentally deals with
stuff that is individually separate and distinct.
In an algebra or calculus class, you might have found a particular set of
numbers (maybe the set of numbers in the range of a function). You would
represent this set as an interval: [ 0,∞) is the range of f( x) = x2 since the
set of outputs of the function are all real numbers 0 and greater. This set
of numbers is NOT discrete. The numbers in the set are not separated
by much at all. In fact, take any two numbers in the set and there are
infinitely many more between them which are also in the set.
Discrete math could still ask about the range of a function, but the
set would not be an interval. Consider the function which gives the
number of children of each person reading this. What is the range? I’m
guessing it is something
{ like} 0, 1, 2, 3 . Maybe 4 is in there too. But certainly
there is nobody reading this that has 1.32419 children. This output set is
discrete because the elements are separate. The inputs to the function
also form a discrete set because each input is an individual person.
One way to get a feel for the subject is to consider the types of problems
you solve in discrete math. Here are a few simple examples:

Investigate!
Note: Throughout the text you will see Investigate! activities like
this one. Answer the questions in these as best you can to give
yourself a feel for what is coming next.
1. The most popular mathematician in the world is throwing
a party for all of his friends. As a way to kick things off,
they decide that everyone should shake hands. Assuming
all 10 people at the party each shake hands with every other
person (but not themselves, obviously) exactly once, how
many handshakes take place?
2. At the warm-up event for Oscar’s All Star Hot Dog Eating
Contest, Al ate one hot dog. Bob then showed him up by
eating three hot dogs. Not to be outdone, Carl ate five.
This continued with each contestant eating two more hot
dogs than the previous contestant. How many hot dogs did
Zeno (the 26th and final contestant) eat? How many hot dogs
were eaten all together?
3. After excavating for weeks, you finally arrive at the burial
chamber. The room is empty except for two large chests. On
each is carved a message (strangely in English):

If this chest is This chest is filled

empty, then the with treasure or the
other chest’s other chest
message is contains deadly
true. scorpions.

You know exactly one of these messages is true. What should

you do?
4. Back in the days of yore, five small towns decided they
wanted to build roads directly connecting each pair of towns.
While the towns had plenty of money to build roads as long
and as winding as they wished, it was very important that
the roads not intersect with each other (as stop signs had
not yet been invented). Also, tunnels and bridges were not
allowed. Is it possible for each of these towns to build a
road to each of the four other towns without creating any
intersections?

! Attempt the above activity before proceeding !

 One reason it is difficult to define discrete math is that it is a very broad
description which encapsulates a large number of subjects. In this
course we will study four main topics: combinatorics (the theory of ways
things combine; in particular, how to count these ways), sequences,
symbolic logic, and graph theory. However, there are other topics that
belong under the discrete umbrella, including computer science, abstract
algebra, number theory, game theory, probability, and geometry (some
of these, particularly the last two, have both discrete and non-discrete
variants).
Ultimately the best way to learn what discrete math is about is to do it.
Let’s get started! Before we can begin answering more complicated (and
fun) problems, we must lay down some foundation. We start by reviewing
mathematical statements, sets, and functions in the framework of discrete
mathematics.

Lesson 2: Mathematical Statements

Investigate!
While walking through a fictional forest, you encounter three trolls guarding a bridge
Troll 1: If I am a knave, then there are exactly two knights here.
Troll 2: Troll 1 is lying.
Troll 3: Either we are all knaves or at least one of us is a knight.
Which troll is which?

! Attempt the above activity before proceeding !

In order to do mathematics, we must be able to talk and write about
mathematics. Perhaps your experience with mathematics so far has mostly
involved finding answers to problems. As we embark towards more
advanced and abstract mathematics, writing will play a more
prominent role in the mathematical process.
Communication in mathematics requires more precision than many
other subjects, and thus we should take a few pages here to consider
the basic building blocks: mathematical statements.
 Atomic and Molecular Statements
A statement is any declarative sentence which is either true or false.
A statement is atomic if it cannot be divided into smaller statements,
otherwise it is called molecular.

Example

These are statements (in fact, atomic statements):

• Telephone numbers in the USA have 10 digits.
• The moon is made of cheese.
• 42 is a perfect square.
• Every even number greater than 2 can be expressed as the
sum of two primes.

3 + 7 = 12
And these are not statements:
Would you like some cake?
The sum of two squares.
1 + 3 + 5 + 7 + · · · + 2n + 1.
Go to your room!
3 + x = 12

The reason the sentence “3 + x = 12” is not a statement is that it

contains a variable. Depending on what x is, the sentence is either true
or false, but right now it is neither. One way to make the sentence into a
statement is to specify the value of the variable in some way. This could
be done by specifying a specific substitution, for example, “3 + x = 12
where x = 9,” which is a true statement. Or you could capture the free
variable by quantifying over it, as in, “for all values of x, 3 + x = 12,”
which is false. We will discuss quantifiers in more detail at the end of
this section.
You can build more complicated (molecular) statements out of simpler
(atomic or molecular) ones using logical connectives. For example, this is
a molecular statement:

Telephone numbers in the USA have 10 digits and 42 is a

perfect square.

Note that we can break this down into two smaller statements. The
two shorter statements are connected by an “and.” We will consider 5
connectives: “and” (Sam is a man and Chris is a woman), “or” (Sam is a
man or Chris is a woman), “if. . . , then. . . ” (if Sam is a man, then Chris is
a woman), “if and only if” (Sam is a man if and only if Chris is a
woman), and “not” (Sam is not a man). The first four are called binary
connectives (because they connect two statements) while “not” is an
example of a unary connective (since it applies to a single statement).
These molecular statements are of course still statements, so they must
be either true or false. The absolutely key observation here is that which
truth value the molecular statement achieves is completely determined
by the type of connective and the truth values of the parts. We do not
need to know what the parts actually say, only whether those parts are
true or false. So to analyze logical connectives, it is enough to consider
propositional variables (sometimes called sentential variables), usually
capital letters in the middle of the alphabet: P, Q, and R, S, We think of
these as standing in for (usually atomic) statements, but there are only two
values the variables can achieve: true or false.

Logical Connectives.
P ∧ Q is read “P and Q,” and called a conjunction.
P ∨ Q is read “P or Q,” and called a disjunction.

P → Q is read “if P then Q,” and called an implication or

conditional.
P ↔ Q is read “P if and only if Q,” and called a biconditional.
¬P is read “not P,” and called a negation.

1 We also have symbols for the logical connectives: ∧, ∨, →, ↔, ¬.

The truth value of a statement is determined by the truth value(s) of
its part(s), depending on the connectives:
Truth Conditions for Connectives.
• P ∧ Q is true when both P and Q are true.
• P ∨ Q is true when P or Q or both are true.
• P → Q is true when P is false or Q is true or both.
• P ↔ Q is true when P and Q are both true, or both false.
• ¬P is true when P is false.
Note that for us, or is the inclusive or (and not the sometimes used
exclusive or) meaning that P Q is in fact true when both P and Q are
∨
true. As for the other connectives, “and” behaves as you would expect,
as does negation. The biconditional (if and only if) might seem a little
strange, but you should think of this as saying the two parts of the
statements are equivalent in that they have the same truth value. This
leaves only the conditional P Q which has a slightly different meaning
→
in mathematics than it does in ordinary usage. However, implications are
so common and useful in mathematics, that we must develop fluency
with their use, and as such, they deserve their own subsection.
 Implications
Implications.
An implication or conditional is a molecular statement of the form
P→Q
where P and Q are statements. We say that
P is the hypothesis (or antecedent).
Q is the conclusion (or consequent).
An implication is true provided P is false or Q is true (or both),

and false otherwise. In particular, the only way for P → Q to be false

is for P to be true and Q to be false.

Easily the most common type of statement in mathematics is the

implication. Even statements that do not at first look like they have this
form conceal an implication at their heart. Consider the Pythagorean
Theorem. Many a college freshman would quote this theorem as “a2 + b2 =
c2.” This is absolutely not correct. For one thing, that is not a statement
since it has three variables in it. Perhaps they imply that this should be
true for any values of the variables? So 12 + 52 = 22??? How can we fix this?
Well, the equation is true as long as a and b are the legs of a right
triangle and c is the hypotenuse. In other words:

If a and b are the legs of a right triangle with hypotenuse c,

then a2 + b2 = c2.

This is a reasonable way to think about implications: our claim is that the
conclusion (“then” part) is true, but on the assumption that the hypothesis
(“if” part) is true. We make no claim about the conclusion in situations
when the hypothesis is false.2
Still, it is important to remember that an implication is a statement,
and therefore is either true or false. The truth value of the implication is
determined by the truth values of its two parts. To agree with the usage
above, we say that an implication is true either when the hypothesis is
false, or when the conclusion is true. This leaves only one way for an
implication to be false: when the hypothesis is true and the conclusion
is false.
2However, note that in the case of the Pythagorean Theorem, it is also the case that
if a2 + b2 = c2, then a and b are the legs of a right triangle with hypotenuse c. So we
could have also expressed this theorem as a biconditional: “a and b are the legs of a right
triangle with hypotenuse c if and only if a2 + b2 = c2.”
 Example

Consider the statement:

If Bob gets a 90 on the final, then Bob will pass the class.

This is definitely an implication: P is the statement “Bob gets a 90

on the final,” and Q is the statement “Bob will pass the class.”
Suppose I made that statement to Bob. In what circumstances
would it be fair to call me a liar? What if Bob really did get a 90
on the final, and he did pass the class? Then I have not lied; my
statement is true. However, if Bob did get a 90 on the final and
did not pass the class, then I lied, making the statement false. The
tricky case is this: what if Bob did not get a 90 on the final?
Maybe he passes the class, maybe he doesn’t. Did I lie in either
case? I think not. In these last two cases, P was false, and the
statement P → Q was true. In the first case, Q was true, and so
was P → Q.
So P → Q is true when either P is false or Q is true.
Just to be clear, although we sometimes read P Q as “P implies Q”,
we are not insisting that there is some causal relationship
→ between the
statements P and Q. In particular, if you claim that P Q is false, you are
not saying that P does not imply Q, but rather that→P is true and Q is
false.

Example

Decide which of the following statements are true and which are
false. Briefly explain.
1. If 1 = 1, then most horses have 4 legs.
2. If 0 = 1, then 1 = 1.
3. If 8 is a prime number, then the 7624th digit of π is an 8.
4. If the 7624th digit of π is an 8, then 2 + 2 = 4.

Solution. All four of the statements are true. Remember, the only
way for an implication to be false is for the if part to be true and the
then part to be false.
1. Here both the hypothesis and the conclusion are true, so
the implication is true. It does not matter that there is no
meaningful connection between the true mathematical fact
and the fact about horses.
2. Here the hypothesis is false and the conclusion is true, so
the implication is true.
 I have no idea what the 7624th digit of π is, but this does not matter. Since the hypothe
Similarly here, regardless of the truth value of the hypothesis, the conclusion is true, ma

It is important to understand the conditions under which an

implication is true not only to decide whether a mathematical statement is
true, but in order to prove that it is. Proofs might seem scary (especially
if you have had a bad high school geometry experience) but all we are
really doing is explaining (very carefully) why a statement is true. If
you understand the truth conditions for an implication, you already
have the outline for a proof.
Direct Proofs of Implications.

To prove an implication P → Q, it is enough to assume P, and from

it, deduce Q.

Perhaps a better way to say this is that to prove a statement of the form
P →Q directly, you must explain why Q is true, but you get to assume P
is true first. After all, you only care about whether Q is true in the case
that P is as well.
There are other techniques to prove statements (implications and
others) that we will encounter throughout our studies, and new proof
techniques are discovered all the time. Direct proof is the easiest and most
elegant style of proof and has the advantage that such a proof often does a
great job of explaining why the statement is true.
Example

Prove: If two numbers a and b are even, then their sum a + b is even.
Solution.
Proof.Suppose the numbers a and b are even. This means that
a = 2k and b = 2 j for some integers k and j. The sum is then

a + b = 2k + 2 j = 2(k + j). Since k + j is an integer, this means that

a + b is even. ■
Notice that since we get to assume the hypothesis of the impli- cation, we immediately
 This sort of argument shows up outside of math as well. If you ever
found yourself starting an argument with “hypothetically, let’s assume
. . . ,” then you have attempted a direct proof of your desired conclusion.
An implication is a way of expressing a relationship between two state-
ments. It is often interesting to ask whether there are other
relationships between the statements. Here we introduce some
common language to address this question.
Converse and Contrapositive.

The converse of an implication P → Q is the implication Q →

P. The converse is NOT logically equivalent to the original implication. That is,

The contrapositive of an implication P → Q is the statement

¬Q → ¬P. An implication and its contrapositive are logically
equivalent (they are either both true or both false).

Mathematics is overflowing with examples of true implications which

have a false converse. If a number greater than 2 is prime, then that
number is odd. However, just because a number is odd does not mean
it is prime. If a shape is a square, then it is a rectangle. But it is false that
if a shape is a rectangle, then it is a square.
However, sometimes the converse of a true statement is also true.
For example, the Pythagorean theorem has a true converse: if a2 + b2 =
c2, then the triangle with sides a, b, and c is a right triangle. Whenever
you encounter an implication in mathematics, it is always reasonable to
ask whether the converse is true.
The contrapositive, on the other hand, always has the same truth value
as its original implication. This can be very helpful in deciding whether
an implication is true: often it is easier to analyze the contrapositive.

Example

True or false: If you draw any nine playing cards from a regular
deck, then you will have at least three cards all of the same suit.
Is the converse true?
Solution. True. The original implication is a little hard to analyze
because there are so many different combinations of nine cards. But
consider the contrapositive: If you don’t have at least three cards all
of the same suit, then you don’t have nine cards. It is easy to see
why this is true: you can at most have two cards of each of the
four suits, for a total of eight cards (or fewer).
 The converse: If you have at least three cards all of the same suit, then you have nine c

Understanding converses and contrapositives can help understand

implications and their truth values:

Example

Suppose I tell Sue that if she gets a 93% on her final, then she will
get an A in the class. Assuming that what I said is true, what can
you conclude in the following cases:
1. Sue gets a 93% on her final.
2. Sue gets an A in the class.
3. Sue does not get a 93% on her final.
4. Sue does not get an A in the class.

Solution. Note first that whenever P→Q and P are both true
statements, Q must be true as well. For this problem, take P to
mean “Sue gets a 93% on her final” and Q to mean “Sue will get
an A in the class.”

1. We have P → Q and P, so Q follows. Sue gets an A.

2. You cannot conclude anything. Sue could have gotten the A
because she did extra credit for example. Notice that we do
not know that if Sue gets an A, then she gets a 93% on her
final. That is the converse of the original implication, so it
might or might not be true.
3. The contrapositive of the converse of P Q is P Q,
→ ¬ →¬
which states that if Sue does not get a 93% on the final, then
she will not get an A in the class. But this does not follow from
the original implication. Again, we can conclude nothing. Sue
could have done extra credit.
4. What would happen if Sue does not get an A but did get a
93% on the final? Then P would be true and Q would be
false. This makes the implication P → Q false! It must be
that
 Sue did not get a 93% on the final. Notice now we have the
implication ¬Q → ¬P which is the contrapositive of P → Q.
Since P → Q is assumed to be true, we know ¬Q → ¬P is
true as well.

As we said above, an implication is not logically equivalent to its

converse, but it is possible that both the implication and its converse
are true. In this case, when both P Q and Q P are true, we say
→
that P and Q are equivalent and write P Q. This is the biconditional we
↔
mentioned earlier.
If and only if.
P ↔ Q is logically equivalent t
Example: Given an integer n, it is true that n is even if and only if n2 is even. That is, if

You can think of “if and only if” statements as having two parts: an
implication and its converse. We might say one is the “if” part, and
the other is the “only if” part. We also sometimes say that “if and only
if” statements have two directions: a forward direction ( P → Q and
a backwards direction (P ← Q, which is really just sloppy notation
) for
Q→ P).
Let’s think a little about which part is which. Is P
→Q the “if” part or
the “only if” part? Consider an example.

Example

Suppose it is true that I sing if and only if I’m in the shower. We know this means bo

statement, “I sing,” and Q be, “I’m in the shower.” So P → Q is the

statement “if I sing, then I’m in the shower.” Which part of the if and only if statemen
What we are really asking for is the meaning of “I sing if I’m in the shower” and “I sin

the shower, then I sing.” So the “if” part is Q → P. On the other

hand, to say, “I sing only if I’m in the shower” is equivalent to saying “if I sing, then I’m
 It is not terribly important to know which part is the “if” or “only if”
part, but this does illustrate something very, very important: there are many
ways to state an implication!

Example

Rephrase the implication, “if I dream, then I am asleep” in as

many different ways as possible. Then do the same for the
converse.
Solution. The following are all equivalent to the original implica-
tion:

1. I am asleep if I dream.
2. I dream only if I am asleep.
3. In order to dream, I must be asleep.
4. To dream, it is necessary that I am asleep.
5. To be asleep, it is sufficient to dream.
6. I am not dreaming unless I am asleep.

The following are equivalent to the converse (if I am asleep, then

I dream):

1. I dream if I am asleep.
2. I am asleep only if I dream.
3. It is necessary that I dream in order to be asleep.
4. It is sufficient that I be asleep in order to dream.
5. If I don’t dream, then I’m not asleep.

Hopefully you agree with the above example. We include the

“neces- sary and sufficient” versions because those are common when
discussing mathematics. In fact, let’s agree once and for all what they
mean.

Necessary and Sufficient.

“P is necessary for Q” means Q → P.
“P is sufficient for Q” means P → Q.
If P is necessary and sufficient for Q, then P ↔ Q.

To be honest, I have trouble with these if I’m not very careful. I find it
helps to keep a standard example for reference.

Example
 true (for example, f (x) = |x | at the point 0). Restate this fact using
“necessary and sufficient” language.
Thinking about the necessity and sufficiency of conditions can also help
when writingItproofs
Solution. is trueand
thatjustifying
in order for a function If
conclusions. toyou
be differentiable at a point c, it is ne
want to establish
It is true that to be continuous at a point c, it is sufficient that
some mathematical fact, it is helpful to think what other facts would be the function be differen
enough (be sufficient) to prove your fact. If you have an assumption, think
about what must also be necessary if that hypothesis is true.

Lesson 3: Predicates and Quantifiers

Investigate!
Consider the statements below. Decide whether any are equivalent to each other, or
You can fool some people all of the time.
You can fool everyone some of the time.
You can always fool some people.
Sometimes you can fool everyone.

! Attempt the above activity before proceeding !

It would be nice to use variables in our mathematical sentences. For
example, suppose we wanted to claim that if n is prime, then n + 7 is
not prime. This looks like an implication. I would like to write something
like

P(n) → ¬P(n + 7)
where P n means “n is prime.” But this is not quite right. For one
( )
thing, because this sentence has a free variable (that is, a variable that
we have not specified anything about), it is not a statement. A sentence
that contains variables is called a predicate.
Now, if we plug in a specific value for n, we do get a statement. In
fact, it turns out that no matter what value we plug in for n, we get a
true implication in this case. What we really want to say is that for all
values of n, if n is prime, then n + 7 is not. We need to quantify the
variable.
Although there are many types of quantifiers in English (e.g., many, few,
most, etc.) in mathematics we, for the most part, stick to two: existential
and universal.
Universal and Existential Quantifiers.
The existential quantifier is ∃ and is read “there exists” or “there is.”
For example,
∃x(x < 0)
asserts that there is a number less than 0.
The universal quantifier is ∀ and is read “for all” or “every.” For
example,
∀x(x ≥ 0)
asserts that every number is greater than or equal to 0.
 As with all mathematical statements, we would like to decide whether
quantified statements are true or false. Consider the statement

∀x∃y(y < x).

You would read this, “for every x there is some y such that y is less than x.”
Is this true? The answer depends on what our domain of discourse is:
when we say “for all” x, do we mean all positive integers or all real
numbers or all elements of some other set? Usually this information is
implied. In discrete mathematics, we almost always quantify over the
natural numbers, 0, 1, 2, . . . , so let’s take that for our domain of discourse
here.
For the statement to be true, we need it to be the case that no matter
what natural number we select, there is always some natural number that
is strictly smaller. Perhaps we could let y be x−1? But here is the problem:
what if x = 0? Then y = −1 and that is not a number! (in our domain of
discourse). Thus we see that the statement is false because there is a
number which is less than or equal to all other numbers. In symbols,

∃x∀y(y ≥ x).

To show that the original statement is false, we proved that the negation
was true. Notice how the negation and original statement compare.
This is typical.

Quantifiers and Negation.

¬∀xP(x) is equivalent to ∃x¬P(x).
¬∃xP(x) is equivalent to ∀x¬P(x).

Essentially, we can pass the negation symbol over a quantifier, but that
causes the quantifier to switch type. This should not be surprising: if
not everything has a property, then something doesn’t have that property.
And if there is not something with a property, then everything doesn’t
have that property.

Implicit Quantifiers.
It is always a good idea to be precise in mathematics. Sometimes
though, we can relax a little bit, as long as we all agree on a convention. An
example of such a convention is to assume that sentences containing
predicates with free variables are intended as statements, where the
variables are universally quantified.
For example, do you believe that if a shape is a square, then it is a
 rectangle? But how can that be true if it is not a statement? To be a little
more precise, we have two predicates: S(x) standing for “x is a square”
and R(x) standing for “x is a rectangle”. The sentence we are looking at is,

S(x) → R(x).

This is neither true nor false, as it is not a statement. But come on! We
all know that we meant to consider the statement,
∀x(S(x) → R(x)),
and this is what our convention tells us to consider.
Similarly, we will often be a bit sloppy about the distinction
between a predicate and a statement. For example, we might write,
( ) let P
n be the statement, “n is prime,” which is technically incorrect. It is
implicit that we mean that we are
( )defining P n to be a predicate, which
for each n becomes the statement, n is prime.

Exercises
1. For each sentence below, decide whether it is an atomic statement,
a molecular statement, or not a statement at all.
(a) Customers must wear shoes.
(b) The customers wore shoes.
(c) The customers wore shoes and they wore socks.
2. Classify each of the sentences below as an atomic statement, a
molecular statement, or not a statement at all. If the statement is
molecular, say what kind it is (conjunction, disjunction, conditional,
biconditional, negation).
(a) The sum of the first 100 odd positive integers.
(b) Everybody needs somebody sometime.
(c) The Broncos will win the Super Bowl or I’ll eat my hat.
(d) We can have donuts for dinner, but only if it rains.
(e) Every natural number greater than 1 is either prime or composite.
(f) This sentence is false.
3. Suppose P and Q are the statements: P: Jack passed math. Q: Jill
passed math.
(a) Translate “Jack and Jill both passed math” into symbols.
(b) Translate “If Jack passed math, then Jill did not” into symbols.
(c) Translate “P ∨ Q” into English.
(d) Translate “¬(P ∧ Q) → Q” into English.

(e) Suppose you know that if Jack passed math, then so did Jill.
 What can you conclude if you know that:

i. Jill passed math?

ii. Jill did not pass math?
4. Determine whether each molecular statement below is true or false, or
whether it is impossible to determine. Assume you do not know what
my favorite number is (but you do know that 13 is prime).
(a) If 13 is prime, then 13 is my favorite number.
(b) If 13 is my favorite number, then 13 is prime.
(c) If 13 is not prime, then 13 is my favorite number.
(d) 13 is my favorite number or 13 is prime.
(e) 13 is my favorite number and 13 is prime.
(f) 7 is my favorite number and 13 is not prime.
(g) 13 is my favorite number or 13 is not my favorite number.
5. In my safe is a sheet of paper with two shapes drawn on it in
colored crayon. One is a square, and the other is a triangle. Each
shape is drawn in a single color. Suppose you believe me when I tell
you that if the square is blue, then the triangle is green. What do you
therefore know about the truth value of the following statements?
(a) The square and the triangle are both blue.
(b) The square and the triangle are both green.
(c) If the triangle is not green, then the square is not blue.
(d) If the triangle is green, then the square is blue.
(e) The square is not blue or the triangle is green.

6. Again, suppose the statement “if the square is blue, then the
triangle is green” is true. This time however, assume the converse is
false. Classify each statement below as true or false (if possible).
(a) The square is blue if and only if the triangle is green.
(b) The square is blue if and only if the triangle is not green.
(c) The square is blue.
(d) The triangle is green.

7. Consider the statement, “If you will give me a cow, then I will give you
magic beans.” Decide whether each statement below is the
converse, the contrapositive, or neither.
(a) If you will give me a cow, then I will not give you magic beans.
 (b) If I will not give you magic beans, then you will not give me a
cow.
(c) If I will give you magic beans, then you will give me a cow.
(d) If you will not give me a cow, then I will not give you magic
beans.
(e) You will give me a cow and I will not give you magic beans.
(f) If I will give you magic beans, then you will not give me a cow.
8. Consider the statement “If Oscar eats Chinese food, then he drinks
milk.”
(a) Write the converse of the statement.
(b) Write the contrapositive of the statement.
(c) Is it possible for the contrapositive to be false? If it was, what
would that tell you?
(d) Suppose the original statement is true, and that Oscar drinks
milk. Can you conclude anything (about his eating Chinese
food)? Explain.
(e) Suppose the original statement is true, and that Oscar does
not drink milk. Can you conclude anything (about his eating
Chinese food)? Explain.
9. You have discovered an old paper on graph theory that discusses
the viscosity of a graph (which for all you know, is something
completely made up by the author). A theorem in the paper claims
that “if a graph satisfies condition (V), then the graph is viscous.”
Which of the following are equivalent ways of stating this claim?
Which are equivalent to the converse of the claim?
(a) A graph is viscous only if it satisfies condition (V).
(b) A graph is viscous if it satisfies condition (V).
(c) For a graph to be viscous, it is necessary that it satisfies condition
(V).
(d) For a graph to be viscous, it is sufficient for it to satisfy condition
(V).

(e) Satisfying condition (V) is a sufficient condition for a graph to

be viscous.
(f) Satisfying condition (V) is a necessary condition for a graph to
be viscous.
(g) Every viscous graph satisfies condition (V).
(h) Only viscous graphs satisfy condition (V).
 10. Write each of the following statements in the form, “if . . . , then......”
Careful, some of the statements might be false (which is alright for the
purposes of this question).
(a) To lose weight, you must exercise.
(b) To lose weight, all you need to do is exercise.
(c) Every American is patriotic.
(d) You are patriotic only if you are American.
(e) The set of rational numbers is a subset of the real numbers.
(f) A number is prime if it is not even.
(g) Either the Broncos will win the Super Bowl, or they won’t
play in the Super Bowl.
11. Which of the following statements are equivalent to the implication,
“if you win the lottery, then you will be rich,” and which are equivalent
to the converse of the implication?
(a) Either you win the lottery or else you are not rich.
(b) Either you don’t win the lottery or else you are rich.
(c) You will win the lottery and be rich.
(d) You will be rich if you win the lottery.
(e) You will win the lottery if you are rich.
(f) It is necessary for you to win the lottery to be rich.
(g) It is sufficient to win the lottery to be rich.
(h) You will be rich only if you win the lottery.
(i) Unless you win the lottery, you won’t be rich.
(j) If you are rich, you must have won the lottery.
(k) If you are not rich, then you did not win the lottery.
(l) You will win the lottery if and only if you are rich.

12. Let P(x) be the predicate, “3x + 1 is even.”

(a) Is P(5) true or false?
(b) What, if anything, can you conclude about ∃xP(x) from the truth
value of P(5)?
(c) What, if anything, can you conclude about ∀xP(x) from the truth
value of P(5)?
13. Let P(x) be the predicate, “4x + 1 is even.”
(a) Is P(5) true or false?
(b) What, if anything, can you conclude about ∃xP(x) from the truth
 value of P(5)?
(c) What, if anything, can you conclude about ∀xP(x) from the truth
value of P(5)?
14. For a given predicate P x , you might believe that the statements
xP x or xP x are either ( ) true or false. How would you decide if
∀ you( ) were
∃ correct
( ) in each case? You have four choices: you could
give an example of an element n in the domain for which P(n) is
true or for which P(n) if false, or you could argue that no matter
what n is,
P(n) is true or is false.
(a) What would you need to do to prove ∀xP(x) is true?
(b) What would you need to do to prove ∀xP(x) is false?
(c) What would you need to do to prove ∃xP(x) is true?
(d) What would you need to do to prove ∃xP(x) is false?
15. Suppose P x, y is some binary predicate defined on a very small
( )
domain of discourse: just the integers 1, 2, 3, and 4. For each of the
16 pairs of these numbers, P x, y is either true or false, according to
( )
the following table (x values are rows, y values are columns).
1 2 3 4
1 T F F F
2 F T T F
3 T T T T
4 F F F F
For example, P (1, 3) is false, as indicated by the F in the first row,
third column.
Use the table to decide whether the following statements are
true or false.
(a) ∀x∃yP(x, y).
 (b) ∀y∃xP(x, y).
(c) ∃x∀yP(x, y).
(d) ∃y∀xP(x, y).
16. Translate into symbols. Use E x for “x is even” and O x for “x is
( ) ( )
odd.”
(a) No number is both even and odd.
(b) One more than any even number is an odd number.
(c) There is prime number that is even.
(d) Between any two numbers there is a third number.
(e) There is no number between a number and one more than
that number.
17. Translate into English:
(a) ∀x(E(x) → E(x + 2)).
(b) ∀x∃y(sin(x) = y).
(c) ∀y∃x(sin(x) = y).
(d) ∀x∀y(x3 = y3 → x = y).
18. Suppose P x is some predicate for which the statement xP x is true.
( ) ∀ ( )
Is it also the case that xP x is true? In other words, is the statement
∃ ( )
xP x xP x always true? Is the converse always true? Assume
∀ ( )→∃ ( )
the domain of discourse is non-empty.
19. For each of the statements below, give a domain of discourse for which
the statement is true, and a domain for which the statement is false.
(a) ∀x∃y(y 2 = x).
(b) ∀x∀y(x < y → ∃z(x < z < y)).
(c) ∃x∀y∀z(y < z → y ≤ x ≤ z).
20. Consider the statement, “For all natural numbers n, if n is prime, then
n is solitary.” You do not need to know what solitary means for this
problem, just that it is a property that some numbers have and
others do not.
(a) Write the converse and the contrapositive of the statement,
saying which is which. Note: the original statement claims
that an implication is true for all n, and it is that implication
that we are taking the converse and contrapositive of.
 (b) Write the negation of the original statement. What would you
need to show to prove that the statement is false?
(c) Even though you don’t know whether 10 is solitary (in fact,
nobody knows this), is the statement “if 10 is prime, then 10 is
solitary” true or false? Explain.
(d) It turns out that 8 is solitary. Does this tell you anything about
the truth or falsity of the original statement, its converse or its
contrapositive? Explain.
(e) Assuming that the original statement is true, what can you
say about the relationship between the set P of prime numbers
and the set S of solitary numbers. Explain.

Lesson 4: Sets
The most fundamental objects we will use in our studies (and really in
all of math) are sets. Much of what follows might be review, but it is
very important that you are fluent in the language of set theory. Most
of the notation we use below is standard, although some might be a
little different than what you have seen before.
For us, a set will simply be an unordered collection of objects. Two
examples: we could consider the set of all actors who have played The
Doctor on Doctor Who, or the set of natural numbers between 1 and 10
inclusive. In the first case, Tom Baker is an element (or member) of the set,
while Idris Elba, among many others, is not an element of the set. Also,
the two examples are of different sets. Two sets are equal exactly if they
contain the exact same elements. For example, the set containing all of the
vowels in the declaration of independence is precisely the same set as
the set of vowels in the word “questionably” (namely, all of them); we
do not care about order or repetitions, just whether the element is in the
set or not.

Notation
We need some notation to make talking about sets easier. Consider,

A = {1, 2, 3}.

This is read, “A is the set containing the elements 1, 2 and 3.” We

use curly braces “{, }” to enclose elements of a set. Some more notation:

a ∈ {a, b, c}.
The symbol “ ” is read “is in” or “is an element of.” Thus the above
means that a is an∈element of the set containing the letters a, b, and c. Note
that this is a true statement. It would also be true to say that d is not in
that set:
 d g {a, b, c}.
Be warned: we write “x A” when we wish to express that one of the
∈
elements of the set A is x. For example, consider the set,

A = {1, b, {x, y, z}, ∅}.

This is a strange set, to be sure. It contains four elements: the
number 1, the letter b, the set x, y, z , and the empty set = , the set
{ Is x} in A? The answer ∅
containing no elements. {} None of the four
is no.
elements in A are the letter x, so we must conclude that x g A. Similarly,
consider the set B = {1, b}. Even though the elements of B are elements
of A, we cannot
say that the set B is one of the elements of A. Therefore B g A. (Soon we
will see that B is a subset of A, but this is different from being an element
of A.)
We have described the sets above by listing their elements. Sometimes
this is hard to do, especially when there are a lot of elements in the set
(perhaps infinitely many). For instance, if we want A to be the set of all
even natural numbers, would could write,

A = {0, 2, 4, 6, . . .},

but this is a little imprecise. A better way would be

A = {x ∈ N : ∃n ∈ N(x = 2n)}.
Let’s look at this carefully. First, there are some new symbols to digest:
“N” is the symbol usually used to denote that natural numbers, which we
will take to be the set 0, 1, 2, 3, Next, the colon, “:”, is read such that;
{ }
it separates the elements that are in the set from the condition that the
elements in the set must satisfy. So putting this all together, we would
read the set as, “the set of all x in the natural numbers, such that there
exists some n in the natural numbers for which x is twice n.” In other
words, the set of all natural numbers, that are even. Here is another
way to write the same set.

A = {x ∈ N : x is even}.
Note: Sometimes mathematicians use or э for the “such that” symbol
|
instead of the colon. Also, there is a fairly even split between
mathemati- cians about whether 0 is an element of the natural numbers,
so be careful there.
This notation is usually called set builder notation. It tells us how
to build a set by telling us precisely the condition elements must meet to
gain access (the condition is the logical statement after the “:” symbol).
Reading and comprehending sets written in this way takes practice. Here
are some more examples:

Example

Describe each of the following sets both in words and by listing out
enough elements to see the pattern.
 1. {x : x + 3 ∈ N}.
2. {x ∈ N : x + 3 ∈ N}.
3. {x : x ∈ N ∨ −x ∈ N}.
4. {x : x ∈ N ∧ −x ∈ N}.

Solution.
1. This is the set of all numbers which are 3 less than a natural number (i.e., that if

(note that 0 is a natural number, so −3 is in this set because

−3 + 3 = 0).
This is the set of all natural numbers which are 3 less than a natural number. S
This is the set of all integers (positive and negative whole numbers, written Z

4. Here we want all numbers x such that x and −x are natural

numbers. There is only one: 0. So we have the set {0}.

There is also a subtle variation on set builder notation. While the

condition is generally given after the “such that”, sometimes it is
hidden in the first part. Here is an example.

List a few elements in the sets below and describe them in words. The set Z is the
set of integers; positive and negative whole numbers.
1. A = {x ∈ Z : x2 ∈ N}
2. B = {x2 : x ∈ N}

Solution

1. The set of integers that pass the condition that their square is a natural number. Well,
every integer, when you square it, gives you a non-negative integer, so a natural number.
Thus A = Z = {. . . , −2, −1, 0, 1, 2, 3, . . .}.
2. Here we are looking for the set of all x2s where x is a natural number. So this set is
simply the set of perfect squares. B = {0, 1, 4, 9, 16, . . .}.

Another way we could have written this set, using more strict set builder notation,
would be as B = {x ∈ N : x = n2 for some n ∈ N}.
 We already have a lot of notation, and there is more yet. Below is a
handy chart of symbols. Some of these will be discussed in greater
detail as we move forward.
Special sets.

∅ The empty set is the set which contains no elements. The universe set is the
The set of natural numbers. That is, N = {0, 1, 2, 3 . . .}. The set of integers. T
U
The set of real numbers.
NZQ
R

P(A) The power set of any set A is the set of all subsets of A.

Set Theory Notation.

{, } We use these braces to enclose the elements of a set. So

{1, 2, 3} is the set containing 1, 2, and 3.
: {x : x > 2} is the set of all x such that x is greater than 2.
∈ 2 ∈ {1, 2, 3} asserts that 2 is an element of the set {1, 2, 3}.
g 4 g {1, 2, 3} because 4 is not an element of the set {1, 2, 3}.
A B asserts that A is a subset of B: every element of A
⊆ is also an element of B.
A B asserts that A is a proper subset of B: every
⊂ element of A is also an element of B, but A ≠ B.
A B is the intersection of A and B: the set containing
∩ all elements which are elements of both A and B.
A B is the union of A and B: is the set containing
∪ all elements which are elements of A or B or both.
× A × B is the Cartesian product of A and B: the set of
all ordered pairs (a, b) with a ∈ A and b ∈ B.
A B is set difference between A and B: the set
\ containing all elements of A which are not elements of B.
\
A The complement of A is the set of everything which is
not an element of A.
A The cardinality (or size) of A is the number of elements in
| |
A.
Investigate!
Find the cardinality of each set below. (a) A = {3, 4, . . . , 15}.
(b) B = {n ∈ N : 2 < n ≤ 200}.
(c) C = {n ≤ 100 : n ∈ N ∧ ∃m ∈ N(n = 2m + 1)}.
Find two sets A and B for which |A| = 5, |B| = 6, and

|A ∪ B| = 9. What is |A ∩ B|?

3. Find sets A and B with |A| = |B| such that |A ∪ B| = 7 and

|A ∩ B| = 3. What is |A|?

4. Let A = {1, 2, . . . , 10}. Define B2 = {B ⊆ A : |B| = 2}. Find

|B2|.

5. For any sets A and B, define AB = {ab : a ∈ A ∧ b ∈ B}. If

A = {1, 2} and B = {2, 3, 4}, what is |AB|? What is |A × B|?

! Attempt the above activity before proceeding !

Lesson 5: Relationship Between Sets

We have already said what it means for two sets to be equal: they have
exactly the same elements. Thus, for example,

{1, 2, 3} = {2, 1, 3}.

(Remember, the order the elements are written down in does not
matter.) Also,

{1, 2, 3} = {1, 1 + 1, 1 + 1 + 1} = {I , II , III} = {1, 2, 3, 1 + 2}

since these are all ways to write the set containing the first three
positive integers (how we write them doesn’t matter, just what they
are).
{ 2, 3, 4 } ? Clearly A ≠ B,
What about the sets A = {1, 2, 3 } and B = 1,
but notice that every element of A is also an element of B. Because of
this we say that A is a subset of B, or in symbols
⊂ A B or A B. Both
symbols are read “is a subset of.” The difference is that sometimes we
want to say that A is either equal to or is a subset of B, in which case we
use ⊆. This is analogous to the difference between < and ≤.

Example

1. A ⊂ B.
2. B ⊂ A.
3. B ∈ C.

Solution.
Let A = {1, 2, 3, 4, 5, 6 }, B = {2, 4, 6 }, C = {1, 2, 3 } and D = {7, 8, 9 }.
Determine which of the following are true, false, or meaningless.
1. A ⊂ 4. ∅ ∈ A. 7. 3 ∈ C.
B. 5. ∅ ⊂ A. 8. 3 ⊂ C.
2. B ⊂ 6. A < D. 9. {3} ⊂ C.
A.
3. B ∈ C.

Solution.

1. False. For example, 1 ∈ A but 1 g B.

2. True. Every element in B is an element in A.
3. False. The elements in C are 1, 2, and 3. The set B is not
equal to 1, 2, or 3.
4. False. A has exactly 6 elements, and none of them are the
empty set.
5. True. Everything in the empty set (nothing) is also an element
of A. Notice that the empty set is a subset of every set.
6. Meaningless. A set cannot be less than another set.
7. True. 3 is one of the elements of the set C.
8. Meaningless. 3 is not a set, so it cannot be a subset of
another set.
9. True. 3 is the only element of the set {3}, and is an element of
C, so every element in {3} is an element of C.
 In the example above, B is a subset of A. You might wonder what other
sets are subsets of A. If you collect all these subsets of A into a new set, we
get a set of sets. We call the set of all subsets of A the power set of A,
and write it P(A).

Example 0.3.4

Let A = {1, 2, 3}. Find P(A).

Solution. P(A) is a set of sets, all of which are subsets of A. So

P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
 Notice that while 2 ∈A, it is wrong to write 2 ∈ P(A) since none
of the elements in P(A) are numbers! On the other hand, we do
have {2} ∈ P(A) because {2} ⊆ A.
What does a subset of P(A) look like? Notice that {2} ¢ P(A)
because not everything in {2} is in P(A). But we do have {{2}} ⊆
P(A). The only element of {{2}} is the set {2} which is also an
element of P(A). We could take the collection of all subsets of P(A)
and call that P(P(A)). Or even the power set of that set of sets of
sets.

Another way to compare sets is by their size. Notice that in the example
above, A has 6 elements and B, C, and D all have 3 elements. The size of a
set is called the set’s cardinality . We would write | |A = 6,| B| = 3, and so
on. For sets that have a finite number of elements, the cardinality of the set
is simply the number of elements in the set. Note that the cardinality of
1,
{ 2, 3, 2, 1 } is 3. We do not count repeats (in fact, {1, 2, 3, 2, 1} is exactly
the same set as {1, 2, 3 }). There are sets with infinite cardinality, such as N,
the set of rational numbers (written Q), the set of even natural numbers,
and the set of real numbers ( R). It is possible to distinguish between
different infinite cardinalities, but that is beyond the scope of this text. For
us, a set will either be infinite, or finite; if it is finite, the we can determine
its cardinality by counting elements.

Example 0.3.5

Find the cardinality of A = {23, 24, . . . , 37, 38}.

Find the cardinality of B = {1, {2, 3, 4}, ∅}.
If C = {1, 2, 3}, what is the cardinality of P(C)?
Solution.
1. Since 38 − 23 = 15, we can conclude that the cardinality of the

set is |A| = 16 (you need to add one since 23 is included).

2. Here |B| = 3. The three elements are the number 1, the set
{2, 3, 4}, and the empty set.
3. We wrote out the elements of the power set P(C) above, and
there are 8 elements (each of which is a set). So |P(C)| = 8.
(You might wonder if there is a relationship between |A| and
|P(A)| for all sets A. This is a good question which we will
return to in .)
 Operations On Sets
Is it possible to add two sets? Not really, however there is something
similar. If we want to combine two sets to get the collection of objects that
are in either set, then we can take the union of the two sets.
Symbolically,

C = A ∪ B,

read, “C is the union of A and B,” means that the elements of C are exactly
the elements which are either an element of A or an element of B (or an
element of both). For example, if A = {1, 2, 3} and B = {2, 3, 4} , then
A∪ B = 1,{2, 3, 4 . }
The other common operation on sets is intersection. We write,

C=A∩B

and say, “C is the intersection of A and B,” when the elements in C are
precisely those both in A and in B. So if A = {1, 2, 3} and B = 2, { 3, 4 },
then A ∩B = 2,{3 . }
Often when dealing with sets, we will have some understanding as
to what “everything” is. Perhaps we are only concerned with natural
numbers. In this case we would say that our universe is N. Sometimes
we denote this universe by U . Given this context, we might wish to
speak of all the elements which are not in a particular set. We say B is the
complement of A, and write,

B =A

when B contains every element not contained in A. So, if our universe

{ is 1, 2, . . . , 9,}10 , and A {= 2, 3, 5, 7} , then A = 1,
{ 4, 6, 8, 9, 10 .}
Of course we can perform more than one operation at a time. For
example, consider
A ∩ B.
This is the set of all elements which are both elements of A and not
elements of B. What have we done? We’ve started with A and removed
all of the elements which were in B. Another way to write this is the set
difference:
A ∩ B = A \ B.
It is important to remember that these operations (union,
intersection, complement, and difference) on sets produce other sets.
Don’t confuse these with the symbols from the previous section
(element of and subset of). A ∩ B is a set, while A ⊆ B is true or false.
This is the same difference as between 3 + 2 (which is a number) and 3 ≤
2 (which is false).
 Example 0.3.6

Let A = {1, 2, 3, 4, 5, 6}, B = {2, 4, 6}, C = {1, 2, 3} and D = {7, 8, 9}.

If the universe is U = {1, 2, . . . , 10}, find:
1. A ∪ B. 4. A ∩ 7. (D ∩ C)∪ A ∩ B.
2. A ∩ B. D. 8. ∅ ∪ C.
3. B ∩ C. 5. B ∪ C. 9. ∅ ∩ C.
6. A \ B.
Solution.

1. A B = 1, 2, 3, 4, 5, 6 = A since everything in B is already

in ∪
A. { }

2. A ∩ B = {2, 4, 6} = B since everything in B is in A.

3. B ∩ C = {2} as the only element of both B and C is 2.
4. A ∩ D = ∅ since A and D have no common elements.
5. B ∪ C = {5, 7, 8, 9, 10} . First we find that B ∪C = 1,
{ 2, 3, 4, 6 ,}
then we take everything not in that set.
6. A \ B = {1, 3, 5} since the elem ents 1, 3, and 5 are in A but
not in B. This is the same as A ∩ B.

7. (D ∩ C) ∪ A ∩ B = {1, 3, 5, 7, 8, 9, 10}. The set contains all

elements that are either in D but not in C (i.e., {7, 8, 9}), or not
in both A and B (i.e., {1, 3, 5, 7, 8, 9, 10}).
8. ∅ ∪ C = C since nothing is added by the empty set.
9. ∅ ∩ C = since nothing can be both in a set and in the empty
set.

Having notation like this is useful. We will often want to add or remove
elements from sets, and our notation allows us to do so precisely.

Example 0.3.7

If A = {1, 2, 3}, then we can describe the set we get by adding

the number 4 as A ∪ {4}. If we want to express the set we get by
removing the number 2 from A we can do so by writing A \ {2}.
Careful though. If you add an element to the set, you get a new
set! So you would have B = A ∪ {4} and then correctly say that B
contains 4, but A does not.
 You might notice that the symbols for union and intersection
slightly resemble the logic symbols for “or” and “and.” This is no
accident. What does it mean for x to be ∪ an element of A B? It means
that x is an element of A or x is an element of B (or both). That is,

x ∈A∪B ⇔ x ∈ A ∨ x ∈ B.

Similarly,

x ∈A∩B ⇔ x ∈A∧x ∈
Also,

B. x ∈ A ⇔ ¬(x ∈ A).
which says x is an element of the complement of A if x is not an element
of A.
There is one more way to combine sets which will be useful for us: the
Cartesian product, A×B. This sounds fancy but is nothing you haven’t
seen before. When you graph a function in calculus, you graph it in
the Cartesian plane. This is the set of all ordered pairs of real numbers
x,
( y .) We can do this for any pair of sets, not just the real numbers with
themselves.
Put another way, A× B = {(a, b ): a ∈A ∧b ∈B }. The first coordinate
comes from the first set and the second coordinate comes from the second
set. Sometimes we will want to take the Cartesian product of a set with
itself, and this is fine: A ×A = {(a, b ) : a, b ∈A } (we might also write A2
for this set). Notice that in A×A, we still want all ordered pairs, not just
the ones where the first and second coordinate are the same. We can also
take products of 3 or more sets, getting ordered triples, or quadruples,
and so on.
Example 0.3.8

Let A = {1, 2} and B = {3, 4, 5}. Find A × B and A × A. How many

elements do you expect to be in B × B?
Solution. A × B = {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}.
A × A = A2 = {(1, 1), (1, 2), (2, 1), (2, 2)}.
|B × B| = 9. There will be 3 pairs with first coordinate 3, three
more with first coordinate 4, and a final three with first coordinate 5.

Venn Diagrams
There is a very nice visual tool we can use to represent operations on
sets. A Venn diagram displays sets as intersecting circles. We can shade
the region we are talking about when we carry out an operation. We
can
also represent cardinality of a particular set by putting the number in
the corresponding region.

AB A B

C
Each circle represents a set. The rectangle containing the circles
represents the universe. To represent combinations of these sets, we shade
the corresponding region. For example, we could draw A ∩ B as:

AB

Here is a representation of A ∩ B, or equivalently A \ B:

AB

A more complicated example is (B ∩ C) ∪ (C ∩ A), as seen below.

A B

C
Notice that the shaded regions above could also be arrived at in another
way. We could have started with all of C, then excluded the region where
C and A overlap outside of B. Th at region is ( A ∩ C) ∩ B. So the

above
Venn diagram also represents C ∩ (
.we have determined that A ∩ C) ∩ B

So using just the picture,

(B ∩ C) ∪ (C ∩ A) = C ∩ (A ∩ C) ∩ B .
 Exercises
1. Let A = {1, 4, 9} and B = {1, 3, 6, 10}. Find each of the following sets.
(a) A ∪ B.
(b) A ∩ B.
(c) A \ B.
(d) B \ A.
2. Find the least element of each of the following sets, if there is one.
(a) {n ∈ N : n2 − 3 ≥ 2}.
(b) {n ∈ N : n2 − 5 ∈ N}.
(c) {n2 + 1 : n ∈ N}.
(d) {n ∈ N : n = k2 + 1 for some k ∈ N}.
3. Find the following cardinalities:
(a) |A| when A = {4, 5, 6, . . . , 37}.
(b) |A| when A = {x ∈ Z : −2 ≤ x ≤ 100}.
(c) |A ∩ B| when A = {x ∈ N : x ≤ 20} and B = {x ∈ N : x is prime}.

4. Find a set of largest possible size that is a subset of both {1, 2, 3, 4, 5}

and {2, 4, 6, 8, 10}.
5. Find a set of smallest possible size that has both {1, 2, 3, 4, 5} and
{2, 4, 6, 8, 10} as subsets.
6. Let A = { n ∈ N : 20 ≤ n < 50} and B = { n ∈ N : 10 < n ≤ 30} .
Suppose C is a set such that C ⊆ A and C B. What is the largest
possible cardinality of C?

7. Let A = {1, 2, 3, 4, 5} and B = {2, 3, 4}. How many sets C have

the property that C ⊆ A and B ⊆ C.

8. Let A = {1, 2, 3, 4, 5}, B = {3, 4, 5, 6, 7}, and C = {2, 3, 5}.

(a) Find A ∩ B.
(b) Find A ∪ B.
(c) Find A \ B.
(d) Find A ∩ (B ∪ C).
9. Let A = {x ∈ N : 4 ≤ x < 12} and B = {x ∈ N : x is even}.
(a) Find A ∩ B.
(b) Find A \ B.
10. Let A = {x ∈ N : 3 ≤ x ≤ 13}, B = {x ∈ N : x is even}, and
C = {x ∈ N : x is odd}.
(a) Find A ∩ B.
(b) Find A ∪ B.
(c) Find B ∩ C.
(d) Find B ∪ C.
11. Find an example of sets A and B such that A ∩ B = {3, 5} and
A ∪ B = {2, 3, 5, 7, 8}.
12. Find an example of sets A and B such that A ⊆ B and A ∈ B.
13. Recall Z = .{ . . , − − 0, 1, 2, . . . }(the integers). Let Z = 1,{2, 3, . . . be}
2, 1, +

the positive integers. Let 2Z be the even integers, 3Z be the multiples

of 3, and so on.
(a) Is Z+ ⊆ 2Z? Explain.
(b) Is 2Z ⊆ Z+? Explain.
(c) Find 2Z ∩ 3Z. Describe the set in words, and using set notation.
(d) Express { x ∈ Z : ∃ y ∈ Z (x = 2y ∨ x = 3y )} as a union or
intersection of two sets already described in this problem.
14. Let A2 be the set of all multiples of 2 except for 2. Let A3 be the set of
all multiples of 3 except for 3. And so on, so that An is the set of all
multiples of n except for n, for any n ≥ 2. Describe (in words) the
set A2 ∪ A3 ∪ A4 ∪ · · ·.
15. Draw a Venn diagram to represent each of the following:
(a) A ∪ B
(b) (A ∪ B)
(c) A ∩ (B ∪ C)
(d) (A ∩ B) ∪ C
(e) A ∩ B ∩ C
(f) (A ∪ B) \ C
16. Describe a set in terms of A and B (using set notation) which has the
following Venn diagram:
A B
17. Let A = {a, b, c, d}. Find P(A).
18. Let A = 1,
{ 2, . . . , 10 }. How many subsets of A contain exactly one
element (i.e., how many singleton subsets are there)? singleton set
How many doubleton subsets (containing exactly two elements)
are there? doubleton set
19. Let A = {1, 2, 3, 4, 5, 6}. Find all sets B ∈ P(A) which have the property
{2, 3, 5} ⊆ B.
20. Find an example of sets A and B such that |A| = 4, |B| = 5, and
|A ∪ B| = 9.
21. Find an example of sets A and B such that |A| = 3, |B| = 4, and
|A ∪ B| = 5.
22. Are there sets A and B such that |A| = |B|, |A ∪ B| = 10, and |A ∩ B| = 5?
Explain.
23. Let A = {2, 4, 6, 8}. Suppose B is a set with |B| = 5.
(a) What are the smallest and largest possible values of |A ∪ B ?
Explain. |
(b) What are the smallest and largest possible values of |A ∩ B ?
Explain. |
(c) What are the smallest and largest possible values of |A × B ?
Explain. |
24. Let X = { n ∈ N : 10 ≤ n < 20 .} Find examples of sets with the
properties below and very briefly explain why your examples
work.
(a) A set A ⊆ N with |A| = 10 such that X \ A = {10, 12, 14}.
(b) A set B ∈ P(X) with |B| = 5.
(c) A set C ⊆ P(X) with |C| = 5.
(d) A set D ⊆ X × X with |D | = 5
(e) A set E ⊆ X such that |E| ∈ E.
25. Let A, B and C be sets.
(a) Suppose that A ⊆ B and B ⊆ C. Does this mean that A ⊆ C?
Prove your answer. Hint: to prove that A ⊆ C you must prove
the implication, “for all x, if x ∈ A then x ∈ C.”
(b) Suppose that A ∈ B and B ∈ C. Does this mean that A C?
Give an example to prove that
∈ this does NOT always happen
(and explain why your example works). You should be able to
give an example where |A| = |B| = |C| = 2.
26. In a regular deck of playing cards there are 26 red cards and 12
face cards. Explain, using sets and what you have learned about
cardinalities, why there are only 32 cards which are either red or a
face card.
27. Find an example of a set A with | | A = 3 which contains only other
sets and has the following property: for all sets
∈ B A, we also have B
A. Explain why your example works. (FYI: sets that have this
property are called transitive.)
28. Consider the sets A and B, where A = {3, |B |} and B = {1, |A ,| B| .
What are the sets? |}
29. Explain why there is no set A which satisfies A = {2, |A|}.
30. Find all sets A, B, and C which satisfy the following.

A ={1, |B| , |C|}

B ={2, |A| , |C|}
C ={1, 2, |A| , |B|}.
 0.4. FUnctIons

Functions
A function is a rule that assigns each input exactly one output. We call the
output the image of the input. The set of all inputs for a function is
called the domain. The set of all allowable outputs is called the
codomain. We would → write f : X Y to describe a function with name f ,
domain X and codomain Y. This does not tell us which function f is
though. To define the function, we must describe the rule. This is often
done by giving a formula to compute the output for any input
(although this is certainly not the only way to describe the rule).
For example, consider the function f : N → N defined by f ( x) = x2 + 3.
Here the domain and codomain are the same set (the natural numbers).
The rule is: take your input, multiply it by itself and add 3. This works
because we can apply this rule to every natural number (every element of
the domain) and the result is always a natural number (an element of
the codomain). Notice though that not every natural number is actually
an output (there is no way to get 0, 1, 2, 5, etc.). The set of natural
numbers that are outputs is called the range of the function (in this case,
the{ range is 3, 4, 7, 12,} 19, 28, . . . , all the natural numbers that are 3
more than a perfect square).
The key thing that makes a rule a function is that there is exactly one
output for each input. That is, it is important that the rule be a good
rule. What output do we assign to the input 7? There can only be one
answer for any particular function.

Example 0.4.1

The following are all examples of functions:

1. f : Z →Z defined by f n( )= 3n. The domain and codomain are
both the set of integers. However, the range is only the set of
integer multiples of 3.
2. g : { 1, 2, 3} → { a, b, c} defined by g (1 ) = c, g (2) = a and
g (3) = a. The domain is the set { 1, 2, 3} , the codomain is the
set {a, b, c } and the range is the set { a, c} . Note that g(2 and
g (3 ))are the same element of the codomain. This is okay since
each element in the domain still has only one output.
3. h : {1, 2, 3, 4} → N defined by the table:

x 1 2 3 4
h(x) 3 6 9 12
Here the domain is the finite set {1, 2, 3, 4} and to codomain
is the set of natural numbers, N. At first you might think
this
 0.4. FUnctIons

function is the same as f defined above. It is absolutely not. Even though the rule is th

Example 0.4.2

Just because you can describe a rule in the same way you would write a function, do
1.

f : N → N defined by f (n) =. nThe2 reason this is not a

function is because not every input has an output. Where
3 3
does f send 3? The rule says that f (3) =, 2butis not
2 an
element of the codomain.
2. Consider the rule that matches each person to their phone number. If you think

Describing Functions
It is worth making a distinction between a function and its description.
The function is the abstract mathematical object that in some way exists
whether or not anyone ever talks about it. But when we do want to talk
about the function, we need a way to describe it. A particular function can
be described in multiple ways.
Some calculus textbooks talk about the Rule of Four, that every function
can be described in four ways: algebraically (a formula), numerically (a
table), graphically, or in words. In discrete math, we can still use any of
these to describe functions, but we can also be more specific since we
are primarily concerned with functions that have N or a finite subset of N
as their domain.
Describing a function graphically usually means drawing the graph of
the function: plotting the points on the plane. We can do this, and
might get a graph like the following for a function f : {1, 2, 3} → {1, 2,
3}.
 0.4. FUnctIons

It would be absolutely WRONG to connect the dots or try to fit them to

some curve. There are only three elements in the domain. A curve
would mean that the domain contains an entire interval of real
numbers.
Here is another way to represent that same function:
1 2 3

1 2 3
This shows that the function f sends 1 to 2, 2 to 1 and 3 to 3: just follow
the arrows.
The arrow diagram used to define the function above can be very
helpful in visualizing functions. We will often be working with functions
with finite domains, so this kind of picture is often more useful than a
traditional graph of a function.
Note that for finite domains, finding an algebraic formula that gives
the output for any input is often impossible. Of course we could use a
piecewise defined function, like

x+1 if x = 1
f (x) = .
 x − 1 if x = 2
 x if x = 3


This describes exactly the same function as above, but we can all agree is a
ridiculous way of doing so. 
Since we will so often use functions with small domains and
codomains, let’s adopt some notation to describe them. All we need is
some clear way of denoting the image of each element in the domain. In
fact, writing a table of values would work perfectly:

x 0 1 2 3 4
f (x) 3 3 2 4 1
We simplify this further by writing this as a “matrix” with each input
directly over its output:

0 1 2 3 4
= 3 3 2 4 1 .
f
 0.4. FUnctIons

Note this is just notation and not the same sort of matrix you would find in
a linear algebra class (it does not make sense to do operations with
these matrices, or row reduce them, for example).
One advantage of the two-line notation over the arrow diagrams is
that it is harder to accidentally define a rule that is not a function using
two-line notation.

Example 0.4.3

Which of the following diagrams represent a function? Let X =

{1, 2, 3, 4} and Y = {a, b, c, d}.
f :X→Y g:X→Y h:X→ Y
1 2 3 1 2 3 4 1 2 3 4
4

a b c a c a c
b b d
d d

Solution. f is a function. So is g. There is no problem with an

element of the codomain not being the image of any input, and
there is no problem with a from the codomain being the image of
both 2 and 3 from the domain. We could use our two-line notation
to write these as

1 2 3 4 1 2 3 4
f = d a c g= d a a .
b b

However, h is NOT a function. In fact, it fails for two reasons.

First, the element 1 from the domain has not been mapped to any
element from the codomain. Second, the element 2 from the domain
has been mapped to more than one element from the codomain (a
and c). Note that either one of these problems is enough to make
a rule not a function. In general, neither of the following
mappings are functions:

It might also be helpful to think about how you would write the
two-line notation for h. We would have something like:

1 2 3 4
= a, c? d b .
h
There is nothing under 1 (bad) and we needed to put more than one
thing under 2 (very bad). With a rule that is actually a function, the
two-line notation will always “work”.
 0.4. FUnctIons

We will also be interested in functions with domain N. Here two-

line notation is no good, but describing the function algebraically is
often possible. Even tables are a little awkward, since they do not
describe the function completely. For example, consider the function
→ f :N
N given by the table below.

x 0 1 2 3 4 5 ...
f (x) 0 1 4 9 16 25 ...
Have I given you enough entries for you to be able to determine f( 6) ?
You might guess that f (6 )= 36, but there is no way for you to know this for
sure. Maybe I am being a jerk and intended f( 6) = 42. In fact, for every
natural number n, there is a function that agrees with the table above, but
for which f (6 )= n.
Okay, suppose I really did mean for f( 6) = 36, and in fact, for the rule
that you think is governing the function to actually be the rule. Then
I should say what that rule is. f( n) = n2. Now there is no confusion
possible.
Giving an explicit formula that calculates the image of any element
in the domain is a great way to describe a function. We will say that
these explicit rules are closed formulas for the function.
There is another very useful way to describe functions whose domain
is N, that rely specifically on the structure of the natural numbers. We can
define a function recursively!

Example 0.4.4

Consider the function f : N → N given by f (0) = 0 and f (n + 1) =

f (n) + 2n + 1. Find f (6).
Solution. The rule says that f 6( )= f 5 (+) 11 (we are using 6 = n + 1 so
n = 5). We don’t know what f 5 is ( )though. Well, we know that f 5
= (f 4) + 9. (So) we need to compute f 4 , which( will ) require knowing
f 3 , which (will ) require f 2 ,. . . will it
( )ever end?
Yes! In fact, this process will always end because we have N as
our domain, so there is a least element. And we gave the value of
f (0) explicitly, so we are good. In fact, we might decide to work up
to f (6) instead of working down from f (6):

f (1) = f (0) + 1 = 0+1=1

f (2) = f (1) + 3 = 1+3=4
f (3) = f (2) + 5 = 4+5=9
f (4) = f (3) + 7 = 9 + 7 = 16
f (5) = f (4) + 9 = 16 + 9 = 25
 0.4. FUnctIons

f (6) = f (5) + 11 = 25 + 11 = 36

It looks that this recursively defined function is the same as the

explicitly defined function f (n) = n2. Is it? Later we will prove that
it is.

Recursively defined functions are often easier to create from a “real

world” problem, because they describe how the values of the functions
are changing. However, this comes with a price. It is harder to calculate
the image of a single input, since you need to know the images of other
(previous) elements in the domain.
Recursively Defined Functions.

For a function f : N → N, a recursive definition consists of an

initial condition together with a recurrence relation. The initial
condition is the explicitly given value of f (0). The recurrence relation
is a formula for f (n + 1) in terms for f (n) (and possibly n itself).

Example 0.4.5

Give recursive definitions for the functions described below.

1. f : N → N gives the number of snails in your terrarium n
years after you built it, assuming you started with 3 snails and
the number of snails doubles each year.
2. g : N →N gives the number of push-ups you do n days after
you started your push-ups challenge, assuming you could do
7 push-ups on day 0 and you can do 2 more push-ups each
day.
3. h : N → N defined by h( n) = n!. Recall that n! = 1 ·2 ·3 · · · ·
( n −1 n·) is the product of all numbers from 1 through n. We
also
· define 0! = 1.

Solution.

1. The initial condition is f( 0) = 3. To get f (n + 1) we would

double the number of snails in the terrarium the previous
year, which is given by f ( n). Thus f (n + 1 ) = 2 f ( n) . The
full recursive definition contains both of these, and would
be written,
f (0) = 3; f (n + 1) = 2 f (n).
 0.4. FUnctIons

2. We are told that on day 0 you can do 7 push-ups, so g(0) = 7.

The number of push-ups you can do on day n + 1 is 2 more
than the number you can do on day n, which is given by g(n).
Thus
g(0) = 7; g(n + 1) = g(n) + 2.

3. Here h(0) = 1. To get the recurrence relation, think about how

you can get h(n + 1) = (n + 1)! from h(n) = n!. If you write out
both of these as products, you see that (n + 1)! is just like n!
except you have one more term in the product, an extra n + 1. So we have,
h(0) = 1; h(n + 1) = (n + 1) · h(n).

Surjections, Injections, and Bijections

We now turn to investigating special properties functions might or might
not possess.
In the examples above, you may have noticed that sometimes there are
elements of the codomain which are not in the range. When this sort of the
thing does not happen, (that is, when everything in the codomain is in
the range) we say the function is onto or that the function maps the
domain onto the codomain. This terminology should make sense: the
function puts the domain (entirely) on top of the codomain. The fancy
math term for an onto function is a surjection, and we say that an onto
function is a surjective function.
In pictures:

Surjective Not surjective

Example 0.4.6

Which functions are surjective (i.e., onto)?

1. f : Z → Z defined by f (n) = 3n.
1 2 3
2. g : { 1, 2, 3} → {a, b, c } defined by g = .
c a a
3. h : {1, 2, 3} → {1, 2, 3} defined as follows:
 0.4. FUnctIons

1 2 3

1 2

Solution.
1. f is not surjective. There are elements in the codomain which

are not in the range. For example, no n ∈ Z gets mapped to

the number 1 (the rule would say that 13 would be sent to 1,
but 13 is not in the domain). In fact, the range of the function
is 3Z (the integer multiples of 3), which is not equal to Z.
2. g is not surjective. There is no x ∈ {1, 2, 3} (the domain) for
which g(x) = b, so b, which is in the codomain, is not in the
range. Notice that there is an element from the codomain “missing” from the bo
3. h is surjective. Every element of the codomain is also in the range. Nothing in

To be a function, a rule cannot assign a single element of the domain

to two or more different elements of the codomain. However, we have
seen that the reverse is permissible: a function might assign the same
element of the codomain to two or more different elements of the domain.
When this does not occur (that is, when each element of the codomain is
the image of at most one element of the domain) then we say the function
is one-to-one. Again, this terminology makes sense: we are sending at
most one element from the domain to one element from the codomain.
One input to one output. The fancy math term for a one-to-one function is
an injection. We call one-to-one functions injective functions.
In pictures:

Injective Not injective

Example 0.4.7

Which functions are injective (i.e., one-to-one)?

1. f : Z → Z defined by f (n) = 3n.
 0.4. FUnctIons

123
2. g : {1, 2, 3} → {a, b, c} defined by g = caa .
1 2

3. h : {1, 2, 3} → {1, 2, 3} defined as follows:

3 1 2

Solution.
1. f is injective. Each element in the codomain is assigned to at
most one element from the domain. If x is a multiple of three,

then only x/3 is mapped to x. If x is not a multiple of 3, then

there is no input corresponding to the output x.
g is not injective. Both inputs 2 and 3 are assigned the output
a. Notice that there is an element from the codomain that appears more than onc
h is injective. Each output is only an output once.

Be careful: “surjective” and “injective” are NOT opposites. You can see
in the two examples above that there are functions which are surjective but
not injective, injective but not surjective, both, or neither. In the case when
a function is both one-to-one and onto (an injection and surjection), we
say the function is a bijection, or that the function is a bijective
function.
To illustrate the contrast between these two properties, consider a more
formal definition of each, side by side.
Injective vs Surjective.
A function is injective provided every element of the codomain is the image of at most on
A function is surjective provided every element of the codomain is the image of at least

Notice both properties are determined by what happens to elements of

the codomain: they could be repeated as images or they could be “missed”
(not be images). Injective functions do not have repeats but might or might
not miss elements. Surjective functions do not miss elements, but might
 0.4. FUnctIons

or might not have repeats. The bijective functions are those that do not
have repeats and do not miss elements.

Image and Inverse Image

When discussing functions, we have notation for talking about an element
of the domain (say x) and its corresponding element in the codomain
(we write( ) f x , which is the image of x). Sometimes we will want to talk
about all the elements that are images of some subset of the domain. It
would also be nice to start with some element of the codomain (say y)
and talk about which element or elements (if any) from the domain it is
the image of. We could write “those x in the domain (such ) that f x = y,”
but this is a lot of writing. Here is some notation to make our lives
easier.
To address the first situation, what we are after is a way to describe
the set of images of elements in some subset of the domain. Suppose
f : X→ Y is a function and that A X is some subset of the domain
(possibly all of it). We will use the notation f( A) to denote the image of A
under f , namely the set of elements in Y that are the image of elements
from A. That is, f (A )= f {a Y( :) a∈A . ∈ }
We can do this in the other direction as well. We might ask which
elements of the domain get mapped to a particular set in the codomain. Let
f : X →Y be a function and suppose B Y is a subset of the codomain.
−
Then we will write f 1 ( B) for the inverse image of B under f , namely
the set of elements in X whose image are elements in B. In other words,
−
f 1 (B )= x{ X∈: f x B (. ) ∈ }
Often we are interested in the element(s) whose image is a
−
particular element y of in the codomain. The notation above works: ({ }) f 1
y is the set of all elements in the domain that f sends to y. It makes
sense to think of this as a set: there might not be anything sent to y (if y
({ })case f −1 y = . Or f might send multiple
is not in the range), in which
elements to y (if f is not injective). As a notational convenience, we
usually drop the set braces around the( y) and write f 1 y instead for this
−

set.
−
WARNING: f 1(y )is not an inverse function! Inverse functions only
−
exist for bijections, but f 1( y) is defined for any function f . The point:
f 1(y )is a set, not an element of the domain. This is just sloppy notation
−

for f 1({y }). To help make this distinction, we would call f 1( y) the
− −

−
complete inverse image of y under f . It is not the image of y under f 1
−
(since the function f 1 might not exist).
 0.4. FUnctIons

Example 0.4.8

Consider the function f : {1, 2, 3, 4, 5, 6} → {a, b, c, d} given by

123456
f = aabbbc .

Find f ({1, 2, 3}), f −1({a, b}), and f −1(d).

Solution. f ({1, 2, 3}) = {a, b} since a and b are the elements in the
codomain to which f sends 1 and 2.
f −1({a, b}) = {1, 2, 3, 4, 5} since these are exactly the elements
that f sends to a and b.
f −1(d) = ∅ since d is not in the range of f .

Example 0.4.9

Consider the function g : Z → Z defined by g(n) = n2 + 1. Find

− − −
g(1) and g({1}). Then find g 1(1), g 1(2), and g 1(3).
Solution. Note that g( 1) ≠ g ({1 .})The first is an element: g 1( =
)
2. The second is a set: g 1 = 2 .
− ({ }) { }
To find g 1(1), we need to find all integers n such that n2 + 1 = 1.
−
Clearly only 0 works, so g 1(1 )= 0{ (note
} that even though there
is only one element, we still write it as a set with one element in it).
−
To find g 1(2 ), we need to find all n such that n2 + 1 = 2. We see
−1
g ( 2) = {−1, 1}.
Finally, if n2 + 1 = 3, then we are looking for an n such that
−
n2 = 2. There are no such integers so g 1(3) = ∅.

− −. ( ). number of
Since f 1 y( is) a set, it makes sense to ask for f 1 y , the
elements in the domain which map to y.

Example 0.4.10

. f −1 .
Find a function f : {1, 2, 3, 4, 5} → N such that (7) = 5.

Solution. There is only one such function. We need five elements

of the domain to map to the number 7 ∈ N. Since there are only five
elements in the domain, all of them must map to 7. So

1 2 3 4 5
f = 7 7 7 7 7.
 0.4. FUnctIons

Function Definitions.
Here is a summary of all the main concepts and definitions we use
when working with functions.

• A function is a rule that assigns each element of a set, called the

domain, to exactly one element of a second set, called the codomain.
• Notation: f : X→Y is our way of saying that the function is called
f , the domain is the set X, and the codomain is the set Y.
• To specify the rule for a function with small domain, use two-line
notation by writing a matrix with each output directly below its
corresponding input, as in:

1 2 3 4
= 2 1 3 1 .
f

• f (x )= y means the element x of the domain (input) is assigned to

the element y of the codomain. We say y is an output. Alternatively,
we call y the image of x under f .
• The range is a subset of the codomain. It is the set of all elements
which are assigned to at least one element of the domain by the
function. That is, the range is the set of all outputs.
• A function is injective (an injection or one-to-one) if every
element of the codomain is the image of at most one element from
the domain.
• A function is surjective (a surjection or onto) if every element of
the codomain is the image of at least one element from the
domain.
• A bijection is a function which is both an injection and surjection.
In other words, if every element of the codomain is the image of
exactly one element from the domain.
• The image of an element x in the domain is the element y in the
codomain that x is mapped to. That is, the image of x under f is
f (x).
• The complete inverse image of an element y in the codomain,
−
( ) f 1 y , is the set of all elements in the domain which are
written
assigned to y by the function.
• The image of a subset A of the domain is the set f (A) = { f (a) ∈ Y :
a ∈ A}.
−1
• The inverse image of a subset B of the codomain is the set f (B) =
{x ∈ X : f (x) ∈ B}.
 0.4. FUnctIons

Exercises
1. Consider the function f : {1, 2, 3, 4} → {1, 2, 3, 4} given by

41 21 33 44
f (n) = .

(a) Find f (1).

(b) Find an element n in the domain such that f (n) = 1.
(c) Find an element n of the domain such that f (n) = n.
(d) Find an element of the codomain that is not in the range.
2. The following functions all have {1, 2, 3, 4, 5} as both their domain and
codomain. For each, determine whether it is (only) injective, (only)
surjective, bijective, or neither injective nor surjective.
1 2 3 4 5
(a) = 3 3 3 3 3 .
f
1 2 3 4 5
(b) = 2 3 1 5 4 .
f
(c) f (x) = 6 − x.
(
x/2 if x is even
(d) f (x ) = .
(x + 1)/2 if x is odd

3. The following functions all have domain {1, 2, 3, 4, 5} and codomain

1,
{ 2, 3} . For each, determine whether it is (only) injective, (only)
surjective, bijective, or neither injective nor surjective.
1 2 3 4 5
(a) = 1 2 1 2 1 .
f
1 2 3 4 5
(b) = 1 2 3 1 2 .
f
(
x if x ≤ 3
(c) f x = .
( )
x−3 if x > 3

4. The following functions all have domain {1, 2, 3, 4} and codomain

1,
{ 2, 3, 4, 5}. For each, determine whether it is (only) injective, (only)
surjective, bijective, or neither injective nor surjective.
1 2 3 4
(a) = .
f 1 2 5 4
 0.4. FUnctIons

1 2 3 4
(b) = .
1 2 3f 2
(c) f (x )gives the number of letters in the English word for the
number x. For example, f ( 1) = 3 since “one” contains three
letters.
5. Write out all functions f :{ 1, 2,} 3→ {a, b } (using two-line notation).
How many functions are there?
How many are injective?
How many are
surjective? How many
are bijective?

6. Write out all functions f : { 1, 2} → {a, b, c }(in two-line notation).

How many functions are there?
How many are injective?
How many are
surjective? How many
are bijective?
7. Consider the function f : {1, 2, 3, 4, 5} → {1, 2, 3, 4}given by the table
below:
x 1 2 3 4 5
f (x) 3 2 4 1 2

(a) Is f injective? Explain.

(b) Is f surjective? Explain.
(c) Write the function using two-line notation.
8. Consider the function f : {1, 2, 3, 4} → {1, 2, 3, 4}given by the graph
below.
f (x)
4

1 2
3 4 x

(a) Is f injective? Explain.

(b) Is f surjective? Explain.
(c) Write the function using two-line notation.
9. Consider the function f : N → N given recursively by f (0) = 1 and
f (n + 1) = 2 · f (n). Find f (10).
 0.4. FUnctIons

10. Suppose f : N → N satisfies the recurrence f( n + 1) = f( n) + 3. Note

that this is not enough information to define the function, since we
don’t have an initial condition. For each of the initial conditions below,
find the value of f (5).
(a) f (0) = 0.
(b) f (0) = 1.
(c) f (0) = 2.
(d) f (0) = 100.
11. Suppose f : N → N satisfies the recurrence relation
(
f ( n)
f (n + 1) = 2 if f (n) is even
.
3 f (n) + 1 if f (n) is odd

Note that with the initial condition f(0) = 1, the values of the function
are: f 1( =
) 4, f 2 (=)2, f 3 =( 1,) f 4 = 4,
( )and so on, the images cycling
through those three numbers. Thus f is NOT injective (and also
certainly not surjective). Might it be under other initial conditions?3
(a) If f satisfies the initial condition f( 0) = 5, is f injective? Explain
why or give a specific example of two elements from the domain
with the same image.
(b) If f satisfies the initial condition f( 0) = 3, is f injective? Explain
why or give a specific example of two elements from the domain
with the same image.
(c) If f satisfies the initial condition f (0) = 27, then it turns out that
f (105 )= 10 and no two numbers less than 105 have the same
image. Could f be injective? Explain.
(d) Prove that no matter what initial condition you choose, the
function cannot be surjective.

12. For each function given below, determine whether or not the function
is injective and whether or not the function is surjective.
(a) f : N → N given by f (n) = n + 4.
(b) f : Z → Z given by f (n) = n + 4.
(c) f : Z → Z given by f (n) = 5n − 8.
3It turns out this is a really hard question to answer in general. The Collatz
conjecture is that no matter what the initial condition is, the function will eventually
produce 1 as an output. This is an open problem in mathematics: nobody knows the
answer.
 0.4. FUnctIons

( /
n 2 if n is even
(d) f : Z Z given by f ( n) =
→
(n + 1)/2 if n is odd.
13. Let A = {1, 2, 3, . . . , 10} . Consider the function f : P( A) → N given
by f (B ) = |B |. That is, f takes a subset of A as an input and outputs
the cardinality of that set.
(a) Is f injective? Prove your answer.
(b) Is f surjective? Prove your answer.
−1
(c) Find f (1).
−1
(d) Find f (0).
−1
(e) Find f (12).
14. Let X = {n ∈N : 0 ≤ n ≤ 999} be the set of all numbers with three
or fewer digits. Define the function f : X→N by f abc( = a + b + c,
where a, b, and c are the digits of the number in X) (write numbers
less than 100 with leading 0’s to make them three digits). For example,
f (253) = 2 + 5 + 3 = 10.
(a) Let A = {n ∈ X : 113 ≤ n ≤ 122}. Find f (A).
−1
(b) Find f ({1, 2})
−1
(c) Find f (3).
−1
(d) Find f (28).
(e) Is f injective? Explain.
(f) Is f surjective? Explain.

15. Consider the set N2 = N × N, the set of all ordered pairs (a, b) where a
and b are natural numbers. Consider a function f : N2 → N given by
f ((a, b)) = a + b.
(a) Let A = {(a, b) ∈ N2 : a, b ≤ 10}. Find f (A).
−1 −1
(b) Find f (3) and f ({0, 1, 2, 3}).
− −1
(c) Give geometric descriptions of f 1(n) and f ({0, 1, . . . , n}) for
any n ≥ 1.
. − . . − .
(d) Find f 1(8) and f 1({0, 1, . . . , 8}) .

16. Let f : X → Y be some function. Suppose 3 ∈ Y. What can you say

−
about f 1(3) if you know,
(a) f is injective? Explain.
(b) f is surjective? Explain.
 0.4. FUnctIons

(c) f is bijective? Explain.

−1 −1
17. Find a set X and a function f : X → N so that f (0) ∪ f (1) = X.
18. What can you deduce about the sets X and Y if you know,
(a) there is an injective function f : X → Y? Explain.
(b) there is a surjective function f : X → Y? Explain.
(c) there is a bijective function f : X → Y? Explain.
19. Suppose f : X → Y is a function. Which of the following are possible?
Explain.
(a) f is injective but not surjective.
(b) f is surjective but not injective.
(c) |X | = |Y | and f is injective but not surjective.
(d) |X | = |Y | and f is surjective but not injective.
(e) |X | = |Y |, X and Y are finite, and f is injective but not surjective.
(f) |X | = |Y |, X and Y are finite, and f is surjective but not injective.
20. Let f : X → Y and g : Y Z be functions. We can define the
composition of f and g to be the function g ◦f : X → Z for which
the image of each x ∈ X is g ( f (x )) . That is, plug x into f , then plug
the result into g (just like composition in algebra and calculus).
(a) If f and g are both injective, must g ◦ f be injective? Explain.
(b) If f and g are both surjective, must g ◦ f be surjective? Explain.
(c) Suppose g ◦ f is injective. What, if anything, can you say about
f and g? Explain.
(d) Suppose g ◦ f is surjective. What, if anything, can you say about
f and g? Explain.
(
n + 1 if
21. Consider the function f : Z Z given by f n =
n is even → ( )

n−3 if n is odd.
(a) Is f injective? Prove your answer.
(b) Is f surjective? Prove your answer.
22. At the end of the semester a teacher assigns letter grades to each of
her students. Is this a function? If so, what sets make up the domain
and codomain, and is the function injective, surjective, bijective, or
neither?
 0.4. FUnctIons

23. In the game of Hearts, four players are each dealt 13 cards from a deck
of 52. Is this a function? If so, what sets make up the domain and
codomain, and is the function injective, surjective, bijective, or neither?
24. Seven players are playing 5-card stud. Each player initially receives
5 cards from a deck of 52. Is this a function? If so, what sets make
up the domain and codomain, and is the function injective, surjective,
bijective, or neither?
25. Consider the function f : N →N that gives the number of handshakes
that take place in a room of n people assuming everyone shakes hands
with everyone else. Give a recursive definition for this function.

26. Let f : X → Y be a function and A ⊆ X be a finite subset of the

domain. What can you say about the relationship between |A| and
. .f (A) ? Consider both the general case and what happens
know f is injective, surjective, or bijective.
when you
27. Let f : X → Y be a function and B ⊆ Y be a finite subset of the
..codoma
−1 .f .
in. What can you say about the relationship between |B| and
(B) ? Consider both the general case and what
know
happens when you surjective, or
f is injective,
bijective.
28. Let f : X → Y be a function, A ⊆ X and B ⊆
Y. (a) Is f f (A) = A? Always, sometimes, never? Explain.
−1
−1
(b) Is f f (B) = B? Always, sometimes, never? Explain.
(c) If one or both of the above do not always hold, is there something
else you can say? Will equality always hold for particular
types of functions? Is there some other relationship other than
equality that would always hold? Explore.
29. Let f : X → Y be a function and A, B ⊆ X be subsets of the domain.
(a) Is f (A∪B) = f (A)∪ f (B)? Always, sometimes, or never? Explain.
(b) Is f (A∩B) = f (A)∩ f (B)? Always, sometimes, or never? Explain.
30. Let f : X → Y be a function and A, B ⊆ Y be subsets of the codomain.
− −1 −1
(a) Is f 1( A∪B )= f ( A) ∪
f B( ?) Always, sometimes, or never?
Explain.
− −1 −1
(b) Is f 1( A∩B )= f ( A) ∩
f B( ?) Always, sometimes, or never?
Explain.
4. ∅ ∈ A. 7. 3 ∈ C.
5. ∅ ⊂ A. 8. 3 ⊂ C.
6. A < D. 9. {3} ⊂ C.
0.4. FUnctIons