Relations

Question

For a set of n elements, what is the number of relations possible if:

1. Relation is neither Reflexive nor Irreflexive

2. Relation is Reflexive, Symmetric but not Anti-Symmetric.

Comments

Hint: Use Principle of Inclusion-Exclusion for solving this.

Answer 1

1.   Relation is neither Reflexive nor Irreflexive   =   $(2^n - 1 -1) \, \times (2^{n^2-n})$

For Counting of Relations, Use the Matrix Representation for ease. For a Relation to be Reflexive, All Main Diagonal Elements must be "1" and For a Relation to be Irreflexive, All Main Diagonal Elements must be "0", So, If a Relation is neither Reflexive nor Irreflexive, These Two cases must NOT be there (All Main Diagonal Elements  "0" or All Main Diagonal Elements  "1"), That's why  $(2^n - 1 -1)$ ... And We are free to assign any one of 0 or 1 to the remaining "n² - n" positions, that's why  $(2^{n^2-n})$

2.   Relation is Reflexive, Symmetric but not Anti-Symmetric   :   $(2^{(n^2-n)/2})  - 1$ 

We Subtract 1 because there is only one relation which is All Symmetric, Antisymmetric and Reflexive. 

Comments

Let suppose A = {1,2,3}

A * A ={ (1,1) (2,2),(3,3) (1,2) (1,3) (2,1) (2,3) (3,1) (3,2) }

R1 = { (1,1) }  (Relation is neither Reflexive nor Irreflexive)

R2 = { (1,1) (2,2) (3,3) (1,2) (2,1) } (Relation is Reflexive, Symmetric but not Anti-Symmetric)

Use hint and solve using Ven diagram. And apply Principle of Inclusion-Exclusion.

---

amazing 5* explanation