Mathematical Foundation of Computer Science

DHARM

DISCRETE THEORY, RELATIONS AND FUNCTIONS 15

We find that at x = 0 ⇒ f(0) = 0 % 5 = 0; at x = 1 ⇒ f(1) = 1 % 5 = 1; at x = 2 ⇒ f(2) = 2 %

5 = 2; at x = 3 ⇒ f(3) = 3 % 5 = 3; and x = 4 ⇒ f(4) = 4 % 5 = 4. Since, img (f) = P and arg(f) = 0

(that is no element left in the argument set), therefore mapping is bijective, or function is

bijective.

(B). Let X = {1< 2 < 3 < 4} and

Y =

d

c

a

b

are partial ordered sets. Then classify the following function (f : X → Y) expressions,

(i)f =

1234

abcd

F

H

I

K (ii)f =

1234

dbca

F

H

I
K
For the solution of (i) since we know that if function preserved the partial ordered rela-
tion then it is monotone, i.e., if x 1 ≤ x 2 then f(x 1 ) ≤ f(x 2 ) for all x 1 , x 2 ∈ X. Since, first row of the
expression consists of the elements of X, i.e. there ordering is 1 < 2 < 3 < 4 and the second row
of the expression consists of image elements of Y, i.e. there ordering is a < b < c < d. Thus we
have,
1 < 2 < 3 < 4 ⇒ f(1) < f(2) < f(3) < f(4) ⇒ a < b < c < d
Therefore, function is monotone.
In the given function (ii) we have the ordering of the elements shown in the first row of
the expression is 1 < 2 < 3 < 4 and the ordering of their corresponding image elements is d > b

c > a. Thus we have,
1 < 2 < 3 < 4 ⇒ f(1) > f(2) > f(3) > f(4) ⇒ d > b > c > a
Therefore, function is antitone.
Example 1.6. Let X = {1, 2, 3}< and Y = {a, b, c}< are partial ordered sets. Compute | f : X → Y|
when, (1) f is arbitrary, (2) f is surjective, (3) f is injective, (4) f is bijective, (5) f is monotone, and
(6) f is antitone.
Sol. We first list the set of possible strings generated by the arbitrary function f, which is
shown in Fig. 1.6.
123

aa a acc aba caa cbc acb

aab ccc baa cac ccb bac

abb bbc bab cca cab

bbb bcc bba bcb bca

aac abc aca cbb cba

Fig. 1.6