Basic Structures:

Functions

14011801-3 Discrete Structures I

Today’s Agenda
› Definition of a Function.
– Domain, Codomain
– Image, Preimage
› Injection, Surjection, Bijection
› Inverse Function
› Function Composition
› Graphing Functions
› Floor and Ceiling functions
Functions
› Definition:
– Let A and B be nonempty sets. A function f from A to B, denoted a f:A→ B is
an assignment of each element of A to exactly one element of B. We write
f(x) = y if 𝒚 is the unique element of B assigned by the function f to the
element 𝒙 of A.

f :A→B
A B

› Functions are sometimes called mappings or transformations.

 A f :A→B B

1 a
Functions 2 b

› Let A= {1, 2}, B= {a, b}, then A×B = { (1,a), (1,b), (2,a), (2,b) }
› f: A → B: either we have (1,a) or (1,b) but not both. Same thing for (2,a), or (2,b) not both.

› Definition:
– A function f: A → B can also be defined as a subset of A×B.
– A subset of the Cartesian product A x B is called a relation from the set A to the set B.
– 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
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 co-domain of f.

› If f(a) = b,
– then b is called the image of a under f.
– a is called the pre-image of b.

› The range of f is the set of all images of points in A under f. We denote it by f(A). The
range is a subset of codomain B.

› 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.
Students and grades example (a set of pairs!)
We can use a table as follows:
x f(x)
a 2
b 3

– A formula (if the domain cannot be listed).

f(x) = x + 1

– A computer program.
› A Java program that when given an integer n, produces the nth Factorial.
Example
› Let A = {1, 2, 3} and B = {a, b, c}
– Assume f is defined as:
𝑥 𝑓(𝑥)
1→a
2→b 1 a

3→b 2 b
› Is f a function? Why? 3 b

– Assume f is defined as:

1→a
1→c
2→b
3→b
› Is f a function? Why?
Questions
• 𝑓(𝑎) = ? 𝑧 𝐴 𝐵
• 𝑇ℎ𝑒 𝑖𝑚𝑎𝑔𝑒 𝑜𝑓 𝑑 𝑖𝑠? 𝑧 a
x
b
• 𝑇ℎ𝑒 𝑑𝑜𝑚𝑎𝑖𝑛 𝑜𝑓 𝑓 𝑖𝑠? 𝐴
y
c
• 𝑇ℎ𝑒 𝑐𝑜𝑑𝑜𝑚𝑎𝑖𝑛 𝑜𝑓 𝑓 𝑖𝑠? 𝐵 z
d
• 𝑇ℎ𝑒 𝑝𝑟𝑒𝑖𝑚𝑎𝑔𝑒 𝑜𝑓 𝑦 𝑖𝑠 ? 𝑏
• 𝑓(𝐴) = ? {𝑦, 𝑧}
• 𝑇ℎ𝑒 𝑝𝑟𝑒𝑖𝑚𝑎𝑔𝑒(𝑠) 𝑜𝑓 𝑧 𝑖𝑠 (𝑎𝑟𝑒) ? {𝑎, 𝑐, 𝑑}
Question on Functions and Sets
› If and S is a subset of A, then

A B
• 𝑓 {𝑎, 𝑏, 𝑐} 𝑖𝑠 ? {𝑦, 𝑧}
a
x
• 𝑓 {𝑐, 𝑑} 𝑖𝑠 ? {𝑧} b
y
c
z
d
“many-to-one”
› NOTE:
– In general, a function can map many elements in the domain on the same
element in the range (many-to-one mapping)
– e.g., each of elements a, c, d is mapped to z

A B
a
x
b
y
c
z
d
Sum and Product of Functions
› Let f1 and f2 be functions from A→R (or A→Z), then
› f1+f2 and f1f2 are also functions A→R (or A→Z) defined as follows:
– (f1 + f2)(x) = f1(x) + f2(x)
– (f1f2)(x) = f1(x) f2(x)
Examples:
› Let f1,f2: R→R and f1(x) = x2 and f2(x) = x - x2.
– Find (f1 + f2)(x)
– Find (f1f2)(x).

– (f1 + f2)(x) = f1(x) + f2(x)

= (x2) + (x – x2)
= x 2 + x – x2
=x

– (f1 f2)(x) = f1(x) f2(x)

= (x2) (x – x2) = x3 – x4
Injections- (i.e. one-to-one)
› Definition:
– A function 𝑓 is said to be one-to-one , or injective, if and only if
𝑓(𝑎) = 𝑓(𝑏) implies that 𝑎 = 𝑏 for all 𝑎 and 𝑏 in the domain of 𝑓. A
function is said to be an injection if it is one-to-one.
– Every member in the codomain has: 1 or 0 preimage.

𝐴 𝐵
w
a
x
b
y
c
z
Surjections- (i.e. onto)
› 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.
– Every member in the codomain has: 1 or more preimage.

NOTE: in this example, function could be

A B
surjective (onto) but not injective (one to a
one). Why it is not?
x
b
Vice versa, the example on the previous
slide shows that a function could be y
injective (one-to-one) but not surjective c
(onto). Why? 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 and B has equal number of elements
– Every member in the codomain has: only 1 preimage.
A B
a
x
b
y
c
z
 Examples
For each of the following relations, identify if it is a function, one-
to-one, onto and bijection.

Function is Function is Function is Function is Not function

• 1-to-1 • Onto • 1-to-1 • not 1-to-1,
• not Onto, not • not 1-to-1, not • onto not onto, not
Bijection bijection • bijection bijection
Showing that f is 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}, is f an onto function?
› f would not be onto.

› Example 2:
– Let f:Z → Z and f(x) = x2. Is f onto?

– Solution: No, f is not onto because there is no integer x with x2 = −1, for
example.
Increasing and Decreasing Functions
Let f:A → B and A, B ⊆ R, then:
› If ∀x∀y(x<y → f(x)≤f(y)), f is increasing .
› if ∀x∀y(x<y → f(x)<f(y)), f is strictly increasing

› Example:
– Is the function 𝑓(𝑥) = 𝑥 + 1 from the set of real numbers to the set of real
numbers strictly increasing?

› Solution:
– Assume 𝑥, 𝑦 ∈ 𝑅.
– If 𝑥 < 𝑦, then 𝑥 + 1 < 𝑦 + 1.
– So, f is strictly increasing.
Increasing and Decreasing Functions
› if ∀x∀y(x<y → f(x)≥f(y)), f is decreasing
› if ∀x∀y(x<y → f(x)>f(y)), f is strictly decreasing

› a function that is either strictly increasing or strictly decreasing must be one-

to-one (Every member in the codomain has: 1 or 0 preimage)
𝐴 𝐵
• Example: function 𝑓(𝑥) = 𝑥 + 1 1
2

3
2
• Assume 𝑥, 𝑦 ∈ 𝑅. If 𝑥 < 𝑦, then 𝑥 + 1 < 𝑦 + 1. 6
4
5

› a function that is increasing, or decreasing, but not strictly increasing or

decreasing, is not one-to-one.
Identity Function
› Definition:
– Let A be a set. The identity function on A is the function ιA : A → A,
where for all x ∈ A :

ιA(x) = x

› The identity function is the function that assigns each element to

itself.
› It is one-to-one and onto, so it is a bijection.
Inverse Functions
› Definition:
– Let f be a bijection from A to B. Then the inverse of f, denoted𝑓 −1 , is
the function from B to A defined as 𝑓 −1 𝑦 = 𝑥 iff 𝑓(𝑥) = 𝑦

– No inverse exists unless f is a bijection.

A B A B
a a
x x
b b
y y
c c
z z
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.

› Example 3:
– Let f: R → R be such that 𝑓(𝑥) = 𝑥 2 .
– Is f invertible and if so, what is its inverse?

– Solution: The function f is not invertible because it is not onto (see slide #16)
Composition
› Definition:
– Let g: A → B, f: B → C. The composition of f with g, denoted 𝑓 ∘ 𝑔 is
the function from A to C defined by 𝑓 ∘ 𝑔 𝑥 = 𝑓(𝑔 𝑥 )
Composition
g f
A B C D A D
a v v a
h h
b w w b
i i
c x x c
j j
d z d
z

If g:A→B and f:C →D, then 𝑓 ∘ 𝑔 is defined iff g(A)⊆C

Composition
› Example 1:
– If 𝑓 𝑥 = 𝑥 2 and 𝑔 𝑥 = 2𝑥 + 1
– Is 𝑓 ∘ 𝑔 = 𝑔 ∘ 𝑓?

– Solution:
› 𝑓 ∘ 𝑔 𝑥 =𝑓 𝑔 𝑥 = 𝑓 2𝑥 + 1 = 2𝑥 + 1 2 = 4x2 + 1+ 4x ➔ = (a + b)2 = a2 + b2 + 2ab
› 𝑔 ∘𝑓 𝑥 =𝑔 𝑓 𝑥 = 𝑔 𝑥2 = 2 𝑥2 + 1

𝑓 ∘ 𝑔 ≠𝑔 ∘ 𝑓
Composition Questions
› 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?
– 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.
f({a,b,c}) = {1,2,3} ⊈ Domain of g = {a,b,c}
Composition Questions
Example 3:
Let f and g be functions from the set of integers to the set of integers
defined by:
f(x) = 2x + 3
g(x) = 3x + 2
– What is the composition of f and g?
– What is 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
Composition Questions
Example 4:

Let f a function from the set of integers to the set of integers defined by:

𝑓 𝑥 = 2𝑥 − 1
– What is the composition of f and f-1?
– What is the composition of f-1 and f ? • ∀𝑥 𝑓 ∘ 𝑓 −1 𝑥 = 𝑓 −1 ∘ 𝑓 𝑥 = 𝑥
• It is an identity function.
Solution: First let’s find f-1

𝑓 𝑥 = 2𝑥 − 1

𝑓 𝑥 + 1 = 2𝑥
𝑓 𝑥 +1
=𝑥
2
𝑥+1
∴ 𝑓 −1 𝑥 =
2

𝑥+1 𝑥+1
𝑓 ∘ 𝑓 −1 𝑥 = 𝑓 𝑓 −1 𝑥 =𝑓 =2 −1=𝑥+1−1=𝑥
2 2

2𝑥 − 1 + 1 2𝑥
𝑓 −1 ∘ 𝑓 𝑥 = 𝑓 −1 𝑓 𝑥 = 𝑓 −1 2𝑥 − 1 = = =𝑥
2 2
Graphs of Functions
Let f:Z→Z and f(x) = 2x+1
To draw this function, we have to choose some example points:

x f(x)
0 1
1 3
2 5

These points can be written as ordered pairs:

{(0,1), (1,3), (2,5)}
This set will represent a graph for function f
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.

Examples: