Reflexive ,symmetric relation

Question

How many relations are reflexive or symmetric on set of n element?

Answer 1

Let's Take a Example

A={1,2,3}

A $\times$ A ={ (1,1)(2,2)(3,3)(1,2)(2,1)(1,3)(3,1)(2,3)(3,2) } 

Reflexive Relation :- A relation R on a set A is said to be Reflexive if  (xRx)∀x∈A  

$\underbrace{(1,1)(2,2)(3,3) }_{n}$$\underbrace{(1,2)(2,1)(1,3)(3,1)(2,3)(3,2) }_{n^{2}-n}$

Now For Reflexive relation there are only one choices for diagonal elements (1,1)(2,2)(3,3)

and For remaining n²-n elements there are 2 choices for each.Either it can include in relation or it can't include in relation.

Total number of reflexive relation = $1*2^{n^{2}-n} =2^{n^{2}-n}$

Symmetric Relation:- A relation 'R' on set A is said to be symmetric if (xRy)   then   (yRx) ∀x,y∈A

 

$\underbrace{(1,1)(2,2)(3,3) }_{n}$$\underbrace{(1,2)(2,1)(1,3)(3,1)(2,3)(3,2) }_{n^{2}-n}$

 

For n diagonal elements (1,1)(2,2)(3,3) there are 2 choices for each.Either it can include in relation or it can't include in relation.

For remaining n²-n elements according to definition of symmetric relation we can form pairs of(1,2)(2,1) and (1,3)(3,1)and (2,3)(3,2).For each pair there are 2 choices.Either it can include in relation or it can't not include in relation.

 

Hence,Total Number of Symmetric Relation= 2ⁿ*$2^{\frac{(n^{2}-n)}{2}}$=$2^{\frac{n(n+1)}{2}}$

 

 

Now For Reflexive and Symmetric relation there are only one choices for diagonal elements (1,1)(2,2)(3,3) and

for remaining.we can form pairs of(1,2)(2,1) and (1,3)(3,1)and (2,3)(3,2).For each pair there are 2 choices.Either it can include in relation or it can't not include in relation.

 

Hence,Total Number of Reflexive and Symmetric Relation = $2^{\frac{(n^{2}-n)}{2}}$=$2^{\frac{n(n-1)}{2}}$

 

 

n(R)=$2^{n^{2}-n}$

n(S)=$2^{\frac{n(n+1)}{2}}$

n(R∩S)=$2^{\frac{n(n-1)}{2}}$

Total number of relation which is Reflexive or Symmetric n(R∪S)= n(R) +n(S)-n(R∩S)

 

                                     = $2^{\frac{n(n+1)}{2}}+2^{n^{2}-n}-2^{\frac{n(n-1)}{2}}$

                                                                                         

 

Comments

thank you...very well explain

---

really helpful. Thanks

---

That's a precise explanation. Thanks.

Answer 2

Number of reflexive relations with n element set $2^{n^{2}-n}$

Number of symmetric relations 2ⁿ⨉$2^{\frac{n^{2}-n}{2}}$

Comments

Set A contains (1,2,3) elements 

Then total no of elements in A*A = 9 ie n²

(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3) 

Relation to be reflexive it must have (1,1)(2,2)(3,3) after that it may contain other elements or not 

remaining relations are 9-3 =6 

These 6 may or may not be present so 2⁶ ways to select 

Therefore total reflective relations are : 1* 2⁶

Please check my approach 

---

@Anjali yes, correct..

---

thanku sir:)

Answer 3

Reflexive relation::

A relation is called as refleive if and only if aRa or bRb where a and b both belong to relation R.

Let us assume we have set A={1,2,3}

Relation R=AxA={(1,1)(1,2),(1,3)

                          (2,1)(2,2)(2,3)

                          (3,1)(3,2)(3,3)}

Min Cardinality of reflexive relation =Number of diagonal element here=3 and max=9(3x3)

Suppose |A|=n

Min cardinality=n and max=nxn

Thene number of reflexive relation=1*2^n^2-n=2^n^2-n

For symmetric relation::

A relation  on a set  is symmetric provided that for every  and  in  we have  iff . The symmetric relations on  nodes are isomorphic with the rooted graphs on  nodes.

Number of Symmetric relation=2^n x 2^n^2-n/2