MAT103

DISCRETE
MATHEMATICS
UNIT 3 PART 2
(REFERENCE: DISCRETE MATHEMATICS AND ITS APPLICATIONS
BY KENNETH H. ROSEN)
Mary Ann Ritzell P. Vega, Ph.D.
Department of Mathematics and Statistics
CSM, MSU-Iligan Institute of Technology
EQUIVALENCE RELATIONS
EXAMPLE 1. Let R be the relation on the set of integers such that aRb if and
only if a = b or a = −b. This relation R has been shown to be reflexive,
symmetric, and transitive. It follows that R is an equivalence relation.
EXAMPLE 2 . Let R be the relation on the set of real numbers such that aRb if
and only if a − b is an integer. Is R an equivalence relation?
Solution: Because a −a = 0 is an integer for all real numbers a, aRa for all real
numbers a. Hence, R is reflexive.
Now suppose that aRb. Then a −b is an integer, so b−a is also an integer.
Hence, bRa. It follows that R is symmetric.
If aRb and bRc, then a −b and b−c are integers. Therefore, a −c = (a −b) +
(b−c) is also an integer. Hence, aRc. Thus, R is transitive.
Consequently, R is an equivalence relation.
Combining Relations
Because relations from A to B are subsets of A × B, two relations from A to B
can be combined in any way two sets can be combined.
EXAMPLE 1.
Combining Relations
EXAMPLE 2.
Combining Relations
EXAMPLE 3.
Composite of two Relations
DEFINITION Let R be a relation from a set A to a set B and S a relation from B
to a set C. The composite of R and S is the relation consisting of ordered
pairs (a, c), where a ∈ A, c ∈ C, and for which there exists an element b ∈ B
such that (a, b) ∈ R and (b, c) ∈ S. We denote the composite of R and S by
S∘R.
EXAMPLE .
Powers of a Relation
Powers of a Relation
EXAMPLE.

The following theorem shows that the powers of a transitive relation are subsets of this
relation.
THEOREM
FUNCTIONS
Let A and B be nonempty sets. A function 𝑓 from A to B is an
◦ DEFINITION
assignment of exactly one element of B for each element of A. We write
𝑓 𝑎 = 𝑏 if b is the unique element of B assigned by the function 𝑓 to the
element 𝑎 of A. If f is a function from A to B, we write 𝑓 : A → B.
◦ Remark: Functions are sometimes also called mappings or transformations.

◦ A function 𝑓 : A → B can also be defined in terms of a relation from A to B.

Recall that a relation from A to B is just a subset of A × B. A relation from A
to B that contains one, and only one, ordered pair (a, b) for every element
a ∈ A, defines a function 𝑓 from A to B. This function is defined by the
assignment 𝑓(a) = b, where (a, b) is the unique ordered pair in the
relation that has a as its first element.
FUNCTIONS
◦ DEFINITIONS. If 𝑓 is a function from A to B, we say that A is the domain of
𝑓 and B is the codomain of f. If f (a) = b, we say that b is the image of a and
a is a preimage of b. The range, or image, of 𝑓 is the set of all images of
elements of A.
◦ Also, if 𝑓 is a function from A to B, we say that 𝑓 maps A to B.
FUNCTIONS
◦ When we define a function we specify its domain, its codomain, and the
mapping of elements of the domain to elements in the codomain. Two
functions are equal when they have the same domain, have the same
codomain, and map each element of their common domain to the same
element in their common codomain. Note that if we change either the
domain or the codomain of a function, then we obtain a different function.
If we change the mapping of elements, then we also obtain a different
function.
Examples
◦ 1. Let R be the relation with ordered pairs (Abdul, 22), (Brenda, 24),
(Carla, 21), (Desiree, 22), (Eddie, 24), and (Felicia, 22). Here each pair
consists of a graduate student and this student’s age. Specify a function
determined by this relation.
◦ If f is a function specified by R, then f (Abdul ) = 22, f (Brenda) = 24, f (Carla) = 21,
f(Desiree) = 22, f (Eddie) = 24, and f (Felicia) = 22. (Here, f (x) is the age of x, where x
is a student.) For the domain, we take the set {Abdul, Brenda, Carla, Desiree, Eddie,
Felicia}. We also need to specify a codomain, which needs to contain all possible ages of
students. Because it is highly likely that all students are less than 100 years old, we can
take the set of positive integers less than 100 as the codomain. Using this codomain will
also allow us to extend the function by adding the names and ages of more students later.)
The range of the function we have specified is the set of different ages of these students,
which is the set {21, 22, 24}.
Examples
◦ 2. Let f be the function that assigns the last two bits of a bit string of length
2 or greater to that string. For example, f (11010) = 10. Then, the domain
of f is the set of all bit strings of length 2 or greater, and both the codomain
and range are the set {00, 01, 10, 11}.
◦ 3. Let f : Z → Z assign the square of an integer to this integer. Then,
𝑓(𝑥) = 𝑥 2 , where the domain of f is the set of all integers, the codomain
of f is the set of all integers, and the range of f is the set of all integers that
are perfect squares, namely, {0, 1, 4, 9, . . . }.
◦ A function is called real-valued if its codomain is the set of real numbers,
and it is called integer-valued if its codomain is the set of integers. Two
real-valued functions or two integer-valued functions with the same
domain can be added, as well as multiplied.
SUM and PRODUCT of FUNCTIONS
◦ DEFINITION Let 𝑓1 and 𝑓2 be functions from A to R. Then 𝑓1 + 𝑓2 and 𝑓1 𝑓2 are also functions
from A to R defined for all x ∈ A by
◦ (𝑓1 + 𝑓2 )(x) = 𝑓1 (x) + 𝑓2 (x) , and (𝑓1 𝑓2 )(x) = 𝑓1 (x) 𝑓2 (x) , respectively.
◦ Note that the functions 𝑓1 + 𝑓2 and 𝑓1 𝑓2 have been defined by specifying their values at x in terms of the
values of 𝑓1 and 𝑓2 at x .

◦ Example. Let 𝑓1
and 𝑓2 be functions from R to R such that
◦ 𝑓1 (x) = 𝑥 2 and 𝑓2 (x) = x − 𝑥 2 .
◦ What are the functions 𝑓1 + 𝑓2 and 𝑓1 𝑓2 ?
◦ Solution: From the definition of the sum and product of functions, it follows that

◦ (𝑓1 + 𝑓2 )(x) = 𝑓1 (x) + 𝑓2 (x) = 𝑥 2 + x − 𝑥 2 = x , and

◦ (𝑓1 𝑓2 )(x) = 𝑓1 (x) 𝑓2 (x) = 𝑥 2 (x − 𝑥 2 ) = 𝑥 3 − 𝑥 4 .
FUNCTIONS
◦ When 𝑓 is a function from A to B, the image of a subset of A can also be defined.
◦ DEFINITIONLet 𝑓 be a function from A to B and let S be a subset of A. The
image of S under the function 𝑓 is the subset of B that consists of the
images of the elements of S. We denote the image of S by 𝑓(S), so
𝑓(S) = {t | ∃ s ∈ S (t = 𝑓(s))}.
◦ We also use the shorthand {𝑓(s) | s ∈ S} to denote this set.
◦ Remark: The notation 𝑓(S) for the image of the set S under the function 𝑓 is potentially
ambiguous. Here, 𝑓(S) denotes a set, and not the value of the function 𝑓 for the set S.
◦ EXAMPLE Let A = {a, b, c, d, e} and B = {1, 2, 3, 4} with f (a) = 2, f (b) = 1,
◦ f (c) = 4, f (d) = 1, and f (e) = 1.
◦ The image of the subset S = {b, c, d} is the set f (S) = {1, 4}.
One-to-One Functions
DEFINITION A function f is said to be one-to-one, or an injunction, 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 injective if it is one-to-one.
Note that a function f is one-to-one if and only if 𝑓 (𝑎) ≠ 𝑓 (𝑏) whenever
𝑎 ≠ 𝑏. This way of expressing that f is one-to-one is obtained by taking the
contrapositive of the implication in the definition.
Remark: We can express that f is one-to-one using quantifiers as
∀𝑎∀𝑏 (𝑓 (𝑎) = 𝑓 (𝑏) → 𝑎 = 𝑏) or equivalently,
∀𝑎∀𝑏 (𝑎 ≠ 𝑏 → 𝑓 (𝑎) ≠ 𝑓 (𝑏)), where the universe of discourse is the
domain of the function.
One-to-One Functions
EXAMPLE 1. Determine whether the function f from {a, b, c, d} to {1, 2, 3,
4, 5} with f (a) = 4, f (b) = 5, f (c) = 1, and f (d) = 3 is one-to-one.
Solution: The
function f is one-to-one because f takes on different values at the
four elements of its domain. This is illustrated in the following figure.
One-to-One Functions
EXAMPLE 2. Determine whether the function f (x) = x + 1 from the set of real
numbers to itself is one-to-one.
Solution: Thefunction f (x) = x + 1 is a one-to-one function. To demonstrate
this, note that x + 1 ≠ y + 1 when x ≠ y.
EXAMPLE 3. Suppose that each worker in a group of employees is assigned a
job from a set of possible jobs, each to be done by a single worker. In this
situation, the function f that assigns a job to each worker is one-to-one. To
see this, note that if x and y are two different workers, then f(x)≠f(y)
because the two workers x and y must be assigned different jobs.
One-to-One Functions
◦ EXAMPLE 4.
Onto Functions
DEFINITION A function 𝑓 from A to B is called onto, or a surjection, if and only
if for every element 𝑏 ∈ 𝐵 there is an element 𝑎 ∈ 𝐴 with 𝑓(𝑎) = 𝑏.
A function 𝑓 is called surjective if it is onto.
Remark: A function 𝑓 is onto if ∀𝑦∃𝑥(𝑓(𝑥) = 𝑦), where the domain for 𝑥 is the
domain of the function and the domain for 𝑦 is the codomain of the function.
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. Because
all three elements of the codomain are images of elements
in the domain, we see that f is onto. This is illustrated in the figure on the
next slide. Note that if the codomain were {1, 2, 3, 4}, then f would not be
onto.
Onto Functions
An onto function

EXAMPLE 2. Is the function f (x) = x + 1 from the set of integers to the set of
integers onto?
Solution: This function is onto, because for every integer y there is an integer
x such that f (x) = y. To see this, note that f (x) = y if and only if x + 1 = y,
which holds if and only if x = y − 1 (which is an element of the domain).
Onto Functions
EXAMPLE 3. Consider the function f that assigns jobs (co-domain) to workers
(domain). The function f is onto if for every job there is a worker assigned
this job. The function f is not onto when there is at least one job that has no
worker assigned to it.
EXAMPLE 4.

REMARK. A function is ONTO iff the range of the function is equal to the co-
domain of the function.
BIJECTIVE FUNCTION
DEFINITION The function 𝑓 is a one-to-one correspondence, or a bijection, if
it is both one-to-one and onto.
We also say that such a function is bijective.
◦ EXAMPLE 1. Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f (a) = 4,
f (b) = 2, f (c) = 1, and f (d) = 3. Is f a bijection?
◦ Solution: The
function f is one-to-one and onto. It is one-to-one because no
two values in the domain are assigned the same function value. It is onto
because all four elements of the co-domain are images of elements in the
domain. Hence, f is a bijection.
Examples of different types of correspondences
SUMMARY