# Calculus

## Set Theory # 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.

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.

### 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: