Relations

Question

Consider the set S = {a, b} and ‘L’ be a binary relation such that L = {all binary relations except reflexive relation set S}. The number of relation which are symmetric _______.

Comments

@manu00x
empty relation, {(a,a)}, {(b,b)} are not reflexive relations how??
here (aRa)  also (bRb) hence should be reflexive....correct me if I am wrong

---

@Sunania

empty relation is not reflexive because (a,a) and (b,b) are missing.

{(a,a)} is not reflexive relation because (b,b) is missing

{(b,b)} is not reflexive relation because (a,a) is missing

in a reflexive relation, all the diagonal pairs must exist.

---

"my bad" yes I got it....Thanks

Answer 1

Number of symmetric relations which are not reflexive

{ }

{(a,a)}

{(b,b)}

{(a,b),(b,a)}

{(a,a),(a,b),(b,a)}

{(a,b),(b,a),(b,b)}

Hence I think 6 should be the correct ans.

Comments

can u explain your answer please

Answer 2

Since it is small set,it can be done in hit and trial.But for more elements we should do it systematically.

We need to find number of relations which are symmetric but not reflexive

= [Total Symmetric] - [Symmetric and reflexive]

=[ $2 ^ {n(n+1)/2 }$] - [1*$2 ^ {n(n-1)/2 }$  ]

= 8-2

=6

Comments

How do we compute the number of symmetric AND reflexive relations. I only have idea about the individual number of symmetric relations i.e, 2^n(n+1)/2 and total number of reflexive relations i.e, 2^{n^2 - n}

---

If you consider n*n matrix. Now symmteirc and reflexive we need to find.Diagnal must be 1 for reflexive.Now remaining elements in will form n will form n(n−1)/2 pairs and for each pair we have two choices ,0 or 1, so 1*2^n(n−1)/2

---

Got it. Thanks :).

Answer 3

L  =  {all  binary relations  except  reflexive  relation  set  S}

=> L has no xRx pair

=> So no diagonal element present.

=> Total size of L = 2^(n² - n)

In symmetric relations, xRy and yRx should both come. For each x and y (x!=y), either (x,y) or (y,x) can be present.

Number of symmetric relations in L = (No diagonal element selected)*(One of the non-diagonal pairs)

No of non-diagonal pairs =  (n² - n)/2 

=> Number of symmetric relations =  2^((n² - n)/2)