Calculus

Set Theory

Set Theory Logo

Properties of Relations

Solved Problems

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.

digraph of a relation - example1

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.

digraph of a relation - example2

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.\)

Page 1 Page 2