Discrete Computational Structures

DISCRETE COMPUTATIONAL STRUCTURES
MODULE -2

RELATION STRUCTURES

Relations may exist between objects of the same set or between objects of
two or more sets.


Definition and Properties
A binary relation R from set x to y (written as xRy or R(x,y)) is a subset of
the Cartesian product x×Y. If the ordered pair of G is reversed, the relation
also changes.Generally an n-ary relation R between sets A1,…, and An is a
subset of the n-ary product A1×⋯×An. The minimum cardinality of a
relation R is Zero and maximum is n2 in this case.A binary relation R on a
single set A is a subset of A×A.For two distinct sets, A and B, having
cardinalities m and n respectively, the maximum cardinality of a relation R
from A to B is mn.


Domain and Range
If there are two sets A and B, and relation R have order pair (x, y), then −

● The domain of R, Dom(R), is the set {x|(x,y)∈R for some y in
B}
● The range of R, Ran(R), is the set {y|(x,y)∈R for some x in A}




Types of Relations
● The Empty Relation between sets X and Y, or on E, is the empty
∅.The Full Relation between sets X and Y is the set X×Y.
set
● The Identity Relation on set X is the set {(x,x)|x∈X}

, ● The Inverse Relation R' of a relation R is defined as −
R={(b,a)|(a,b)∈R} R′={(b,a)|(a,b)∈R}
′
● A relation R on set A is called Reflexive if ∀a∈A ∀a∈A is
related to a (aRa holds)
● A relation R on set A is called Irreflexive if no a∈A a∈A is
related to a (aRa does not hold).
● A relation R on set A is called Symmetric if xRy implies yRx
∀x∈A and ∀y∈A
● A relation R on set A is called Anti-Symmetric if xRy and yRx
implies x=y∀x∈A and ∀y∈A
● A relation R on set A is called Transitive if xRy and yRz implies
xRz,∀x,y,z∈A
● A relation is an Equivalence Relation if it is reflexive, symmetric,
and transitive.