Chapter IV: Functions & Algorithms
Lesson I: Functions
It is a mapping in which every element of set A is uniquely associated at the element with
set B. The set of A is called Domain of a function and set of B is called Co domain.
Domain, Co-Domain, and Range of a Function:
Domain of a Function: Let f be a function from P to Q. The set P is called the domain of
the function f.
Co-Domain of a Function: Let f be a function from P to Q. The set Q is called Co-domain
of the function f.
Range of a Function: The range of a function is the set of picture of its domain. In other
words, we can say it is a subset of its co-domain. It is denoted as f (domain).
If f: P → Q, then f (P) = {f(x): x ∈ P} = {y: y ∈ Q | ∃ x ∈ P, such that f (x) = y}.
Example: Find the Domain, Co-Domain, and Range of function.
Let x = {1, 2, 3, 4}
y = {a, b, c, d, e}
f = {(1, b), (2, a), (3, d), (4, c)
Solution:
Domain of function: {1, 2, 3, 4}
Range of function: {a, b, c, d}
Co-Domain of function: {a, b, c, d, e}
Functions as a Set
If P and Q are two non-empty sets, then a function f from P to Q is a subset of P x Q, with
two important restrictions
1. ∀ a ∈ P, (a, b) ∈ f for some b ∈ Q
2. If (a, b) ∈ f and (a, c) ∈ f then b = c.
Example1: If a set A has n elements, how many functions are there from A to A?
Solution: If a set A has n elements, then there are n n functions from A to A.
Representation of a Function
The two sets P and Q are represented by two circles. The function f: P → Q is represented
by a collection of arrows joining the points which represent the elements of P and
corresponds elements of Q
Example1:
Then f can be represented diagrammatically as follows
Example2: Let X = {x, y, z, k} and Y = {1, 2, 3, 4}. Determine which of the following
functions. Give reasons if it is not. Find range if it is a function.
a. f = {(x, 1), (y, 2), (z, 3), (k, 4)
b. g = {(x, 1), (y, 1), (k, 4)
c. h = {(x, 1), (x, 2), (x, 3), (x, 4)
d. l = {(x, 1), (y, 1), (z, 1), (k, 1)}
e. d = {(x, 1), (y, 2), (y, 3), (z, 4), (z, 4)}.
Solution:
1. It is a function. Range (f) = {1, 2, 3, 4}
2. It is not a function because every element of X does not relate with some element of
Y i.e., Z is not related with any element of Y.
3. h is not a function because h (x) = {1, 2, 3, 4} i.e., element x has more than one
image in set Y.
4. d is not a function because d (y) = {2, 3} i.e., element y has more than image in set
Y.
Lesson II: Types of Functions
1. Injective (One-to-One) Functions: A function in which one element of Domain Set is
connected to one element of Co-Domain Set.
2. Surjective (Onto) Functions: A function in which every element of Co-Domain Set has one
pre-image.
Example: Consider, A = {1, 2, 3, 4}, B = {a, b, c} and f = {(1, b), (2, a), (3, c), (4, c)}.
It is a Surjective Function, as every element of B is the image of some A
Note: In an Onto Function, Range is equal to Co-Domain.
3. Bijective (One-to-One Onto) Functions: A function which is both injective (one to - one)
and surjective (onto) is called bijective (One-to-One Onto) Function.
Example:
Consider P = {x, y, z}
Q = {a, b, c}
and f: P → Q such that
f = {(x, a), (y, b), (z, c)}
The f is a one-to-one function and also it is onto. So it is a bijective function.
4. Into Functions: A function in which there must be an element of co-domain Y does not have
a pre-image in domain X.
Example:
Consider, A = {a, b, c}
B = {1, 2, 3, 4} and f: A → B such that
f = {(a, 1), (b, 2), (c, 3)}
In the function f, the range i.e., {1, 2, 3} ≠ co-domain of Y i.e., {1, 2, 3, 4}
Therefore, it is an into function
5. One-One Into Functions: Let f: X → Y. The function f is called one-one into function if
different elements of X have different unique images of Y.
Example:
Consider, X = {k, l, m}
Y = {1, 2, 3, 4} and f: X → Y such that
f = {(k, 1), (l, 3), (m, 4)}
The function f is a one-one into function
6. Many-One Functions: Let f: X → Y. The function f is said to be many-one functions if there
exist two or more than two different elements in X having the same image in Y.
Example:
Consider X = {1, 2, 3, 4, 5}
Y = {x, y, z} and f: X → Y such that
f = {(1, x), (2, x), (3, x), (4, y), (5, z)}
The function f is a many-one function
7. Many-One Into Functions: Let f: X → Y. The function f is called the many-one function if
and only if is both many one and into function.
Example:
Consider X = {a, b, c}
Y = {1, 2} and f: X → Y such that
f = {(a, 1), (b, 1), (c, 1)}
As the function f is a many-one and into, so it is a many-one into function.
8. Many-One Onto Functions: Let f: X → Y. The function f is called many-one onto function if
and only if is both many one and onto.
Example:
Consider X = {1, 2, 3, 4}
Y = {k, l} and f: X → Y such that
f = {(1, k), (2, k), (3, l), (4, l)}
The function f is a many-one (as the two elements have the same image in Y) and it is onto (as
every element of Y is the image of some element X). So, it is many-one onto function
Lesson III: Identity Functions
The function f is called the identity function if each element of set A has an image on itself
i.e. f (a) = a ∀ a ∈ A.
It is denoted by I.
Example:
The function f is an identity function as each element of A is mapped onto itself. The
function f is a one-one and onto
Invertible (Inverse) Functions
A function f: X → Y is invertible if and only if it is a bijective function.
Consider the bijective (one to one onto) function f: X → Y. As f is a one to one, therefore,
each element of X corresponds to a distinct element of Y. As f is onto, there is no element of
Y which is not the image of any element of X, i.e., range = co-domain Y.
The inverse function for f exists if f -1 is a function from Y to X.
Example:
The inverse function of f is shown in fig:
Lesson IV: Compositions of Functions
Consider functions, f: A → B and g: B → C. The composition of f with g is a function from A
into C defined by (gof) (x) = g [f(x)] and is defined by gof.
To find the composition of f and g, first find the image of x under f and then find the
image of f (x) under g.
Example1:
Consider the function f = {(1, a), (2, a), (3, b)} and g = {(a, 5), (b, 7)} as in figure. Find
the composition of gof.
Solution: The composition function gof is shown in fig:
Example2: Consider f, g and h, all functions on the integers, by f (n) =n 2, g (n) = n + 1
and h (n) = n - 1.
Determine (i) hofog (ii) gofoh (iii) fogoh.
Solution:
Note:
o If f and g are one-to-one, then the function (gof) (gof) is also one-to-one.
o If f and g are onto then the function (gof) (gof) is also onto.
o Composition consistently holds associative property but does not hold commutative
property.
