Book Reference: Chapter 2 & Chapter 9

Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
Sets
 A set is an unordered collection of objects.

 S = {a,b,c,d} //roster method

 S = {a,b,c,d} = {b,c,a,d} and, S = {a,b,c,d} = {a,b,c,b,c,d}
 S = {x | P(x)} //set-builder notation
 [a,b) = {x | a ≤ x < b} //interval notation
 closed interval [a,b], open interval (a,b)

 The universal set = U, Empty set = ∅ or, {} //∅ ≠ { ∅ }

 Set A and Set B are equal if and only if:
 A ⊆ B holds if and only if is true.
 If, A ⊆ B and, B ⊆ A, then A and B are equal.
 Proper subset: If A ⊆ B, but A ≠B
Sets (Continued)
 Cardinality: |A| = number of (distinct) elements of A.
 Power Sets: set of all subsets of a set, P(A)
 If |A| =n, then |P(A)| =2ⁿ.
 The ordered n-tuple is the ordered collection: (a1,a2,…..,an)
 2-tuples are called ordered pairs.
 Ordered pairs (a,b) and (c,d) are equal iff a = c and, b = d.
 A × B is the set of ordered pairs (a,b) // cartesian product
 If, A = {a,b} B = {1,2,3},
then A × B = {(a,1),(a,2),(a,3), (b,1),(b,2),(b,3)}
 Q: What is A × B × C if, A = {0,1}, B = {1,2} and C = {0,1,2}
Union, Intersection, Complement,
Difference
 A ∪ B, is the set:
 A ∩ B, is
 if A ∩ B is empty, then A and B are said to be disjoint.
 Complement of A, Ā = {x ∈ U | x ∉ A}
 A – B = {x | x ∈ A  x ∉ B} = A ∩B // difference
 |A ∪ B| = |A| + | B| − |A ∩ B| //cardinality of union
 = //symmetric diff
Review Questions
Example: U = {0,1,2,3,4,5,6,7,8,9,10} A = {1,2,3,4,5}, B ={4,5,6,7,8}
1. A∪B
Solution: {1,2,3,4,5,6,7,8}
2. A ∩ B
Solution: {4,5}
3. Ā
Solution: {0,6,7,8,9,10}
4.
Solution: {0,1,2,3,9,10}
5. A – B
Solution: {1,2,3}
6. B – A
Solution: {6,7,8}
Set Identities
Set-Builder Notation: Second De
Morgan Law
Functions
Definition: A function f from A to B, denoted f: A → B is
an assignment of each element of A to exactly one element
of B.

• A formula, f(x) = x + 1 is function

Students Grades
• A computer program can be a
function A
Carlota Rodriguez
B
• Two functions are equal when they
have the same domain, the same Sandeep Patel C
codomain and map each element
of the domain to the same element Jalen Williams D
of the codomain.
F
Kathy Scott
Review Questions
Injections
Definition: A function f is said to be one-to-one , or
injective, if and only if f(a) = f(b) implies that a = b for
all a and b in the domain of f. A function is said to be
an injection if it is one-to-one.
A B
a x

v
b
y
c
z
d

w
Surjections
Definition: A function f from A to B is called onto or
surjective, if and only if for every element
there is an element with . A
function f is called a surjection if it is onto.

A B
a x

b
y
c
z
d
Bijections
Definition: A function f is a one-to-one
correspondence, or a bijection, if it is both one-to-one
and onto (surjective and injective).

A B
a x

b
y
c

d z

w
Showing that f is one-to-one or onto
Example 1: Let f be the function from {a,b,c,d} to
{1,2,3} defined by f(a) = 3, f(b) = 2, f(c) = 1, and f(d) =
3. Is f an onto function?
Solution: Yes, f is onto since all three elements of the
codomain are images of elements in the domain. If the
codomain were changed to {1,2,3,4}, f would not be
onto.
Example 2: Is the function f(x) = x2 from the set of
integers to the set of integers onto?
Solution: No, f is not onto because there is no integer
x with x2 = −1, for example.
Inverse Functions
Definition: Let f be a bijection from A to B. Then the
inverse of f, denoted , is the function from B to A
defined as
No inverse exists unless f is a bijection. Why?
Questions
Example 1: Let f be the function from {a,b,c} to {1,2,3}
such that f(a) = 2, f(b) = 3, and f(c) = 1. Is f invertible
and if so what is its inverse?

Solution: The function f is invertible because it is a

one-to-one correspondence. The inverse function f-1
reverses the correspondence given by f, so f-1 (1) = c,
f-1 (2) = a, and f-1 (3) = b.
Questions
Example 2: Let f: Z → Z be such that f(x) = x + 1. Is f
invertible, and if so, what is its inverse?

Solution: The function f is invertible because it is a

one-to-one correspondence. The inverse function f-1
reverses the correspondence so f-1 (y) = y – 1.
Questions
Example 3: Let f: R → R be such that . Is f
invertible, and if so, what is its inverse?

Solution: The function f is not invertible because it

is not one-to-one .
Composition
 Definition: Let f: B → C, g: A → B. The composition of
f with g, denoted is the function from A to C
defined by
Composition
Example 1: If and ,
then

and
Composition Questions
Example 2: Let f and g be functions from the set of
integers to the set of integers defined by f(x) = 2x + 3
and g(x) = 3x + 2.
What is the composition of f and g, and also the
composition of g and f ?
Solution:
f∘g (x)= f(g(x)) = f(3x + 2) = 2(3x + 2) + 3 = 6x + 7
g∘f (x)= g(f(x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11
Sequences
 Sequences are ordered lists of elements.
Recurrence Relations
Definition: A recurrence relation for the sequence {an} is an
equation that expresses an in terms of one or more of the
previous terms of the sequence.

Example 1: Let {an} be a sequence that satisfies the

recurrence relation an = an-1 + 3 for n = 1,2,3,4,…. and
suppose that a0 = 2. What are a1 , a2 and a3?
[Here a0 = 2 is the initial condition.]

Solution: We see from the recurrence relation that

a1 = a0 + 3 = 2 + 3 = 5
a2 = 5 + 3 = 8
a3 = 8 + 3 = 11
Questions about Recurrence Relations
Example 2: Let {an} be a sequence that satisfies the
recurrence relation an = an-1 – an-2 for n = 2,3,4,….
and suppose that a0 = 3 and a1 = 5. What are a2 and
a3?
[Here the initial conditions are a0 = 3 and a1 = 5. ]

Solution: We see from the recurrence relation that

a2 = a1 - a0 = 5 – 3 = 2
a3 = a2 – a1 = 2 – 5 = –3
Fibonacci Sequence
Definition: Define the Fibonacci sequence, f0 ,f1 ,f2,…, by:
 Initial Conditions: f0 = 0, f1 = 1
 Recurrence Relation: fn = fn-1 + fn-2

Example: Find f2 ,f3 ,f4 , f5 and f6 .

Answer:
f2 = f1 + f0 = 1 + 0 = 1,
f3 = f2 + f1 = 1 + 1 = 2,
f4 = f3 + f2 = 2 + 1 = 3,
f5 = f4 + f3 = 3 + 2 = 5,
f6 = f5 + f4 = 5 + 3 = 8.
Finding Closed form equation using
forward substitution
Technique: Working upward, forward substitution
Example: Let {an} be a sequence that satisfies the
recurrence relation an = an-1 + 3 for n = 2,3,4,…. and
suppose that a1 = 2.
a2 = 2 + 3
a3 = (2 + 3) + 3 = 2 + 3 ∙ 2
a4 = (2 + 2 ∙ 3) + 3 = 2 + 3 ∙ 3
.
.
.
an = an-1 + 3 = (2 + 3 ∙ (n – 2)) + 3 = 2 + 3(n – 1)
Questions on Special Integer
Sequences
Example 1: Find formulae for the sequences with the
following first five terms: 1, ½, ¼, 1/8, 1/16
Solution: Note that the denominators are powers of 2. The
sequence with an = 1/2n is a possible match. This is a
geometric progression with a = 1 and r = ½.

Example 2: 1,3,5,7,9
Solution: Note that each term is obtained by adding 2 to
the previous term. A possible formula is an = 2n + 1.
This is an arithmetic progression with a =1 and d = 2.
Guessing Sequences
Example 3: Conjecture a simple formula for an if the
first 10 terms of the sequence {an} are 1, 7, 25, 79, 241,
727, 2185, 6559, 19681, 59047.

Solution: Note the ratio of each term to the previous

approximates 3. So now compare with the sequence
3n . We notice that the nth term is 2 less than the
corresponding power of 3. So a good conjecture is
that an = 3n − 2.

[You can prove this using mathematical induction.]

Binary Relations
Definition: A binary relation R from a set A to a set B
is a subset R ⊆ A × B.
Example:
 Let A = {0,1,2} and B = {a,b}
 {(0, a), (0, b), (1,a) , (2, b)} is a relation from A to B.
 We can represent relations from a set A to a set B
graphically or using a table:
Relations are more general than
functions. A function is a relation
where exactly one element of B is
related to each element of A.
Reflexive Relations
Definition: R is reflexive if and only if
∀x[x∊U ⟶ (x,x) ∊ R]
Example: The following relations on the integers are
reflexive:
If A = ∅ then the empty relation is
R1 = {(a,b) | a ≤ b}, reflexive vacuously. That is the empty
R3 = {(a,b) | a = b or a = −b}, relation on an empty set is reflexive!

R4 = {(a,b) | a = b}.
The following relations are not reflexive:
R2 = {(a,b) | a > b} (note that 3 ≯ 3),
R5 = {(a,b) | a = b + 1} (note that 3 ≠3 + 1),
R6 = {(a,b) | a + b ≤ 3} (note that 4 + 4 ≰ 3).
Symmetric Relations
Definition: R is symmetric if and only if
∀x∀y [(x,y) ∊R ⟶ (y,x) ∊ R]
Example: The following relations on the integers are
symmetric:
R3 = {(a,b) | a = b or a = −b},
R4 = {(a,b) | a = b},
R6 = {(a,b) | a + b ≤ 3}.
The following are not symmetric:
R1 = {(a,b) | a ≤ b} (note that 3 ≤ 4, but 4 ≰ 3),
R2 = {(a,b) | a > b} (note that 4 > 3, but 3 ≯ 4),
R5 = {(a,b) | a = b + 1} (note that 4 = 3 + 1, but 3 ≠4 + 1).
Antisymmetric Relations
Definition:R is antisymmetric if and only if
∀x∀y [(x,y) ∊R ∧ (y,x) ∊ R ⟶ x = y]
 Example: The following relations on the integers are
antisymmetric:
For any integer, if a a ≤ b and
R1 = {(a,b) | a ≤ b}, a ≤ b , then a = b.
R2 = {(a,b) | a > b},
R4 = {(a,b) | a = b},
R5 = {(a,b) | a = b + 1}.
The following relations are not antisymmetric:
R3 = {(a,b) | a = b or a = −b}
(note that both (1,−1) and (−1,1) belong to R3),
R6 = {(a,b) | a + b ≤ 3} (note that both (1,2) and (2,1) belong to
R6).
Transitive Relations
Definition: R is transitive if and only if
∀x∀y ∀z[(x,y) ∊R ∧ (y,z) ∊ R ⟶ (x,z) ∊ R ]
 Example: The following relations on the integers are
transitive:
R1 = {(a,b) | a ≤ b}, For every integer, a ≤ b
and b ≤ c, then b ≤ c.
R2 = {(a,b) | a > b},
R3 = {(a,b) | a = b or a = −b},
R4 = {(a,b) | a = b}.
The following are not transitive:
R5 = {(a,b) | a = b + 1} (note that both (3,2) and (4,3) belong to
R5, but not (3,3)),
R6 = {(a,b) | a + b ≤ 3} (note that both (2,1) and (1,2) belong to
R6, but not (2,2)).
Combining and, Composition
 Given two relations R1 and R2, we can combine them
using basic set operations to form new relations such
as R1 ∪ R2, R1 ∩ R2, R1 − R2, and R2 − R1.
 The composition (or composite) of R2 with R1, is a
relation from A to C where if (x,y) is a member of R1
and (y,z) is a member of R2, then (x,z) is a member of
R2∘ R1.
Representing the Composition of a
Relation
R1 m R2 w
a
x
n
b
y
o
c
p z

R1∘ R2 = {(b,x),(b,z)}
Representing Relations Using
Matrices
 A relation between finite sets can be represented using
a zero-one matrix.
 Suppose R is a relation from A = {a1, a2, …, am} to
B = {b1, b2, …, bn}.
 The relation R is represented by the matrix
MR = [mij], where
Examples of Representing
Relations Using Matrices
Example 1: Suppose that A = {1,2,3} and B = {1,2}. Let
R be the relation from A to B containing (a,b) if a ∈ A,
b ∈ B, and a > b. What is the matrix representing R?
Solution: Because R = {(2,1), (3,1),(3,2)}, the matrix is
Matrices of Relations on Sets
 If R is a reflexive relation, all the elements on the main
diagonal of MR are equal to 1.

 R is a symmetric relation, if and only if mij = 1

whenever mji = 1. R is an antisymmetric relation, if
and only if mij = 0 or mji = 0 when i≠ j.
Example of a Relation on a Set
Example 2: Suppose that the relation R on a set is
represented by the matrix

Is R reflexive, symmetric, and/or antisymmetric?

Solution: Because all the diagonal elements are equal
to 1, R is reflexive. Because MR is symmetric, R is
symmetric and not antisymmetric because both m1,2
and m2,1 are 1.
Equivalence Relations
Definition 1: A relation on a set A is called an
equivalence relation if it is reflexive, symmetric, and
transitive.

Definition 2: Two elements a, and b that are related

by an equivalence relation are called equivalent. The
notation a ∼ b is often used to denote that a and b are
equivalent elements with respect to a particular
equivalence relation.
Exercises
1. Determine whether each of these functions is a bijection from R to R.

a) 𝑓(𝑥) = −3𝑥 2 + 7
b) 𝑓(𝑥) = (𝑥 + 1)/(𝑥 + 2)
c) 𝑓(𝑥) = 𝑥3

2. Determine whether each of these functions from Z to Z is one-to-one.

a) 𝑓(𝑛) = 𝑛3
b) 𝑓(𝑚, 𝑛) = 𝑚2 + 𝑛2

3. Why is f not a function from R to R if:

a) 𝑓(𝑥) = 1/𝑥
b) 𝑓(𝑥) = 𝑥
c) 𝑓(𝑥) = ∓ 𝑥 2 + 1
Exercises
 Determine whether the relation R on the set of all real
numbers is reflexive, symmetric, antisymmetric,
and/or transitive, where(x,y)∈R if and only if:
 (x-y) is a rational number.
 x*y >= 0
 Determine whether the relation R on the set of all
integer numbers is reflexive, symmetric,
antisymmetric, and/or transitive, where(x,y)∈R if and
only if:
 x ≡ y (mod 7)
 x = 𝑦2