UGC NET Computer Science December 2019 | Question 58
Question 58
How many reflexive relations are there on a set with 4 elements?
1. 24
2. 212
3. 42
4. 2
Explanation
The number of reflexive relations on an set with n elements is 2n2 – n
How does this formula work?
Let Assume that given set A = {a, b, ..., n } has n elements.
Reflexive Relation : A Relation R on a set A is said to be Reflexive if xRx for every element of x ∈ A.
Reflexive Relation will form matrix as shown below:
If we consider matrix, we can notice that the size of matrix is n*n = n2
To make relation R reflexive we have to keep all matrix diagonal entries in symmatric relation and all such entries are of the form (a,a) ∀ a ∈ R.
a
b
c
d
a
(a,a)
✓
✓
✓
b
✓
(b,b)
✓
✓
c
✓
✓
(c,c)
✓
d
✓
✓
✓
(d,d)
The n diagonal entries are fixed for symmatric relation.
For remaining n2 – n entries, there is choice to either include each entry in relation or not. There are total 2n2 – n ways of filling the matrix.
So, lets consider our case with 4 elements, then
Number of reflexive relations on a set with 4 elements
= 242−4
= 216 − 4
= 212
How does this formula work?
Let Assume that given set A = {a, b, ..., n } has n elements.
Reflexive Relation : A Relation R on a set A is said to be Reflexive if xRx for every element of x ∈ A.
Reflexive Relation will form matrix as shown below:
If we consider matrix, we can notice that the size of matrix is n*n = n2
To make relation R reflexive we have to keep all matrix diagonal entries in symmatric relation and all such entries are of the form (a,a) ∀ a ∈ R.
The n diagonal entries are fixed for symmatric relation.
For remaining n2 – n entries, there is choice to either include each entry in relation or not. There are total 2n2 – n ways of filling the matrix.
So, lets consider our case with 4 elements, then
Number of reflexive relations on a set with 4 elements
= 242−4
= 216 − 4
= 212
So, Option 2 is the right answer.