Relations and Functions
Unit – V
Part 1 - Relations
Prof. Sridhar K.R
If there are 4096 relations from the finite sets A and B with |B| = 3 then
find |A|?
Solution:
Let |A| = m and given |B| = n = 3.
Number of relations from A to B = 2mn = 4096
2m 3 = 4096
2 3 m = 212
3m = 12
m=4
|A| = 4
PROPERTIES OF RELATIONS
• A relation R on a set A is called empty relation, if no
element of A is related to any element of A,
i.e., R = ⊂ A × A.
• A relation R in a set A is called universal relation, if each
element of A is related to every element of A,
i.e., R = A × A.
Note: Both the empty relation and the universal relation are
sometimes called trivial relations.
A relation R on a set A is called reflexive if (a, a) ∈ R for every
element a ∈ A.
i.e., a A (a, a) R.
Example:
Which of the following relations on set A = {1, 2, 3, 4} are
reflexive?
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
A relation R on a set A is called symmetric if (b, a) ∈ R
whenever (a, b) ∈ R for all a, b ∈ A.
i.e., (a, b) R (b, a) R
Example:
Which of the following relations on set A = {1, 2, 3, 4} are
symmetric?
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)(3,1)},
A relation R on a set A is called transitive if whenever
(a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R, for all a, b, c ∈ A.
i.e., (a, b), (b, c) R (a, c) R
Example:
Which of the following relations on set A = {1, 2, 3, 4} are transitive?
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.
A relation R on a set A is called an Equivalence relation if it is reflexive, symmetric and
transitive.
Example:
Which of the following relations on set A = {1, 2, 3, 4} are Equivalence?
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (3, 3), (4, 1), (4, 2), (4, 4)},
R4 = {(1, 1), (1, 3), (2, 2), (3, 1), (3, 3), (3, 4), (4, 3), (4, 4)}
Relation Matrix:
Digraph of a Relation:
• The pictorial representation of a relation R is called a
directed graph or digraph of R.
• Let R be a relation on set A then the elements of set A are
called the vertices.
• If (x, y) R then draw a directed line from x to y which is
called an edge.
• An edge of the form (x, x) is represented using an arc from
the vertex x back to itself. Such an edge is called a loop.
• The number of edges terminating at a vertex is called the
in-degree of that vertex and the number edges leaving a
vertex are called the out-degree of that vertex.
Example:
The following figure is the directed graph or digraph for the
relation R = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)} on
set A = { a, b, c, d }
Vertices In-degree Out-degree
a 1 2
b 4 2
c 0 2
d 2 1
PROBLEMS
Suppose that A = {1, 2, 3} and B = {1, 2}. Let R be the relation
from A to B containing (a, b) if a ∈ A, b ∈ B, and a > b. Write
the matrix representing R.
Solution:
By definition of R, we have
R = {(2, 1), (3, 1), (3, 2)}.
By examining the entries in MR, we find that
R = {(a, 2), (b, 1), (b, 3), (b, 4), (c, 1), (c, 3), (c, 5)}.
By examining the entries in MR, we find that
R = {(a, a), (b, b), (b, c), (c, a), (c, b), (c, c), (d, b), (d, d)}
From the second digraph, we find that
PARTIAL ORDERINGS
A relation R on a set A is called a partial ordering or partial order
if it is reflexive, antisymmetric and transitive. A set A together with a
partial order R is called a partially ordered set or POSET and is denoted
by (A, R). Members of A are called elements of the POSET.
EXAMPLES
(Z, ) is a POSET.
Solution:
For any a Z, we have a a. Hence R is reflexive.
If a b and b a then a = b. Hence R is antisymmetric.
If a b and b c then a c. Hence R is transitive.
Thus R is a partial order.
(Z, ) is a POSET.
(Z, ) is a POSET.
Solution:
For any a Z, we have a a. Hence R is reflexive.
If a b and b a then a = b. Hence R is antisymmetric.
If a b and b c then a c. Hence R is transitive.
Thus R is a partial order.
(Z, ) is a POSET.
HASSE DIAGRAMS
The pictorial representation of a POSET is called a POSET diagram or Hasse
diagram.
• In other words, a Hasse diagram is a graphical rendering of a partially ordered
set displayed via the cover relation of the partially ordered set with an
implied upward orientation. A point is drawn for each element of the POSET
which is called a vertex in the plane and line segments or curves are drawn
between these points according to the following two rules:
• If x < y in the POSET, then the point corresponding to x
appears lower in the drawing than the point
corresponding to y.
• The line segment between the points corresponding to
any two elements x and y of the POSET is included in
the drawing iff x covers y or y covers x.
Note:
• For a POSET (A, ≤), one represents each element of A as a vertex in the plane
and draws a line segment or curve that goes upward from x to y whenever y
covers x (that is, whenever x < y and there is no z such that x < z < y). These
curves may cross each other but must not touch any vertices other than their
endpoints.
• In POSET, every element is related to itself, we eliminate self-loops in Hasse
diagram.
EXAMPLES
Show that the set A = {1, 2, 3, 4, 6, 8, 12} is a POSET with respect to the
relation R defined as {(a, b) : a divides b}and draw its Hasse diagram.
Solution:
Given, R = {(a, b) : a divides b} on set A = {1, 2, 3, 4, 6, 8, 12}.
(i) Every integer divides itself.
Hence, a A a divides a
(a, a) R.
Hence R is reflexive.
(ii) Let a R b and b R a a, b A
i.e., a divides b and b divides a
a = b.
Hence R is antisymmetric.
(iii) Let a R b and b R c
i.e., a divides b and b divides c
a divides c.
Hence R is transitive.
Thus R is a partial order.
(A, R) is a POSET.
Hasse diagram
Let S = {a, b, c} and P(S) be the power set of S. On P(S), define the relation R
by {(x, y) | x ⊆ y}. Show that this relation is a partial ordering on P(S). Draw its
Hasse diagram.
Solution:
The power set of S = {a, b, c} is given by
P(S) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}
(i) We know that every set is a subset of itself.
i.e., x P(S) x x
(x, x) R.
Hence R is reflexive.
(ii) Let x R y and y R x x, y P(S)
i.e., x y and y x
x = y.
Hence R is antisymmetric.
(iii) Let x R y and y R z
i.e., x y and y z
xz
Hence R is transitive.
Thus R is a partial order.
(P(S), R) is a POSET.
Hasse diagram
Draw the Hasse diagram of the POSET ({2, 4, 5, 10, 12, 20, 25}, | ).
Draw the Hasse diagram for the positive divisors of 30 under the divisibility
relation.
Let A = Positive divisors of 30 = {1, 2, 3, 5, 6, 10, 15, 30}
Hasse Diagram
Draw the Hasse diagram for the positive divisors of 36 under the divisibility relation.
Let A = Positive divisors of 36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}
Hasse Diagram
Draw the Hasse diagram for the positive divisors of 45
under the divisibility relation.
Let A = Positive divisors of 45 = {1, 3, 5, 9, 15, 45}
Hasse Diagram
