Rosen 9.1 - 48

Question

How many transitive relations are there on a set with n elements if

(a) n = 1

(b) n = 2

(c) n= 3

Answer has not been given. How do I calculate number of transitive relations?

For n = 1, there will be 1 transitive relation.

For n = 2, If $(a,b) \varepsilon R$ and $(b,a)\varepsilon R$ the $(a,a)\varepsilon R$ and $(b,b)\varepsilon R$. But how can we calculate this?

Comments

For n=1 there will be two (one is relation itself and other is phi) transitive relations. Rest i will answer soon . :-P

---

Thanks Digvijay. Please aswer with some explanation. In Wikipedia there is only a table.

Answer 1

 

(a) take only self loops (not necessarily all at a time). 4 options.

(b) There are two interconnecting lines.for Transitive relation select any edge (but not both). For each line case (a) occurs. So 2*22 = 8

(c) select all self loops all interconnecting edges i.e. whole relation. 1 relation.

Comments

Consider n=2,

(a) {(a,a), (b,b)}, {}, {(a,a)}, {(b,b)} - 4 choices [OK]

(c) {(a,a), (b,b)} - 1 choices [But we have already consider this in (a)]

Also in (b) there are relations which is repeating, isn't it??

Thanks Digvijay, it really helps.

---

See

(a) take only self loops (not necessarily all at a time). 4 options.

(b) There are two interconnecting lines.for Transitive relation select any edge (but not both). For each line case (a) occurs. So 2*2² = 8

(c) select all self loops all interconnecting edges i.e. whole relation. 1 relation.

Answer 2

https://en.wikipedia.org/wiki/Transitive_relation?wprov=sfla1

Answer 3

for n=2, there is one more easy method. Just count total number of relations for n=2 which is 2^2x2 = 16. Now remove those which are not transitive.

eg: if A={1,2} then, relations which will not be transitive will be - {(1,2),(2,1)}, {(1,2),(2,1),(1,1)},{(1,2),(2,1),(2,2)} which are 3. So total number of Transitive relations will be 16-3 = 13.