# Calculus

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

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