Question

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

a) \(n = 1\) ?

b) \(n = 2\) ?

c) \(n = 3\) ?

Short answer

(a) 2

(b) 13

(c) 171

Step-by-step solution

Given Data

There is a set with \(n\) elements.

Concept of the transitive relation

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

Determine the transitive relations on the set

(a)

\(|A| = 1\)

Let us assume that \(a\) is the only element in \(A\). Then there is only one ordered pair on the set \(A\) :

\((a,a)\)

A relation on the set \(A\) contains any possible subset of the set of ordered pairs.

All possible relations are then:

\(\begin{array}{l}\emptyset {\rm{ Transitive }}\\\{ (a,a)\} {\rm{Transitive }}\end{array}\)

Thus we then note that there are 2 transitive relations on the set \(A\).

Determine the transitive relations on the set

(b)

\(|A| = 2\)

Let us assume that \(a\)and \(b\) are the only element in \(A\). Then there are 4 possible ordered pairs on the set \(A\):

\((a,a),(a,b),(b,a),(b,b)\)

A relation on the set \(A\)contains any possible subset of the set of ordered pairs.

The relation is then transitive, if it does not contain \(((a,b)\)and \(\left( {b,{\rm{ }}a} \right){\rm{ }})\)or contains all 4 elements. There are 13 such relations

Determine the transitive relations on the set

(c)

\(|A| = 3\)

Let the elements of \(A\) be \(a,b\) and \(c\)

All ordered pairs of the set \(\{ a,b,c,d\} \) are:

\((a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)\)

We then note that there are 9 ordered pairs.

For each of the 9 ordered 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 \ldots \cdot 2 = {2^9} = 512\)

Thus, there are 512 relations on the set \(A\).

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

Therefore,