Set theory

Question

Let S be a set with n elements. How many relations on S are symmetric, anti-symmetric and transitive?  

(a) 2^n  

(b) n(n-1)/ 2  

(c) 0  

(d) 1

Comments

If a relation R is symmetric, antisymmetric and Transitive $⇒$ R may or may not be Reflexive.

Let's say S={1,2} , now to make R symmetric , antisymmetric and Transitive possible relations could be { }, { (1,1) }, { (2,2) },{ (1,1),(2,2) } so Total number of relations = 4.

Lets generalize it , if there is a set with n elements then no. of possible relations are $2^n$ where R is symmetric, antisymmetric and Transitive.

Answer 1

(a) $2^n$

Reason is simple. Question says relation should symmetric and anti-symmetric. This means if (a,b) appears then a=b because of anti-symmetric nature. Note that due to this transitivity has no effect here.

So there will be $n$ pairs. eg: (a,a), (b,b), (c,c), ..... 

Now the thing is every such pair has two choices: Appear or Not appear in the relation.

So total possible relations are: $2.2.2.2....2 = 2^n$