Mathematical Foundation of Computer Science

DHARM

DISCRETE THEORY, RELATIONS AND FUNCTIONS 13

1.4.5 Ordering Relation (Partial Ordered Relation)

A binary relation R is said to be partial ordered relation if it is reflexive, antisymmetric, and

transitive. For example,

R = {(w, w), (x, x), (y, y), (z, z), (w, x), (w, y), (w, z), (x, y), (x, z)}

In a partial ordered relation objects are related through superior/inferior criterion.

For example,

l In the arithmetic relation ‘less than or equal to’ or ‘≤’ (or ‘greater than or equal to’ or

‘≥’) are partial ordered relations. Since, every number is equated to itself so it is re-

flexive. Also, if m and n are two numbers then ordered couple (m, n) ∈ R if m = n ⇒ n

≤/^ m so (n, m) ∉ R hence, relation is antisymmetric. Further, if (m, n) ∈ R and (n, k) ∈

R ⇒ m = n and n = k ⇒ m = k so (m, k) ∈ R hence, R is transitive.

In the next chapter we shall discuss the partial ordered relations in detail.

1.5 FUNCTION

Function is a relation. Function establishes the relationship between objects. For example, in

computer system input is fed to the system in form of data or objects and the system generates

the output that will be the function of input. So, function is the mapping or transformation of

objects from one form to other. In this section we will concentrate our discussion on function

and its classifications.

We are given two sets X and Y. A relation f from X to Y is called a function or mapping

i.e.

f : X → Y,

where f(x) = y, ∀x ∈ X and ∀y ∈ Y, and the triple (X, Y, f) is called morphism.

In general, sets X and Y in most instances are finite sets. Assume, | X | = m and | Y |

= n are the cardinalities of the sets. Then we may describe f by the expression,

f =

.... ( )......()

x

fx x

F

H

I
K ∈X
This we call as the standard representation of f : X → Y. Usually, the domain X and the
codomain (range) Y are totally ordered in some natural way, but , obviously any ordering is
possible. For example, the expressions

xxxx

yyyy

123 4

1122

F

HG

I

KJ,

xx xx

yyyy

1432

1221

F

HG

I

KJ,

xxxx

yyyy

4312

2211

F

HG

I

KJ

represents the same mapping f.

1.5.1 Classification of Functions...................................................................................

Let (X, Y, f ) be a morphism. With f : X → Y we define image img (f) and the argument arg(f),

where

img (f) = ∪

x∈

fx

X

() ;