Discrete Structures

Lecture - 16
Functions
Application of Functions

• Define discrete structures such as sequences and strings

• Represent the time that a computer takes to solve
problems of a given size
• Represent the complexity of algorithms
•…
Functions
• In many examples we assign to each element of a set a
particular element of a second set (which may be the
same as the first).
• For example, suppose that each student in a discrete
mathematics class is assigned a letter grade from the set
{A,B,C,D, F}.
• This assignment is an example of a function.
Functions
• Let A and B be nonempty sets.

• A function f from A to B is an assignment of exactly one

element of B to each element of A.

• If b is the unique element of B assigned by the function f

to the element a of A, we write f(a) = b.

• If f is a function from A to B, we write f: A → B.

Functions

• If f is a function from A to B, we say that A is the domain

of f and B is the codomain of f.

• if f(a) = b, we say that b is the image of a and a is the pre-

image of b.

• The range of f is the set of all images of elements of A.

• Also, if f is function from A to B, we say that f maps A to

B.
 Functions
• A function takes an element from a set and maps it to a
UNIQUE element in another set.
f maps R to Z
Domain R Z Co-domain
f

f(4.3)
4.3 4

Pre-image of 4 Image of 4.3

Arrow Diagram of Functions

• The definition of a function implies that the arrow diagram

for a function f has the following two properties:

• Every element of A has an arrow coming out of it

• No elements of A has two arrows coming out of it that

point to two different elements of B.
Arrow Diagram of Functions(example)
• Let A = {Badar, Jameel, Sara, Ali} and
B = {A, B, C, D, F}.
Define a function f from A to B by the arrow diagram.

Badar A
Jameel B
Sara C
Ali D
F
Set A Set B
More Functions 1

A pre-image The image

of 1 of “a”
“a” 1
“bb“ 2
“cccc” 3
“dd” 4
“e” 5

A string length function

More Functions 2
What are the domain, codomain, and range of the
function that assigns grades to students.

Domain Co-domain
Alice A
Bob B
Chris C
Dave D
Emma F

A grade function

Range is the set {A,C,D,F}.

Even More Functions

Range
a 1 “a” 1
e 2 “bb“ 2
i 3 “cccc” 3
o 4 “dd” 4
u 5 “e” 5

Some function…

Not a valid function!

Also not a valid function!
Functions and Non-Functions
• Which of the arrow diagrams define functions from
• A = {2,4,5,6,7} to B = {1,2,4,6,8}.
Domain Co-domain Domain Co-domain
2 1 2 1
4 2 4 2
5 4 5 4
6 6 6 6
7 8 7 8

A B A B

Not a Function Not a Function

Function Arithmetic
• Let f1 and f2 be functions from A to R. Then f1 + f2 and f1*f2 are
also functions from A to R defined by
• (f1+f2)(x) = f1(x) + f2(x)
• (f1f2)(x) = f1(x)f2(x)

Example:
• Let f1(x) = 2x
• Let f2(x) = x2
• Find f1 + f2 and f1*f2.
• f1+f2 = (f1+f2)(x) = f1(x)+f2(x) = 2x+x2
• f1*f2 = (f1*f2)(x) = f1(x)*f2(x) = 2x*x2 = 2x3
One-to-One Function
• A function is one-to-one if each element in the co-domain
has a unique pre-image
• Formal definition: A function f is one-to-one if f(a) = f(b)
implies a = b for all a and b in the domain of f.
a 1 a 1
e 2 e 2
i 3 i 3
o 4 o 4
5 5

A one-to-one function A function that is

not one-to-one
One-to-One Function

• 𝑓 is one-to-one using quantifiers as

• ∀𝑎∀𝑏 𝑓 𝑎 = 𝑓 𝑏 → 𝑎 = 𝑏 or equivalently
∀𝑎∀𝑏 𝑎 ≠ 𝑏 → 𝑓(𝑎) ≠ 𝑓 𝑏

• Where 𝑎 and 𝑏 in domain of 𝑓.

More on One-to-One Functions
• Injective is synonymous with one-to-one
• “A function is injective”
• A function is an injection if it is one-to-one

a 1
e 2
• Note that there can i 3
be un-used elements
o 4
in the co-domain
5

A one-to-one function
Example one-to-one function
• Determine whether the function 𝑓 from {𝑎, 𝑏, 𝑐, 𝑑} to
{1, 2, 3, 4, 5} with 𝑓 𝑎 = 4, 𝑓 𝑏 = 5, 𝑓 𝑐 = 1, 𝑎𝑛𝑑
𝑓(𝑑) = 3 is one-to-one.
Onto Functions
• A function is onto if each element in the co-domain is an
image of some pre-image
• Formal definition: A function f is onto if for all b  B, there
exists a  A such that f(a) = b.

a 1 a 1
e 2 e 2
i 3 i 3
o 4 o 4
u 5

An onto function A function that

is not onto
Onto functions

• 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.
More on Onto Functions
• Surjective is synonymous with onto
• “A function is surjective”
• A function is a surjection if it is onto

• Note that there can

a 1
be multiple used
elements in the e 2
co-domain i 3
o 4
u

An onto function
Example onto function
• Determine whether the function 𝑓 from {𝑎, 𝑏, 𝑐, 𝑑} to
{1, 2, 3} defined by 𝑓 𝑎 = 3, 𝑓 𝑏 = 2, 𝑓 𝑐 = 1, 𝑎𝑛𝑑
𝑓(𝑑) = 3. Is 𝑓 an onto function?
 Onto vs One-to-One
• Are the following functions onto, one-to-one, both, or
neither?
a 1 a 1 a
b 1
2 b 2 b 2
c 3 c 3 c 3
4 d 4
4
1-to-1, not onto Both 1-to-1 and onto Not a valid function
a 1 a 1
b 2 b 2
c 3 c 3
d d 4

Onto, not 1-to-1 Neither 1-to-1 nor onto

Example
• Determine whether the function f (x) = 𝑥 2 from the set of
integers to the set of integers is one-to-one.
𝑓: 𝑍 → 𝑍; 𝑓 𝑥 = 𝑥 2
Example
• Determine whether the function f (x) = 𝑥 + 1 from the set
of integers to the set of integers is onto.
𝑓: 𝑍 → 𝑍; 𝑓 𝑥 = 𝑥 + 1
Bijections
• Consider a function that is
both one-to-one and onto:
a 1
• Such a function is a one-to-one b 2
c 3
correspondence, or a bijection.
d 4
Example
• Determine whether the following functions are bijective or
not?

𝑓: 𝑅 → 𝑅; 𝑓 𝑥 = 𝑥 3
𝑥+1
𝑓: 𝑅 − {0} → 𝑅; 𝑓 𝑥 =
𝑥
Identity Functions

• A function such that the image and the pre-image are

ALWAYS equal

• f(x) = 1*x
• f(x) = x + 0

• The domain and the co-domain must be the same set.

Inverse Function
• Let f be a one-to-one correspondence from the set A to
the set B.
• The inverse function of f is the function that assigns to an
element in b belonging to B the unique element a in A
such that f(a) = b.
• The inverse function of f is denoted by f −𝟏 .
• Hence , f −𝟏 (b) = a when f(a) = b.
Inverse Functions

If f(a) = b, then f-1(b) = a

A B

f
a= f-1(b) f(a)=b
f-1

A=domain of f B=Co-domain of f
Inverse Functions
If f(x) = y, then f-1(y) = x
Let f(x) = 2*x
f(x)=y
R f R

f-1

f(4.3)
4.3 8.6
f-1(8.6)

Then f-1(y) = y/2

More on Inverse Functions
• Can we define the inverse of the following functions?

a 1 a 1
b 2 b 2
c 3 c 3
4 d

What is f-1(2)? What is f-1(2)?

Not onto! Not 1-to-1!
• An inverse function can ONLY be done defined on a
bijection
More on Inverse Functions

• A one-to-one correspondence is called invertible

because we can define an inverse of this function.

• A function is not invertible if it is not a one-to-one

correspondence, because the inverse of such a function
does not exist.
Example
• 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 it is, what is its inverse?
Working Rule to Find Inverse Function
• Let f: X →Y be a one-to-one correspondence defined by
the formula f(x) = y.
1. Solve the equation f(x) = y for x in terms of y.
2. f −𝟏 (y) equals the right hand side of the equation found
in step 1.
Example
Let f : Z → Z be such that f (x) = x + 1. Is f invertible, and if
it is, what is its inverse?
Compositions of Functions
• Let g be a function from the set A to the set B and let f be
a function from the set B to the set C. the compositions of
the functions f and g, denoted by f °g, is defined by

(f °g)(𝒂) = f (g(a))
Compositions of Functions

(f °g)(a) = f(g(a))
f °g
A B C
g f

g(a) f(b)
a f(g(a))
b = g(a)

(f °g)(a)
Compositions of Functions

Let f(x) = 2x+3 Let g(x) = 3x+2

f°g
R R R
g f

g(1) f(5)
f(g(1))=13
1
g(1)=5

(f ° g)(1)

f(g(x)) = 2(3x+2)+3 = 6x+7

Compositions of Functions
Does f(g(x)) = g(f(x))?

Let f(x) = 2x+3 Let g(x) = 3x+2

f(g(x)) = 2(3x+2)+3 = 6x+7

g(f(x)) = 3(2x+3)+2 = 6x+11 Not equal!

Function composition is not commutative!

Compositions of Functions
• Let A = {1,2,3,4,5}
f : A → A and g : A → A
f(1) = 3, f(2) = 5, f(3) = 3, f(4) = 1, f(5) = 2
g(1) = 4, g(2) = 1, g(3) = 1, g(4) = 2, g(5) = 3
Find the composition functions f ◦ g and g ◦ f .
f◦g g◦f
(f ◦ g ) (1) = f(g(1)) = f(4) =1 (g ◦ f ) (1) = g(f(1)) = g(3) = 1
(f ◦ g ) (2) = ? (g ◦ f ) (2) = ?
(f ◦ g ) (3) = ? (g ◦ f ) (3) = ?
(f ◦ g ) (4) = ? (g ◦ f ) (4) = ?
(f ◦ g ) (5) = ? (g ◦ f ) (5) = ?
Compositions of Functions
Let g : A → A be the function, Set A = {a, b, c} such that g(a) = b,
g(b) = c, and g(c) = a.

Let f : A → B be the function, Set A = {a, b, c} to the set B = {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.
g ◦ f is not defined, because the range of f is not a subset of the
domain of g.
Exercise Questions

Chapter # 2
Topic # 2.3
Questions 1, 10,11,12,18,19,32,33