Calculus

Set Theory

Set Theory Logo

Counting Relations

In this lesson, we will be looking at counting relations with different properties.

Recall that a binary relation \(R\) from set \(A\) to set \(B\) is defined as a subset of the Cartesian product \(A \times B.\) If these sets are finite and have cardinality \(\left| A \right| = n\) and \(\left| B \right| = m,\) then the cardinality of their Cartesian product is given by

\[\left| {A \times B} \right| = \left| A \right| \times \left| B \right| = nm.\]

Hence, the number of subsets of \(A \times B\) or the number of relations from \(A\) to \(B\) is

\[{2^{\left| {A \times B} \right|}} = {2^{nm}}.\]

In particular, the number of relations defined on one set \(A\) of cardinality \(n\) is equal to \({2^{{n^2}}}.\)

Binary relations may have different properties such as reflexivity, symmetry, transitivity and so on. Further, we consider how many relations of different type exist on a set \(A\) consisting of \(n\) elements.

Reflexive Relations

A reflexive relation on set \(A\) must contain the \(n\) elements \(\left( {a,a} \right)\) for every \(a \in A.\) The remaining number of pairs is \(n^2 – n.\) So we can choose only among \(n^2 – n\) elements to build reflexive relations. Hence, there are

\[{2^{{n^2} – n}} = {2^{n\left( {n – 1} \right)}}\]

reflexive relations on a set with cardinality \(n.\)

An irreflexive relation is the opposite of a reflexive relation. It contains no identity elements \(\left( {a,a} \right)\) for all \(a \in A.\) It is clear that the total number of irreflexive relations is given by the same formula as for reflexive relations.

Symmetric Relations

As we know a binary relation corresponds to a matrix of zeroes and ones. A symmetric relation is described by a symmetric matrix such as the one in figure below.

An example of matrix representing a symmetric relation.
Figure 1.

In a symmetric matrix, \(a_{ij} = a_{ji}.\) So choosing a value for an element in the left lower triangle determines the corresponding element in the right upper triangle. The number of the off-diagonal elements is \(n^2 – n.\) Respectively, the number of elements in the lower or upper triangle is equal to \(\large{\frac{{{n^2} – n}}{2}}\normalsize.\) Hence, there are \({2^{\large{\frac{{{n^2} – n}}{2}}\normalsize}}\) ways to set the off-diagonal elements in the relation. Besides that, there are \(2^n\) ways to set diagonal elements that may take any values. Therefore, the total number of symmetric relations on a set with cardinality \(n\) is defined by the formula

\[{{2^n} \cdot {2^{\frac{{{n^2} – n}}{2}}} }={ {2^{n + \frac{{{n^2} – n}}{2}}} }={ {2^{\frac{{{n^2} + n}}{2}}} }={ {2^{\frac{{n\left( {n + 1} \right)}}{2}}} }={ \sqrt {{2^{n\left( {n + 1} \right)}}} .}\]

Antisymmetric Relations

Antisymmetric relations have no restrictions on the diagonal elements \(\left( {a,a} \right),\) so there are \(2^n\) ways to set such elements. As to the non-diagonal elements, there are \(3\) options for each pair \(\left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\) where \(a \ne b.\) An antisymmetric relation may contain either \({\left( {a,b} \right)}\) or \({\left( {b,a} \right)},\) or none of them. Therefore, there are \({3^{\large{\frac{{{n^2} – n}}{2}}\normalsize}}\) ways to set the off-diagonal elements. The total number of antisymmetric relations is given by the expression

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

Asymmetric Relations

A binary relation is called asymmetric if it is both antisymmetric and irreflexive. Thus an asymmetric relation does not contain the diagonal elements \(\left( {a,a} \right).\) The total number of asymmetric relations on a set with \(n\) elements is expressed by the formula

\[\sqrt {{3^{n\left( {n – 1} \right)}}} .\]

Transitive Relations

Finding the number of transitive relations on a set with \(n\) elements is not a simple problem. As of \(2020,\) there is no known closed-form formula to count the number of transitive relations. Of course, such calculations can be performed numerically. The sequence OEIS A006905 thus defined describes the number of transitive relations \(T_n\) on a finite set with cardinality \(n.\) The first few values in this sequence are listed below.

\[{T_0 = 1,\;\;}\kern0pt{T_1 = 2,\;\;}\kern0pt{T_2 = 13,\;\;}\kern0pt{T_3 = 171,\;\;}\kern0pt{T_4 = 3994.}\]

Equivalence Relations

The number of equivalence relations on a set is equal to the number of partitions. These numbers are known as Bell numbers. The first few Bell numbers are given by

\[{{B_0} = 1,\;\;}\kern0pt{{B_1} = 1,\;\;}\kern0pt{{B_2} = 2,\;\;}\kern0pt{{B_3} = 5,\;\;}\kern0pt{{B_4} = 15.}\]

For example, the set \(A = \left\{ {a,b,c} \right\}\) consists of \(3\) elements and therefore has \(B_3 = 5\) partitions:

\[\left\{ {\left\{ a \right\},\left\{ b \right\},\left\{ c \right\}} \right\},\]

\[\left\{ {\left\{ {a,b} \right\},\left\{ c \right\}} \right\},\]

\[\left\{ {\left\{ {a,c} \right\},\left\{ b \right\}} \right\},\]

\[\left\{ {\left\{ a \right\},\left\{ {b,c} \right\}} \right\},\]

\[\left\{ {\left\{ {a,b,c} \right\}} \right\}.\]

Bell numbers can be computed using the following recursive equation:

\[{B_{n + 1}} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right){B_k}}, \]

where \(\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right)\) are the binomial coefficients.

Partial Orders

Similarly to transitive relations, there is no closed formula to count the number of partial orders on a set. This number is represented by the sequence OEIS A001035. The first several values are

\[{{P_0} = 1,\;\;}\kern0pt{{P_1} = 1,\;\;}\kern0pt{{P_2} = 3,\;\;}\kern0pt{{P_3} = 19,\;\;}\kern0pt{{P_4} = 219.}\]

Total Orders

The number of total orders on a set of cardinality \(n\) is equal to the number of permutations on the set. Hence, the number of total orders is \(n!\)


Solved Problems

Click or tap a problem to see the solution.

Example 1

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

Example 2

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

Example 3

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

Example 4

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

Example 5

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

Example 6

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

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 \(\large{\frac{{{n^2} – n}}{2}}\normalsize\) 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 \(\large{\frac{{{n^2} – n}}{2}}\normalsize\) 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)}}} }\]

relations 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.

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

Solution.

Both symmetric and antisymmetric relations have no restrictions on the diagonal elements \(\left( {a,a} \right)\) for all \(a \in A.\)

As for the off-diagonal elements, symmetric and antisymmetric relations have mutually exclusive requirements. For a symmetric relation, both elements of a pair \(\left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\}\) where \(a \ne b,\) must belong to the relation. An antisymmetric relation may have either one element of a pair \(\left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\) or none of them.

Therefore, the relations that are neither symmetric nor antisymmetric may contain only diagonal elements. There are \(2^n\) such relations.

Example 5.

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 6.

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.