Mathematical Foundation of Computer Science

(Chris Devlin) #1
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
Free download pdf