25. What do you mean by a partial ordering relation?
A relation R on a set S is called a “partial ordering” or a “partial
order” if R is reflexive, antisymmetric and transitive.
26. What do you mean by a Poset?
A set S together with a partial ordering R is called a “Partially
ordered set” or “Poset”.
27. What do you mean by Partition?
A Partition P of S is a collection {A i } of nonempty subsets of S with
the properties:
(i) Each a S
∈ belongs to some A i ,
(ii) If A A
i
j
≠ , then A
A
i
j
∩
= ∅.
28. What is a function?
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 maps an element in its domain to an element in its
co-domain.
29. What do you mean by injection?
A one-to-one function is called an Injection. A function f A B
: → is
said to be one-to-one if different elements in the domain A has distinct
images in the range.
A function of is one-to-one if f a
f a
( )
( )
=
′ implies a a
= ′ .
30. Define Surjection.
An onto function is called a Surjection.
A function f A B
: → is said to be an onto function if each element of B
is the image of some element of A.
31. What do you mean by bijection?
A one-to-one onto function is called a bijection. A function that
maps each and every element of A to exactly one element of B, with no
elements left over is a one-to-one onto function.
32. What is an invertible function?
A function f A B
: → is invertible if its inverse relation f
–1 is a
function from B to A.
54
Theory of Automata, Formal Languages and Computation
a
b
c
x
y
z
domain
co-domain