Answer to Question #130533 in Discrete Mathematics for Muhammad Nabeel

Question

How many transitive relatuon are there ona set with m elements

If m=1 , m=2 and m=3

Solve the question

Answer 1

A relation $R$ on a set $A$ is transitive if $(a, b)\in R, (b, c)\in R$ implies $(a, c)\in R.$

a) $m=1$

Let $a$ be the only element in $A.$ All possible relations are:

$(a, a)$ Transitive

$\text{\o}$ Transitive

There are two transitive relations on the set $A.$

b) $m=2$

Let $a, b$ be the elements in $A.$ Then there are 4 possible ordered pairs on the set $A$

$$(a, a), (a, b), (b, a), (b, b)$$

There are 16 relations in all. The only way a relation can fail to be transitive is to contain both $(a, b)$ and $(b, a)$. If the relation contains all four elements it is transitive.

Hence there are 13 transitive relations:

$\text{\o}, \{(a,a)\},\{(a,b)\},\{(b,a)\}, \{(b,b)\},$

$\{(a,a), (a,b)\},\{(a,a), (b,a)\},\{(a,a), (b,b)\},$

$\{(a,b), (b,b)\},\{(b,a), (b,b)\},$

$\{(a,a), (a,b),(b,b)\},\{(a,a), (b,a),(b,b)\},$

$\{(a,a), (a,b),(b,a)(b,b)\}$

There are 13 transitive relations on the set $A.$

c) $m=3$

Let $a, b$ and $c$ be the elements in $A.$ Then there are 9 possible ordered pairs on the set $A$

$$(a, a), (a, b), (a,c), (b, a), (b, b),(b,c),(c,a),(c,b),(c,c)$$

For each of the ordered 9 pairs, we have 2 choices: the element is in the set or the element is not in the set. By the product rule

$$2\cdot 2\cdot 2\cdot...\cdot2=2^9=512$$

There are 512 relations in all.

From https://en.wikipedia.org/wiki/Transitive_relation#Counting_transitive_relations

No general formula that counts the number of transitive relations on a finite set is known.

Using technology to generate all possible relations, we would then obtain 171 transitive relations among the 512 relations.