(b) R is not antisymmetric because 2R3 and 3R2 but 2 3
≠
(c) For each pair ( , )
a b R
∈ , determine all ( , )
b c R
∈ . As ( , )
,
a c R
∈
2
R
2
= (1,1), (2,2), (2,3), (3,2), (3,3), (4,2), (4,3)
{
}
, (4,4) .
Func tions
Suppose every element of S occurs exactly once as the first element of an
ordered pair. In Fig shown, every element of S has exactly one arrow arising
from it. This kind of relation is called a “function”.
A function is otherwise known as “Mapping”. A function is said to map an
element in its domain to an element in its range.
Every element in S in the domain, i.e., every element of S is mapped to
some elemet in the range. No element in the domain maps to more than one
element in the range.
Func tions as rela tions
A function f A B
: → is a relation from A to B i.e., a subset of A B
× , such that
each a A
∈ belongs to a unique ordered pair (a, b) in f.
Kinds of Func tions
(a) One-to-One Function (Injection): A function f A B
: → is said to be
one-to-one if different elements in the domain A have distinct images in the
range.
A function f is one-to-one if f a
f a
( )
( )
=
′ implies a a
= ′.
12
Theory of Automata, Formal Languages and Computation
a
b
c
w
x
y
z
Fig. An Injec tion (one to one func tion)
a
b
c
d
e
w
x
y
z
Fig. A Func tion