1

Functions
Course Code: CSC 1204 Course Title: Discrete Mathematics

Dept. of Computer Science

Faculty of Science and Technology

Lecturer No: 5 Week No: 3 Semester:

Lecturer: Name & email
 2

Lecture Outline

2.3 Functions
• Definition of Function
• Domain, Codomain, Range, Image, Preimage,
• One-to-one function
• Onto function
• One-to-one correspondence
• Inverse Functions
• Compositions of Functions
• Floor function
• Ceiling Function
 Functions
• A function relates an input to an output. Function is defined in terms of sets

Functions can be defined in many ways

 5

Functions

• Definition 1: 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.
We write f(a) = b if b is the unique element of B
assigned by the function f to the element a of A.
• If f is a function from A to B, we write f: AB
• Note: Functions are sometimes called mappings or
transformations.
 6

Functions

• Functions are specified in many ways.

• Sometimes we explicitly state the assignments, as in
Figure 1.
• Often, we give a formula, such as f(x) = x + 1, to define a
function.
• Other times we use a computer program to specify a
function.
 7

Functions

• A function f: A B can also be defined in terms of a

relation from A to B. [we will cover Relation in final
term]
• A relation from A to B is just a subset of A X 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 f from A to B. This function is defined by the
assignment f(a)=b, where ( a, b) is the unique ordered
pair in the relation that has a as its first element.
 8

FIGURE 1: Assignment of Grades in a

Discrete Mathematics Class
 Domain, Codomain and Range

• What can go into a function is called the Domain

• What may possibly come out of a function is called the Codomain
• What actually comes out of a function is called the Range

The Range is a subset of the Codomain.

 10

Some Function Terminology

Definition 2: 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, a is the preimage of b and b is the image of a.

• Range of f is the set of all images of elements of A.

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

Domain, Codomain and Range

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

 A is the domain of f
 B is the codomain of f
 If f(a)=b,
• a is called the preimage of b
• b is called the image of a
• Range of f : the set of all images of elements of A
 12

Range versus Codomain

• The range of a function might not be its whole codomain.

• The codomain is the set that the function is declared to map all
domain values into.
• The range is the particular set of values in the codomain the
function actually maps elements of the domain to.
 13

Range versus Codomain: Example

(See the FIGURE 1 in the previous slide)
• Suppose I declare to you that: “f is a function mapping
students in this class to the set of grades {A, B, C,D,F}”.
• At this point, you know f’s codomain is: {A, B, C,D,F}, and
it’s range is unknown!
• Suppose the grades turn out all As and Bs.
• Then the range of f is {A, B}”, but it’s codomain is still
{A, B, C,D,F}.
 14

Example 1

• What are the domain, codomain, and range of the function that assigns
grades to students of Discrete Math class as follows?
 15

Solution of Example 1
 Solution:
• Let G be the function that assigns grade to a student of
Discrete Mathematics class.
• The domain of G is the set { Adams, Chou, Goodfriend,
Rodriguez, Stevens}
• The codomain of G is the set { A, B, C, D, F}
• The range of G is the set { A, B, C, F}
• Because each grade except D is assigned to some student
 16

Example 2
• Let R be the relation consisting of ordered pairs (Abdul, 22), (Brenda,24),
(Carla,21), (Desire,22), (Eddie,24), and (Felicia,22), where each pair consists of
a graduate student and the age of this student. What is the function that this
relation determines?

• Solution: This relation defines the function f, where with f(Abdul)= 22,
f(Brenda)=24, f(Carla)=21, f(Desire)=22, f(Eddie)= 24, and f(Felicia)=22.
• Here, domain is the set { Abdul, Brenda, Carla, Desire, Eddie, Felicia }
• To define the function f, we need to specify a codomain. Here, we can take the
codomain to be the set of positive integers
• Range is the set {21,22,24}
 17

Functions

Definition 3: 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)
(f1 f2)(x) = f1(x) f2(x)
 18

Example 6

 Let f1 and f2 be functions from R to R such that f1(x)=x2 and

f2(x)=x – x2. What are the functions f1 + f2 and f1 f2 ?
 Solution:
(f1 + f2)(x) = f1(x) + f2(x) = x2 + (x –x2 ) = x

(f1f2)(x) = x2(x x2 ) = x3 – x4
 19

Functions
• Definition 4: Let f be a function from the set A to the set
B, and let S is a subset of A. The image of S under the
function f is the subset of B that consists of the images
of the elements of S.
• We denote the image of S by f(S).
f(S) = {t|sS(t=f(s))}
 20

Example 7
• 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, f(e) = 1.
What is the image of the subset S = {b, c, d}?

• Solution:
• The image of the subset S = {b, c, d} is the set
f(S) = {1, 4}
 A function is a way of matching the members of a set "A" to a set "B”.
"Injective, Surjective and Bijective" tells us about how a function
One-to-One Functions
behaves.

• A General Function points from each member of "A" to a member of "B".

• It never has one "A" pointing to more than one "B", so one-to-many is not
OK in a function (so something like "f(x) = 7 or 9" is not allowed)
• But more than one "A" can point to the same "B" (many-to-one is OK)
• Injective means we won't have two or more "A"s pointing to the
same "B". Injective is also called "One-to-One"
One-to-One Functions
• So many-to-one is NOT OK (which is OK for a general function). As
it is also a function one-to-many is not OK. But we can have a "B"
without a matching "A”.

• Surjective means that every "B" has at least one matching "A"
(maybe more than one).
• There won't be a "B" left out.

• Bijective means both Injective and Surjective together.

• Think of it as a "perfect pairing" between the sets: every one has
a partner and no one is left out. So there is a perfect "one-to-one
correspondence" between the members of the sets.
• (But don't get that confused with the term "One-to-One" used to
mean injective).
 23

One-to-One Functions

 Definition 5: A function f is one-to-one or injective, iff f(a)

= f(b) implies that a = b for all a and b in the domain of f.
 A function f: A B is said to be one-to-one if all the
elements in the domain A have distinct images.
• We can express that f is one-to-one Using quantifiers as
ab ( f(a) = f(b)  a = b ), or equivalently,
ab ( a  b  f(a)  f(b) ), where the universe of
discourse is the domain of the function f
 24

Example 8

• 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 is one-to-one because every
element of domain has a distinct image.
• The function f is one-to-one because f takes on different
values at the four elements of its domain.
 25

Example 9
Example 9: Determine whether the function f(x) = x2 from
the set of integers to the set of integers is one-to-one.

Solution: The function f(x) = x2 is not one-to-one because,

for instance, f(1)= f(–1) = 1, but 1 = – 1
(i.e. 1 and –1 have same image 1)
 26

Class Work

Determine whether the function f(x) = x2 from the set of

positive integers to the set of positive integers is one-
to-one.
For example, the function f(x) = x + 1 is a one-to-one function because
it produces a different answer for every input.

The function f(x) = x^2, on the other hand, is not a one-to-one function
because it gives you the same answer for more than one input.
 27

Example 10

• Determine whether the function f(x) = x + 1 from the

set of real numbers to the set of real numbers is one-
to-one.

• Solution: The function f(x) = x + 1 is a one-to-one

function. Since x + 1 = y + 1, when x = y
• For any real number x, there is a distinct image, just 1
bigger than x; so, the function is one-to-one.
 28

Example : One-to-one function

• Let A = {1, 2, 3} and B = {a, b, c, d}, and let f(1) = a,

f(2) = b, f(3) = d. Then f is injective, since the
different elements 1, 2, 3 in A are assigned to the
different elements a, c, d respectively in B
• Note: Every element of domain has a distinct image.
So, the function is one-to-one.
 29

Onto Function

• Definition 7: A function f from A to B is onto or surjective,

iff for every element bB there is an element aA with
f(a) = b.
• A function f: AB is said to be an onto function if each
element of B is the image of some element of A
• i.e., if B = range of f
• Note: A function is onto if every element of codomain has
preimage(s).
 30

Example 11

• 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?
[see Figure on next slide]
• Solution: Because all three elements of the codomain
are images of elements in the domain, f is onto.
 31

FIGURE for Example 11:

An Onto Function
 32

Example 12

• Is the function f(x) = x2 from the set of integers to the

set of integers onto?
• Solution: The function f is not onto, because there is
no integer x with x2 = –1, for instance.

• Note: The elements of the codomain that are negative

integers ( 1,  2,  3 etc.) do not have any preimage.
 33

Class Work

Is the function f(x) = x2 from the set of positive integers to

the set of positive integers onto?
 34

One-to-one correspondence
(bijection )
• Definition 8: A function f is a one-to-one correspondence or a
bijection if it is both one-to-one and onto.

• Example: Let f be the function from A to B where A={1, 2, 3, 4}

and B = {a, b, c, d} with f(1)=d, f(2)=b, f(3)=c, and f(4)=a, then f is
bijective function.
- f is one-to-one since the every element of domain has a distinct image
- f is onto since every element of B is the image of some element in A.
 Hence f is a bijective function (or, one-to-one correspondence)
• Practice yourself: Example 14