Ajay Kumar Garg Engineering College, Ghaziabad

Relation

Unit: 1

Prof. Shraddha
Mishra

Prof. Shraddha Mishra Unit 1

1
Unit 1
Set Theory& Relations: Introduction, Combination of sets.
Relations: Definition, Operations on relations, Properties of relations,
Composite Relations, Equality of relations, Recursive definition of
relation, Order of relations.

POSET & Lattices: Hasse Diagram, POSET, Definition &

Properties of lattices – Bounded, Complemented, Distributed,
Modular and Complete lattice.

9/19/2024 2
 Cartesian product of two sets (CO1)

The Cartesian Product of two sets P and Q in that order is the set of all
ordered pairs whose first member belongs to the set P and second
member belong to set Q and is denoted by P x Q, i.e.,
P x Q = {(x, y): x P, y Q}

Example: Let P = {a, b, c} and Q = {k, l, m, n}. Determine the Cartesian

product of P and Q.
Solution: The Cartesian product of P and Q is

3
 Ordered Set & Ordered Pairs (CO1)

Ordered Set:
It is defined as the ordered collection of distinct objects.
Example:
Roll no {3, 6, 7, 8, 9}
Week Days {S, M, T, W, TH, F, S}

Ordered Pairs
An Ordered Pair consists of two elements such that one of them is designated
as the first member and other as the second member.

4
 Binary Relation (CO1)

Whenever sets are being discussed, the relationship between the

elements of the sets is the next thing that comes up. Relations may exist
between objects of the same set or between objects of two or more sets.
Let P and Q be two non- empty sets. A binary relation R is defined to be a
subset of P x Q from a set P to Q.

(i) Let A = {a, b, c} and B = {r, s, t}

Then R = {(a, r), (b, r), (b, t), (c, s)} is a relation from A to B.

(ii) Let A = {1, 2, 3} and B = A

Then R = {(1, 1), (2, 2), (3, 3)} is a relation (equal) on A.
Example1: If a set has n elements, how many relations are there from A to A.
Solution: If a set A has n elements, A x A has n2 elements. So, there are 2n2
relations from A to A.
5
 Binary Relation (CO1)

Example2: If A has m elements and B has n elements. How many relations

are there from A to B and vice versa?
Solution: There are m x n elements; hence there are 2m x n relations from A to
B.
Example3: If a set A = {1, 2}. Determine all relations from A to A.
Solution: There are 22= 4 elements i.e., {(1, 2), (2, 1), (1, 1), (2, 2)} in A x A.
So, there are 24= 16 relations from A to A. i.e.
{(1, 2), (2, 1), (1, 1), (2, 2)}, {(1, 2), (2, 1)}, {(1, 2), (1, 1)}, {(1, 2), (2, 2)},
{(2, 1), (1, 1)},{(2,1), (2, 2)}, {(1, 1),(2, 2)},{(1, 2), (2, 1), (1, 1)}, {(1, 2),
(1, 1), (2, 2)}, {(2,1), (1, 1), (2, 2)}, {(1, 2), (2, 1), (2, 2)}, {(1, 2), (2, 1), (1,
1), (2, 2)} and .

6
 Domain and Range of Relation (CO1)
Domain of Relation: The Domain of relation R is the set of elements in
P which are related to some elements in Q, or it is the set of all first
entries of the ordered pairs in R. It is denoted by DOM (R).

Range of Relation: The range of relation R is the set of elements in Q

which are related to some element in P, or it is the set of all second entries
of the ordered pairs in R. It is denoted by RAN (R).
Example:
Let A = {1, 2, 3, 4}
B = {a, b, c, d}
R = {(1, a), (1, b), (1, c), (2, b), (2, c), (2, d)}.
Solution:
7
 Complement of a Relation (CO1)

DOM (R) = {1, 2}

RAN (R) = {a, b, c, d}
Consider a relation R from a set A to set B. The complement of relation
R denoted by Rc is a relation from A to B such that Rc = {(a, b): {a, b)
R}.
Example:
Consider the relation R from X to Y
X = {1, 2, 3}
Y = {8, 9}
R = {(1, 8) (2, 8) (1, 9) (3, 9)} Find
the complement relation of R.
Solution:
X x Y = {(1, 8), (2, 8), (3, 8), (1, 9), (2, 9), (3, 9)}
8
Now we find the complement relation R from X x Y Rc
= {(3, 8), (2, 9)}

9
 Representation of Relations (CO1)

Relations can be represented in many ways. Some of which are as follows:

1. Relation as a Matrix: Let P = [a1,a2,a3,.......am] and Q =
[b1,b2,b3......bn] are finite sets, containing m and n number of elements
respectively. R is a relation from P to Q. The relation R can be
represented by m x n matrix M = [Mij], defined as

Mij = 0 if ( ai,bj ) ∉ R
1 if ( ai,bj ) ∈ R
Example
Let P = {1, 2, 3, 4}, Q = {a, b, c, d} and R = {(1, a),
(1, b), (1, c), (2, b), (2, c), (2, d)}.
The matrix of relation R is shown as fig:

10
 Representation of Relations (CO1)

2. Relation as a Directed Graph: There is another way of picturing a

relation R when R is a relation from a finite set to itself.
Example:
A = {1, 2, 3, 4}
R = {(1, 2) (2, 2) (2, 4) (3, 2) (3, 4) (4, 1) (4, 3)}

11
 Representation of Relations (CO1)

3. Relation as an Arrow Diagram: If P and Q are finite sets and R is a

relation from P to Q. Relation R can be represented as an arrow
diagram as follows.
Example:
Let P = {1, 2, 3, 4}
Q = {a, b, c, d}
R = {(1, a), (2, a), (3, a), (1, b), (4, b), (4, c), (4, d) The
arrow diagram of relation R is shown in fig:

12
 Representation of Relations (CO1)

4. Relation as a Table: If P and Q are finite sets and R is a relation from

P to Q. Relation R can be
represented in tabular form.
Example
Let P = {1, 2, 3, 4}
Q = {x, y, z, k}
R = {(1, x), (1, y), (2, z), (3, z),
(4, k)}.

The tabular form of relation as shown in fig:

13
 Composition of Relations (CO1)

Let A, B, and C be sets, and let R be a relation from A to B and let S be

a relation from B to C. That is, R is a subset of A × B and S is a subset
of B × C. Then R and S give rise to a relation from A to C indicated by
R◦S and defined by:
a (R◦S)c if for some b B we have aRb and bSc.
is,
R ◦ S = {(a, c)| there exists b B for which (a, b) R and (b, c) S}
The relation R◦S is known the composition of R and S; it is sometimes
denoted simply by RS.

Let R is a relation on a set A, that is, R is a relation from a set A to itself.

Then R◦R, the composition of R with itself, is always represented. Also,
R◦R is sometimes denoted by R2. Similarly, R3 = R2◦R = R◦R◦R, and so
on. Thus Rn is defined for all positive n.
14
 Composition of Relations (CO1)

Example1: Let X = {4, 5, 6}, Y = {a, b, c} and Z = {l, m, n}. Consider

the relation R1 from X to Y and R2 from Y to Z.
R1 = {(4, a), (4, b), (5, c), (6, a), (6, c)}
R2 = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}

Find the composition of relation (i) R1 o R2 (ii) R1o R1-1

15
 Composition of Relations (CO1)

Solution:
(i) The composition relation R1 o R2 as shown in fig:
R1 o R2 ={(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)}

(ii) The composition relation R1o R1-1 as shown in fig:

R1o R1-1 = {(4, 4), (5, 5), (5, 6), (6, 4), (6, 5), (4, 6), (6, 6)}

16
 Composition of Relations and Matrices (CO1)

There is another way of finding R◦S. Let MR and MS denote

respectively the matrix representations of the relations R and S. Then

Example:
Let P = {2, 3, 4, 5}. Consider the relation R and S on P defined by
R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3)}
S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2), (5, 5)}.
Find the matrices of the above relations. Use matrices to find the follow
ing composition of the relation R and S.
17
 Composition of Relations and Matrices (CO1)
(i)RoS (ii)RoR (iii)SoR
(i) To obtain the composition of relation R and S. First multiply MR with
MS to obtain the matrix MR x MS as shown in fig:
The non zero entries in the matrix MR x MS tells the elements related in

RoS. So,
Hence the composition R o S of the relation R and S is

18
 Composition of Relations and Matrices (CO1)

R o S = {(2, 2), (2, 3), (2, 4), (2,5),(3, 2), (3, 3), (3,5), (4, 2), (4, 5),
(5, 4), (5, 5)}.

(ii) First, multiply the matrix MR by itself, as shown in fig

Hence the composition R o R of the relation R and S is

19
 Composition of Relations and Matrices (CO1)

R o R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 3), (3, 5), (4, 3), (5, 4), (5, 5)}

(iii) Multiply the matrix MS with MR to obtain the matrix MS x MR as

shown in fig:
20
 Composition of Relations and Matrices (CO1)

The non-zero entries in matrix MS x MR tells the elements related in SoR.

Hence the composition S o R of the relation S and R is
SoR = {(2, 3), (2, 4), (2, 5), (3, 3), (3, 5), (4, 2), (4, 3),
(4, 4), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}.

21
 (Types of Relations)
1. Reflexive Relation
A relation R on set A is said to be a reflexive if (a, a) ∈ R for every a∈
A. Example: If A = {1, 2, 3, 4} then R = {(1, 1), (2, 2), (1, 3), (2, 4), (3, 3),
(3, 4), (4, 4)}. Is a relation reflexive?
Solution: The relation is reflexive as for every a A. (a, a) R, i.e. (1, 1),
(2, 2), (3, 3), (4, 4) R.
Ex. The total number of reflexive relations on a finite set having n
elements is __________.
Consider a set A with n elements Say A ={1, 2, ....... n } out of n2
elements n elements are compulsory for relation to be reflexive.
i.e (1, 1) (2, 2) (3, 3) .... (n, n) and for remaining n2-n

22
elements, we have choice of filling i.e either they are present or
absent. Hence, Total number of reflexive relation are 2(n2 – n)
2. Irreflexive Relation
A relation R on set A is said to be irreflexive if (a, a) ∉ R for every a ∈ A.
Example: Let A = {1, 2, 3} and R = {(1, 2), (2, 2), (3, 1), (1, 3)}. Is the
relation R reflexive or irreflexive?
Solution: The relation R is not reflexive as for every a ∈ A, (a, a) ∉ R, i.e.,
(1, 1), (2, 2) and (3, 3) ∉ R.
Note: There are total n pairs of (x, x) are present in the Cartesian
product which should not be included in an irreflexive relation.
Therefore, for the remaining (n2–n) elements, each element has

23
two choices i.e., either to include or exclude it in the subset. Hence,
the total number of possible irreflexive relations is given by 2(n2 –
n)
Ex. Consider the relation R on the set A={1,2,3,4} defined by
R={(1,1),(2,3),(2,4),(3,3),(3,4)}. Since(2, 2) ∉R, and (1, 1)∈R,
the relation is neither reflexive nor irreflexive.

Ex. How many relations are neither Reflexive nor Irreflexive.

Relation is neither Reflexive nor Irreflexive = (2n−1−1) × 2(n2–n) or 2n2-
2n2-n+1
For Counting of Relations, Use the Matrix Representation for ease. For a
Relation to be Reflexive, All Main Diagonal Elements must be "1" and For a
Relation to be Irreflexive, All Main Diagonal Elements must be "0", So, If a
Relation is neither Reflexive nor Irreflexive, These Two cases must NOT be

24
there (All Main Diagonal Elements "0" or All Main Diagonal Elements "1"),
That's why (2n−1−1) ... And We are free to assign any one of
0 or 1 to the remaining "n2 - n" positions, that's why 2(n2– n)

25
 3. Symmetric Relation:

A relation R on set A is said to be symmetric iff (a, b) ∈ R ⟺ (b, a) ∈ R.

• Relation ⊥r is symmetric since a line a is ⊥r to b, then b is ⊥r to a.
• Also, Parallel is symmetric, since if a line a is ∥ to b then b is also ∥
to a.
Example: Let A = {1, 2, 3} and R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3),
(3, 2)}. Is a relation R symmetric or not?
Solution: The relation is symmetric as for every (a, b) ∈ R, we have (b,
a) ∈ R, i.e., (1, 2), (2, 1), (2, 3), (3, 2) ∈ R but not reflexive because (3,
3) ∉ R.

26
 Total numbers Symmetric Relation?

Total number of symmetric relations is 2n(n+1)/2.

How does this formula work?
A relation R is symmetric if the value of every cell (i, j) is
same as that cell (j, i). The diagonals can have any value.

There are n diagonal values, total possible combination of

diagonal values = 2n
There are n2 – n non-diagonal values. We can only choose
different value for half of them, because when we choose a
value for cell (i, j), cell (j, i) gets same value. So
27
combination of non-diagonal values = 2(n2 – n)/2 Overall
combination = 2n * 2(n2 – n)/2 = 2n(n+1)/2

4. Antisymmetric Relation:
A relation R on a set A is antisymmetric iff (a, b) ∈ R and (b, a) ∈ R then
a = b.
∀a, b∈A, if (a, b) ∈R then (b, a) ∉R or a = b,
This means if an ordered pair of elements “a” to “b” (aRb) is present in
relation R then an ordered pair of elements “b” to “a” (bRa) should not
be present in relation R unless a = b.
Ex. Consider set A = {a, b}
• R = {(a, b), (b, a)} is not anti-symmetric relation as for (a, b) tuple
(b, a) tuple is present but
28
 R = {(a, a), (a, b)} is an anti-symmetric relation.
Example: Let A = {1, 2, 3} and R = {(1, 1), (2, 2)}. Is the relation R
antisymmetric?
Solution: The relation R is antisymmetric as a = b when (a, b) and (b, a)
both belong to R.

29
 Total number of Anti-Symmetric Relation?

A relation R is said to be an antisymmetric relation when if x and y

holds the relation R i.e., if xRy and yRx then, x = y. The formula for
calculating the total number of antisymmetric relations from a set
of n elements is 2n × 3 [n(n-1)]/2.

30
 30

Asymmetric Relation

A relation R on a set A is called asymmetric relation if

∀a, b ∈A, if (a, b) ∈R then (b, a) ∉R and vice versa,
This if an ordered pair of elements “a” to “b” (aRb) is present
in relation R then an ordered pair of elements “b” to “a” (bRa)
should not be present in relation R.
If any such bRa is present for any aRb in R then R is not an
asymmetric relation. Also, if any aRa is present in R then R is
not an asymmetric relation.
Ex. Consider set A = {a, b}

31
R = {(a, b), (b, a)} is not asymmetric relation but
R = {(a, b)} is asymmetric relation.
Total no of Asymmetric Relation:

• A relation R on a set A is a subset of the Cartesian product of

a set, i.e. A * A with N2 elements.
• There are total N pairs of type (x, x) that are present in the
Cartesian product, where any of (x, x) should not be included
in the subset.
• Now, one is left with (N2 – N) elements of the Cartesian
product.
• To satisfy the property of asymmetric relation, one has three
possibilities of either to include only of type (x, y) or only of
type (y, x) or none from a single group into the subset. • Hence,
32
 the total number of possible asymmetric relations is equal to 3
(N2 – N) / 2.
Difference Between Antisymmetric and asymmetric

• A relation, R, is antisymmetric if (a,b) in R implies (b,a) is not in R,

unless a=b. It is asymmetric if (a,b) in R implies (b,a) is not in R, even
if a=b
• In a antisymmetric relation ..the opposite of a set entity can't exist. For
eg for(1,2) ..(2,1) can't exist But 1,1 can..

• Antisymmetric Relation can be reflexive ie 1,1 can exist But

Asymmetric can't be reflexive ie 1,1 can't exist.
33
 6. Transitive Relations:
A Relation R on set A is said to be transitive iff (a, b) ∈ R and (b, c) ∈ R ⟺ (a, c) ∈
R.
Example1: Let A = {1, 2, 3} and R = {(1, 2), (2, 1), (1, 1), (2, 2)}. Is the relation
transitive?
Solution: The relation R is transitive as for every (a, b) (b, c) belong to R, we have
(a, c) ∈ R i.e, (1, 2) (2, 1) ∈ R ⇒ (1, 1) ∈ R.
Remember:
• No. of relations =2mn
• No. of reflexive relations =2 n(n-1)
• No. of irreflexive relations = 2 n(n-1)
• No. of symmetric relations = 2 n(n+1)/2
• No. of asymmetric relations = 3 n(n-1)/2
• No. of Anti Symmetric Relations = 2 n * 3 n(n-1)/2

34
• There is No general formula to counts the number of transitive relations on a
finite set.
Types of Relations (CO1)

Note1: The Relation ≤, ⊆ and / are transitive, i.e., a ≤ b, b ≤ c then a ≤ c

(ii) Let a ⊆ b, b ⊆ c then a ⊆ c
(iii) Let a/b, b/c then a/c

Note2: ⊥r is not transitive since a ⊥r b, b ⊥r c then it is not true that a ⊥r

c. Since no line is ∥ to itself, we can have a ∥ b, b ∥ a but a ∦ a.
Thus ∥ is not transitive, but it will be transitive in the plane.

35
 Types of Relations (CO1)

7. Identity Relation: Identity relation I on set A is reflexive, transitive

and symmetric. So identity relation I is an Equivalence Relation.
Example: A= {1, 2, 3} = {(1, 1), (2, 2), (3, 3)}

8. Void Relation: It is given by R: A →B such that R = ∅ (⊆ A x B) is a

null relation. Void Relation R = ∅ is symmetric and transitive but not
reflexive.

9. Universal Relation: A relation R: A →B such that R = A x B (⊆ A x

B) is a universal relation. Universal Relation from A →B is reflexive,
symmetric and transitive. So this is an equivalence relation.

36
 Closure Properties of Relations (CO1)

(1) Reflexive and Symmetric Closures: The next theorem tells us how
to obtain the reflexive and symmetric closures of a relation easily.

Theorem: Let R be a relation on a set A. Then:

• R ∆A is the reflexive closure of R
• R R-1 is the symmetric closure of R.

37
 Closure Properties of Relations (CO1)

Example1: Let A = {k, l, m}. Let R is a relation on A defined by R

= {(k, k), (k, l), (l, m), (m, k)}.
Find the reflexive closure of R.
Solution: R ∆ is the smallest relation having reflexive property, Hence,
RF = R ∆ = {(k, k), (k, l), (l, l), (l, m), (m, m), (m, k)}.

Example2: Consider the relation R on A = {4, 5, 6, 7} defined by

R = {(4, 5), (5, 5), (5, 6), (6, 7), (7, 4), (7, 7)} Find the
symmetric closure of R.
Solution:
The smallest relation containing R having the symmetric property
is R R-1,i.e. RS = R R-1 =
{(4, 5), (5, 4), (5, 5), (5, 6), (6, 5), (6, 7), (7, 6), (7, 4), (4, 7), (7, 7)}.
38
 Closure Properties of Relations (CO1)

(2)Transitive Closures: Consider a relation R on a set A. The transitive

closure R of a relation R of a relation R is the smallest transitive relation
containing R.
Recall that R2 = R◦ R and Rn = Rn-1 ◦ R. We define

The following Theorem applies:

Theorem1: R* is the transitive closure of R
Suppose A is a finite set with n elements.
R* = R R2 ..... Rn

39
 Closure Properties of Relations (CO1)

Theorem 2: Let R be a relation on a set A with n elements. Then

Transitive (R) = R R2 ..... Rn

40
 Closure Properties of Relations (CO1)

Example1: Consider the relation R = {(1, 2), (2, 3), (3, 3)} on A = {1,
2, 3}.
Then
R2 = R◦ R = {(1, 3), (2, 3), (3, 3)} and
R3 = R2 ◦ R = {(1, 3), (2, 3), (3, 3)}
Accordingly,
Transitive (R) = {(1, 2), (2, 3), (3, 3), (1, 3)}

41
 Closure Properties of Relations (CO1)

Example2: Let A = {4, 6, 8, 10} and R = {(4, 4), (4, 10), (6, 6), (6, 8),
(8, 10)} is a relation on set A. Determine transitive closure of R.
Solution: The matrix of relation R is shown in fig:

42
 Closure Properties of Relations (CO1)
Now, find the powers of MR as in fig:

Hence, the transitive closure of MR is MR* as shown in Fig (where

MR* is the ORing of a power of MR)
Thus, R* = {(4, 4), (4, 10), (6, 8), (6, 6), (6, 10), (8, 10)}

43
44
 Equivalence Relation(CO1)
Consider the set of every person in the world
Now consider a R relation such that (a,b) R if a and b are siblings.
Clearly this relation is
➢ Reflexive
➢ Symmetric, and
➢ Transitive
Such as relation is called an equivalence relation.
Definition: A relation on a set A is an equivalence relation if it is
reflexive, symmetric, and transitive
Example: Let R={ (a,b) | a, b R and a b}
➢ Is R
reflexive?
45
 ➢ Is it
transitive?
➢ Is it
symmetric?
No, it is not. 4 is related to 5
(4 5) but 5 is not related to 4
Thus R is not an equivalence relation

46
 Equality of a relation(CO1)

Definition(Equality of binary relation):

•Two binary relations R1 A1 x A2 and R2 B1 x B2 are equal if and

only if A1 = B1 , A2 = B2 , and R1 = R2 as a set.

•For example, let R1 = {(1, 2) , (1, 2)} {1, 2} x {1, 2} and R2 = {(a, b) ,
(a, b)} {a, b} x {a, b} . Then R1 = R2 if and only if a = 1 and b = 2.

47
 Recursive definition of Relation

Definition (Equality of n-ary relation): An n-ary relation R1 A1 x A2

……. An and an m-ary relation R2 B1 x B2 ……. Bm are equal if and only
if m = n, Ai = Bi for each i, 1 i n and R1 = R2 as a set of ordered n-
tuples.

The procedure for finding the terms of a sequence in a recursive manner

is called recurrence relation.
Def: A recurrence relation is an equation that recursively defines a
sequence where the next term is a function of the previous terms .
Recursive definition consists of three steps:
Basis Step: Specify the primitive elements( at least one)

48
Recursive Step: Rules for generating new elements from existing
elements
Terminal Step: Guarantees that the first two basis and recursive clauses,
are the only way the elements can be obtained.

Fn = Fn-1 + Fn-2 F1 = F2 = 1 Fibonacci number

Fn = Fn-1 + Fn-2 F1 = 1, F2 = 3 Lucas Number

49
 How to solve linear recurrence relation

Suppose, a two ordered linear recurrence relation is Fn=A Fn-1+B Fn-2 where A and
B are real numbers.
The characteristic equation for the above recurrence relation is x2−Ax−B=0
Case 1: If this equation factors as (x−x1)(x−x2)=0 and it produces two distinct real
roots x1 and x2, then Fn =a x1n + b x2n is the solution. [Here, a and b are constants]
Case 2: If this equation factors as (x−x1)2=0 and it produces single real root x1 then
Fn= a x1n + b n x1n is the solution.
Prob1: Solve the recurrence relation Fn =5 Fn−1−6 Fn−2 where F0=1 and F1=4
Solution is Fn=2.3n+(−1).2n
Prob2: Solve the recurrence relation Fn =10 Fn−1−25 Fn−2where F0 =3 and F1=17

50
 Imp questions on Relation (CO1)

Final solution is Fn =3.5n+(2/5).n.2n

51
52
Imp questions on Relation (CO1)

53
Imp questions on Relation (CO1)

54
Imp questions on Relation (CO1)

55
Imp questions on Relation (CO1)

56
Imp questions on Relation (CO1)

57
Imp questions on Relation (CO1)

THANKS

58