DHARM8 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
For example,
l For the sets X = {x 1 , x 2 } and Y = {y 1 , y 2 } then X × Y = {(x 1 , y 1 ), (x 1 , y 2 ), (x 2 , y 1 ), (x 2 , y 2 )}.
l Due to distinct ordering X × Y ≠ Y × X, hence these two sets are disjoints e.g.
(X × Y) ∩ (Y × X) = ∅.
l Let sets X = ∅ and Y ≠ ∅ then X × Y = ∅ and also Y × X = ∅.(S3) Rule of Products
Let Xk {for k = 1 to n}, is a finite family of finite sets, then for the Cartesian product Π
kn=to k
X
1
,
ΠΠ
kn=to k knto k
XX
11
=
=
| |1.4 Relations
The important aspect of the any set is the relationship between its elements. The association
of relationship established by sharing of some common feature proceeds comparing of related
objects. For example, assume a set of students, where students are related with each other if
their sir names are same. Conversely, if set is formed a class of students then we say that
students are related if they belong to same class etc. Hence, we say that a relation is a predefined
alliance of objects. The examples of relations are viz. husband and wife, brother and sister, and
mathematical relation such as less than, greater than, and equal etc. The relations can be
classifying on the basis of its association among the objects. For example, relations said above
are all association among two objects so these relations are called binary relation. Similarly,
relations of parent to their children, boss and subordinates, brothers and sisters etc. are the
examples of relations among three/more objects known as tertiary relation, quadratic rela-
tions and so on. In general an n-ary relation is the relation framed among n objects. In this
section we shall contemplate and study more about binary relation.
1.4.1 Binary Relation......................................................................................................
A relation between two objects is a binary relation and it is given by a set of ordered couples.
Let X and Y are two sets then a binary relation from set X to Y, denoted by XRY is a subset of
X × Y.
For example,
l Relation of husband and wife can be described by an ordered couple (h, w) i.e.
R = {(h, w)/h is husband of w}
l Let I+ is positive integer, then relation R i.e.
R = {( x, x}/x ∈ I+} defines the relation of square root of a positive integer.
Besides ordered couple representation, binary relations can also shown graphically and
through tabular form. Consider sets X = {x 1 , x 2 , x 3 }, Y = {y 1 , y 2 } and let a relation R = {(x 1 , y 1 ),
(x 1 , y 2 ), (x 2 , y 2 ), (x 3 , y 1 )}. Then relation R can be shown as Fig. 1.1 (a) and (b).
Consider another example of binary relation, Let X = {MCA01, MCA11, MCA17, MCA28,
MCA42} be a set of top five MCA students in a class and Y = {TCS, SAIL, HCL, OIL, WIPRO,
INFOSYS} be another set of companies offering jobs through campus selections. We may describe
a binary relation R 1 (shown in Fig 1.2) from X to Y such that students are called for interview
by the companies.