Calculus

Set Theory

Set Theory Logo

Counting Relations

Solved Problems

Example 1.

How many relations are there on a set of \(n\) elements that are reflexive and symmetric?

Solution.

Consider a set \(A\) consisting of \(n\) elements and a relation \(R.\) Since \(R\) is reflexive, its binary matrix must contain the diagonal elements \(\left( {a,a} \right)\) for every \(a \in A.\)

The number of remaining off-diagonal elements is equal to \(n^2 - n.\) If the relation \(R\) is symmetric and has a non-diagonal element \(\left( {a,b} \right)\) where \(a \ne b,\) then it also includes the opposite element \(\left( {b,a} \right).\) It is clear that it is enough to consider all options in the left lower (or in the right upper) triangle of the matrix. Each of the triangles contains \(\frac{{{n^2} - n}}{2}\) elements.

Hence, there are

\[{2^{\frac{{{n^2} - n}}{2}}} = {2^{\frac{{n\left( {n - 1} \right)}}{2}}} = \sqrt {{2^{n\left( {n - 1} \right)}}} \]

relations on the set \(A\) that are simultaneously reflexive and symmetric.

Example 2.

How many relations are there on a set of \(n\) elements that are reflexive and antisymmetric?

Solution.

If a relation \(R\) on set \(A\) is reflexive, its matrix must include the diagonal elements \(\left( {a,a} \right)\) for all \(a \in A.\) We do not count these elements.

The number of the remaining off-diagonal elements is equal to \(n^2 - n.\) These elements form the pairs \(\left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\) where \(a \ne b.\) Total there are \(\frac{{{n^2} - n}}{2}\) such pairs.

There are \(3\) possible options for each pair. We can choose either \({\left( {a,b} \right)}\) or \({\left( {b,a} \right)},\) or none of them.

Consequently, there are

\[{3^{\frac{{{n^2} - n}}{2}}} = {3^{\frac{{n\left( {n - 1} \right)}}{2}}} = \sqrt {{3^{n\left( {n - 1} \right)}}} \]

elations that are reflexive and antisymmetric.

Example 3.

How many relations are there on a set of \(n\) elements that are neither reflexive nor irreflexive?

Solution.

A relation \(R\) on a set \(A\) is reflexive if it contains all diagonal elements of kind \(\left( {a,a} \right)\) where \(a \in A.\) There are \({2^{{n^2} - n}}\) distinct reflexive relations on the set \(A.\)

Similarly, if \(R\) is irreflexive it does not include the diagonal elements \(\left( {a,a} \right)\) for all \(a \in A.\) The number of irreflexive relations is the same and equal to \({2^{{n^2} - n}}.\)

Given the the total number of relations is \({2^{{n^2}}},\) we find the number of relations \(N\) that are neither reflexive nor irreflexive:

\[N = {2^{{n^2}}} - 2 \cdot {2^{{n^2} - n}} = {2^{{n^2}}} - {2^{{n^2} - n + 1}} = {2^{{n^2}}}\left( {1 - {2^{1 - n}}} \right).\]

Example 4.

Let \(B = \left\{ {0,1} \right\}.\) How many relations on the set \(B\) are not symmetric?

Solution.

The total number of relations on a set of \(2\) elements is

\[{R_2} = {2^{{2^2}}} = {2^4} = 16.\]

The number of symmetric relations on the set is given by

\[{S_2} = \sqrt {{2^{2\left( {2 + 1} \right)}}} = \sqrt {{2^6}} = {2^3} = 8.\]

Then there are \(16-8=8\) relations on set \(B = \left\{ {0,1} \right\}\) that are not symmetric. These relations are shown in figure below.

Not symmetric relations on the binary set {0,1}.
Figure 2.

Example 5.

Let \(A = \left\{ {a,b,c} \right\}.\) How many relations on the set \(A\) are reflexive, symmetric, and not transitive?

Solution.

If we consider only reflexive and symmetric relations, there are

\[{RS_3} = \sqrt {{2^{n\left( {n - 1} \right)}}} = \sqrt {{2^{3 \cdot 2}}} = {2^3} = 8\]

such relations.

Recall that if a relation is reflexive, symmetric, and transitive, it is called an equivalence relation. The set \(A\) of \(3\) elements contains \(B_3 = 5\) equivalence relations.

Hence, the number of relations that are reflexive, symmetric, but not transitive is equal to

\[N = R{S_3} - {B_3} = 8 - 5 = 3.\]

These \(3\) relations look as follows:

Relations on set {a,b,c} that are symmetric, reflexive and not transitive.
Figure 3.
Page 1 Page 2