With Question/Answer Animations

Note: These slides were made available by Kenneth H. Rosen, the author of the textbook
Discrete Mathematics and its Applications. They were edited by Abdullah Heyari (course
instructor) to fit the requirements of the course Discrete Structures (CS201) taught at the
German Jordanian University during the second semester of the academic year 2024 – 2025.

Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
Chapter Summary
 2.1 Sets
 The Language of Sets
 Set Operations
 Set Identities
 2.2 Functions
 Types of Functions
 Operations on Functions
 Computability
 2.3 Sequences and Summations
 Types of Sequences
 Summation Formulae
Section Summary
 Definition of a Function
 Domain, Codomain
 Image, Preimage
 Injection, Surjection, Bijection
 Inverse Function
 Function Composition
 Graphing Functions
 Floor, Ceiling, Factorial
 Partial Functions (optional)
Functions [1]
Definition: Let A and B be nonempty sets. 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. We
write f(a) = b if b is the unique element of B assigned
by the function f to the element a of A. Students Grades
 Functions are sometimes A
Carlota Rodriguez
called mappings or B
transformations. Sandeep Patel C
Jalen Williams D

F
Kathy Scott
Functions [2]
 A function f: A → B can also be defined as a subset of
A×B (a relation). This subset is restricted to be a
relation where no two elements of the relation have
the same first element.
 Specifically, a function f from A to B contains one, and
only one ordered pair (a, b) for every element a ∈ A.

and
Functions [3]
Given a function f: A → B:
 We say f maps A to B or
f is a mapping from A to B.
 A is called the domain of f.
 B is called the codomain of f.
 If f(a) = b,
 then b is called the image of a under f.
 a is called the preimage of b.
 The range of f is the set of all images of points in A under f. We
denote it by f(A).
 Two functions are equal when they have the same domain, the
same codomain and map each element of the domain to the
same element of the codomain.
Representing Functions
 Functions may be specified in different ways:
 An explicit statement of the assignment:
Example: The example of students and their grades on slide 5.
 A mathematical formula:
Example: f(x) = x + 1
 A computer program:
 Example: A Java program that when given an integer n,
produces the nth Fibonacci Number (covered in the next
section and also in Chapter 5).
 Questions
f(a) = ? z A B
a
The image of d is ? z x

b
The domain of f is ? A y
c
The codomain of f is ? B
d z
The preimage of y is ? b
f(A) = ? {y, z}
The preimage(s) of z is (are) ? {a, c, d}
Question on Functions and Sets
 If and S is a subset of A, then

A B
f {a, b, c} is ? {y, z} a
x
b
f {c, d} is ? {z} y
c

d z
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 injective
(or one-to-one) if it maps distinct inputs to distinct
outputs.
A B
a x
In an injection, there
is no such thing that
v
f(𝑎 ) = 𝑏 b
f(𝑎 ) = 𝑏 y
where 𝑎 ≠ 𝑎 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 . When a
function is surjective (or onto) every element in its
codomain B must be mapped A B
to at least one element in its a x
domain A.
b
y
c
In a surjection, all the codomain is
z
“consumed/used”. d
𝑓 𝑎 = 𝑧, 𝑓 𝑑 = 𝑧, 𝑎≠𝑧
Thus, f is a surjection but not one-to-one
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
z
d
w
Showing That f is One-to-one or Onto
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,
because 4 was not mapped to any domain element.
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, (a counterexample).
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?
What if: What if:
injective but surjective but
not surjective: not injective:
some elements multiple
of the codomain elements in the
will not be domain will be
assigned to mapped to the
elements in the same element in
domain the codomain
Inverse Functions
f
A B A B
a V V
a

b b
W W
c c

d X X
d

Y Y
Questions [1]
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 [2]
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 [3]
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 [1]
 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 [2]
A g
B f
C A C
V a
a h h
b i b
W i
c
c
X j
d
d j
Y
Composition [3]
Example 1: If and ,
then

and
Composition Questions [1]
Example 2: Let g be the function from the set {a, b, c} to
itself such that g(a) = b, g(b) = c, and g(c) = a. Let f be the
function from the set {a, b, c} to the set {1,2,3} such that
f(a) = 3, f(b) = 2, and f(c) = 1.
What is the composition of f and g, and what is the
composition of g and f.
Solution: The composition f∘g is defined by
f∘g (a)= f(g(a)) = f(b) = 2.
f∘g (b)= f(g(b)) = f(c) = 1.
f∘g (c)= f(g(c)) = f(a) = 3.
Note that g∘f is not defined, because the range of f is not a
subset of the domain of g.
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 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
Graphs of Functions
 Let f be a function from the set A to the set B. The
graph of the function f is the set of ordered pairs
{(a, b) | a ∈ A and f(a) = b}.

Graph of f(n) = 2n + 1 Graph of f(x) = x2

from Z to Z from Z to Z
Some Important Functions
 The floor function, denoted

is the largest integer less than or equal to x.

 The ceiling function, denoted

is the smallest integer greater than or equal to x

Example:
Floor and Ceiling Functions

Graph of (a) Floor and (b) Ceiling Functions

Floor and Ceiling Functions
Proving Properties of Functions
Example: Prove that if x is a real number, then
⌊2x⌋= ⌊x⌋ + ⌊x + 1/2⌋
Solution: Let x = n + ε, where n is an integer and 0 ≤ ε< 1.
Case 1: ε < ½
 2x = 2n + 2ε and ⌊2x⌋ = 2n, since 0 ≤ 2ε< 1.
 ⌊x + 1/2⌋ = n, since x + ½ = n + (1/2 + ε ) and 0 ≤ ½ +ε < 1.
 Hence, ⌊2x⌋ = 2n and ⌊x⌋ + ⌊x + 1/2⌋ = n + n = 2n.
Case 2: ε ≥ ½
 2x = 2n + 2ε = (2n + 1) +(2ε − 1) and ⌊2x⌋ =2n + 1,
since 0 ≤ 2 ε - 1< 1.
 ⌊x + 1/2⌋ = ⌊ n + (1/2 + ε)⌋ = ⌊ n + 1 + (ε – 1/2)⌋ = n + 1 since
0 ≤ ε – 1/2< 1.
 Hence, ⌊2x⌋ = 2n + 1 and ⌊x⌋ + ⌊x + 1/2⌋ = n + (n + 1) = 2n + 1.
Factorial Function
Definition: f: N → Z+ , denoted by f(n) = n! is the
product of the first n positive integers when n is a
nonnegative integer.
f(n) = 1 ∙ 2 ∙∙∙ (n – 1) ∙ n, f(0) = 0! = 1
Examples: Stirling’s Formula:
f(1) = 1! = 1
f(2) = 2! = 1 ∙ 2 = 2
f(6) = 6! = 1 ∙ 2 ∙ 3∙ 4∙ 5 ∙ 6 = 720
f(20) = 2,432,902,008,176,640,000.