UGC NET Computer Science December 2019 | Question 58

Question 58

---

How many reflexive relations are there on a set with 4 elements?

1. 1. 2⁴
2. 2. 2¹²
3. 3. 4²
4. 4. 2

Explanation

The number of reflexive relations on an set with n elements is 2^{n2 – 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 = n²
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 n² – n entries, there is choice to either include each entry in relation or not. There are total 2^{n2 – 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
= 2⁴²⁻⁴
= 2^{16 − 4}
= 2¹²

So, Option 2 is the right answer.

Previous	Next
UGC NET CS December 2019 - Question 57	UGC NET CS December 2019 - Question 59