DHARM14 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEarg(f) = x∈im∪.g()f fy−^1 (); s (symbol ∪. indicates that the sets involved for union
are disjoint to each other)
l The function is an empty function f∅, if img (f∅) = ∅ and undefined argument.
l The function is called identity function if img (f) = x, where f : X → X, for all x ∈ X.
l The function is called surjective if img (f) = Y. Such that, every element of Y is the
image of one/more elements of X, i.e., | X | ≥ |Y|. Otherwise it is not surjective.
l The function is called injective if arg(f) = 0, i.e., if x 1 ≠ x 2 ⇒ f(x 1 ) ≠ f(x 2 ) for all x 1 , x 2
∈ X. Such that each element of X has a unique image in Y, i.e., | X | = | Y |.
l Functions that are both surjective and injective are called bijective. It follows that
number of elements of both sets be strictly equal, i.e., | X | = | Y |.
A function of finite set X into itself, i.e., f : X → X, the classes surjective, injective,
and bijective coincides. For the set of infinite size this is no longer true. For example, f : N
→ N where N = {0, 1, 2, .....} then f(n) = 2n, is injective, but not surjective.
Suppose that both sets X and Y are endowed with a partial order. Function f : X → Y is
called monotone if it preserves the order relation. i.e., if x 1 = x 2 then f(x 1 ) = f(x 2 ) for all x 1 , x 2 ∈ X,
and it is called antitone if x 1 = x 2 then f(x 1 ) = f(x 2 ) for all x 1 , x 2 ∈ X.
Observe that if X is totally unordered set then monotone function is an arbitrary function,
regardless of the order on Y.
Example 1.5. (A). Classify which of the following function is surjective, injective, and bijective.
(I) Let N = {0, 1, 2, .....} and f : N → N, where f(x) = x^2 + 1. then
Since,
at, x = 0; f(0) = (0)^2 + 1 = 1
at, x = 1; f(1) = (1)^2 + 1 = 2
at, x = 2; f(2) = (2)^2 + 1 = 5
....... .........
So we observe that distinct elements of N are mapped into distinct elements of the
image set N, hence function is injective.
(II)Let f : N → {0, 1}, where f(x) = 1, if x is even, otherwise 0.
Since, image set contains the elements 0 and 1, and all even numbers of N are mapped
to element 1 and all odd numbers are mapped to the element 0 of N. So, img (f) = {0, 1}, hence
mapping or function is surjective.
(III)Let f : N → N, where f(x) = 1, if x is even, otherwise 0.
Here, img (f) = {0, 1} but there are other elements in the image set N that are nor the
image of any element of argument N. Hence, function is not surjective.
(IV)Let f : P → P, where P = {0, 1, 2, 3, 4} and f(x) = x % 5 or (x mod 5).
s If the function f : X → Y is surjective, then we can define inverse function f–1, i.e.,
f –1: Y → X ;
where, f –1(y) = x ⇔ f(x) = y, for any x ∈ X and y ∈ Y. The composite of function f and f –1 is an identity
function, i.e.,
f ◊ f –1 = I (Identity function) = f –1 ◊ f
(see example 1.5)