Properties of Relations

Solved Problems

Click or tap a problem to see the solution.

Example 1

The binary relation R = {(a, a), (a, b), (a, c), (b, b), (b, c), (c, c), (d, d)} is defined on the set A = {a, b, c, d}. Determine whether R is

1. reflexive
2. irreflexive
3. symmetric
4. antisymmetric
5. transitive

Example 2

The binary relation S = {(b, d), (c, a), (c, b), (c, d), (d, a)} is defined on the set A = {a, b, c, d} Determine whether S is

1. reflexive
2. irreflexive
3. symmetric
4. asymmetric
5. transitive

Example 3

Determine the properties of the binary relation $$R$$ represented by the digraph.

Example 4

Determine the properties of the binary relation $$T$$ represented by the digraph.

Example 5

A relation $$R$$ is defined on a set $$A$$ by its matrix $$M_R.$$ Determine the properties of the relation. ${M_R} = \left[ {\begin{array}{*{20}{c}} 1&0&0&1\\ 0&1&1&0\\ 0&1&1&0\\ 1&0&0&1 \end{array}} \right].$

Example 6

A relation $$S$$ is defined on a set $$A$$ by its matrix $$M_S.$$ Determine the properties of the relation. ${M_S} = \left[ {\begin{array}{*{20}{c}} 1&1&1&0\\ 0&1&0&1\\ 0&0&1&0\\ 1&0&1&0 \end{array}} \right].$

Example 1.

The binary relation $$R = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {a,c} \right),}\right.$$ $$\left( {b,b} \right),\left( {b,c} \right),\left( {c,c} \right),$$ $$\left.{\left( {d,d} \right)} \right\}$$ is defined on the set $$A = \left\{ {a,b,c,d} \right\}.$$ Determine whether $$R$$ is

1. reflexive
2. irreflexive
3. symmetric
4. antisymmetric
5. transitive

Solution.

1. The relation $$R$$ is reflexive since it contains all $$4$$ pairs $$\left( {a,a} \right),$$ $$\left( {b,b} \right),$$ $$\left( {c,c} \right),$$ and $$\left( {d,d} \right).$$
2. The relation $$R$$ is reflexive, so it cannot be irreflexive.
3. $$R$$ is not symmetric. For example, $$\left( {a,b} \right) \in R,$$ but $$\left( {b,a} \right) \notin R.$$
4. The relation $$R$$ is antisymmetric. It contains $$3$$ non-reflexive elements: $$\left( {a,b} \right),$$ $$\left( {a,c} \right),$$ and $$\left( {b,c} \right).$$ For each of the elements, its reverse does not belong to $$R.$$
5. $$R$$ is transitive. There is only one non-reflexive overlapping pair: $$\left( {a,b} \right)$$ and $$\left( {b,c} \right).$$ We see that $$\left( {a,b} \right),\left( {b,c} \right) \in R,$$ and $$\left( {a,c} \right) \in R.$$

Example 2.

The binary relation $$S = \left\{ {\left( {b,d} \right),\left( {c,a} \right),\left( {c,b} \right),}\right.$$ $$\left.{\left( {c,d} \right),\left( {d,a} \right)}\right\}$$ is defined on the set $$A = \left\{ {a,b,c,d} \right\}.$$ Determine whether $$S$$ is

1. reflexive
2. irreflexive
3. symmetric
4. asymmetric
5. transitive

Solution.

1. The relation $$S$$ is not reflexive since, for example, $$\left( {a,a} \right) \notin S.$$
2. The relation $$S$$ is irreflexive since it does not contain the diagonal elements $$\left( {a,a} \right),$$ $$\left( {b,b} \right),$$ $$\left( {c,c} \right),$$ and $$\left( {d,d} \right).$$
3. $$S$$ is not symmetric. For example, $$\left( {b,d} \right) \in S,$$ but $$\left( {d,b} \right) \notin S.$$
4. The relation $$S$$ is asymmetric since the reverse of every ordered pair is not an element of $$S.$$
5. $$S$$ is not transitive. For example, $$\left( {b,d} \right),\left( {d,a} \right) \in S,$$ but $$\left( {b,a} \right) \notin S.$$

Example 3.

Determine the properties of the binary relation $$R$$ represented by the digraph.

Solution.

The relation $$R$$ is not reflexive since not all set elements have loops on the graph.

$$R$$ is also not irreflexive because the digraph has self-loops for certain set elements.

The relation is not symmetric since there are edges that only go in one direction.

The relation $$R$$ is antisymmetric because there are no edges that go in the opposite direction for each edge.

$$R$$ is not transitive. For example, $$\left( {3,2} \right), \left( {2,1} \right) \in R,$$ but $$\left( {3,1} \right) \notin R.$$

Example 4.

Determine the properties of the binary relation $$T$$ represented by the digraph.

Solution.

The relation $$T$$ is reflexive since all set elements have self-loops on the digraph.

The relation $$T$$ is not irreflexive because it is already identified as reflexive.

$$T$$ is not symmetric since the graph has edges that only go in one direction.

The relation $$T$$ is antisymmetric because all edges of the graph only go one way.

$$T$$ is not transitive. The relation has the overlapping pair of elements $$\left( {1,2} \right)$$ $$\left( {2,4} \right),$$ but does not contain $$\left( {1,4} \right).$$

Example 5.

A relation $$R$$ is defined on a set $$A$$ by its matrix $$M_R.$$ Determine the properties of the relation. ${M_R} = \left[ {\begin{array}{*{20}{c}} 1&0&0&1\\ 0&1&1&0\\ 0&1&1&0\\ 1&0&0&1 \end{array}} \right].$

Solution.

The relation $$R$$ is reflexive since it has $$1\text{s}$$ on the main diagonal.

Since $$R$$ is reflexive, it cannot be irreflexive.

The relation $$R$$ is symmetric because the matrix $$M_R$$ coincides with its transpose $$M_R^T:$$

${M_R} = M_R^T = \left[ {\begin{array}{*{20}{c}}1&0&0&1\\0&1&1&0\\0&1&1&0\\1&0&0&1\end{array}} \right].$

The relation $$R$$ is transitive. The transitivity property is valid for all overlapping pairs:

${a_{32}} = 1,\;\;{a_{23}} = 1,\;\; \Rightarrow {a_{33}} = 1;$
${a_{23}} = 1,\;\;{a_{32}} = 1,\;\; \Rightarrow {a_{22}} = 1;$
${a_{14}} = 1,\;\;{a_{41}} = 1,\;\; \Rightarrow {a_{11}} = 1;$
${a_{41}} = 1,\;\;{a_{14}} = 1,\;\; \Rightarrow {a_{44}} = 1.$

Example 6.

A relation $$S$$ is defined on a set $$A$$ by its matrix $$M_S.$$ Determine the properties of the relation. ${M_S} = \left[ {\begin{array}{*{20}{c}} 1&1&1&0\\ 0&1&0&1\\ 0&0&1&0\\ 1&0&1&0 \end{array}} \right].$

Solution.

The relation $$S$$ is neither reflexive nor irreflexive. It is not reflexive because $$a_{44} = 0.$$ It is not irreflexive since there are $$1\text{s}$$ on the main diagonal.

$$S$$ is not symmetric since $$a_{12} = 1,$$ but $$a_{21} = 0.$$

The relation $$S$$ is antisymmetric since the reverse of every non-reflexive ordered pair is not an element of $$S.$$ However, $$S$$ is not asymmetric as there are some $$1\text{s}$$ along the main diagonal.

$$S$$ is not transitive because $$a_{12} = 1$$ and $$a_{24} = 1,$$ but $$a_{14} = 0.$$