Calculus

Set Theory

Set Theory Logo

Properties of Relations

A binary relation \(R\) defined on a set \(A\) may have the following properties:

  • Reflexivity
  • Irreflexivity
  • Symmetry
  • Antisymmetry
  • Asymmetry
  • Transitivity

Next we will discuss these properties in more detail.

Reflexive Relation

A binary relation \(R\) is called reflexive if and only if \(\forall a \in A,\) \(aRa.\) So, a relation \(R\) is reflexive if it relates every element of \(A\) to itself.

Examples of reflexive relations:

  1. The relation \(\ge\) (“is greater than or equal to”) on the set of real numbers.
  2. Similarity of triangles.
  3. The relation \({R = \left\{ {\left( {1,1} \right),\left( {1,2} \right),}\right.}\) \({\left.{\kern-2pt\left( {2,2} \right),\left( {3,3} \right),\left( {3,1} \right)} \right\}}\) on the set \(A = \left\{ {1,2,3} \right\}.\)
Logical matrix and digraph of a reflexive binary relation.
Figure 1.

Reflexive relations are always represented by a matrix that has \(1\) on the main diagonal. The digraph of a reflexive relation has a loop from each node to itself.

Irreflexive Relation

A binary relation \(R\) on a set \(A\) is called irreflexive if \(aRa\) does not hold for any \(a \in A.\) This means that there is no element in \(R\) which is related to itself.

Examples of irreflexive relations:

  1. The relation \(\lt\) (“is less than”) on the set of real numbers.
  2. Relation of one person being son of another person.
  3. The relation \({R = \left\{ {\left( {1,2} \right),\left( {2,1} \right),}\right.}\) \({\left.{\kern-2pt\left( {1,3} \right),\left( {2,3} \right),\left( {3,1} \right)} \right\}}\) on the set \(A = \left\{ {1,2,3} \right\}.\)
Logical matrix and digraph of an irreflexive binary relation.
Figure 2.

The matrix of an irreflexive relation has all \(0’\text{s}\) on its main diagonal. The directed graph for the relation has no loops.

Symmetric Relation

A binary relation \(R\) on a set \(A\) is called symmetric if for all \(a,b \in A\) it holds that if \(aRb\) then \(bRa.\) In other words, the relative order of the components in an ordered pair does not matter – if a binary relation contains an \(\left( {a,b} \right)\) element, it will also include the symmetric element \(\left( {b,a} \right).\)

Examples of symmetric relations:

  1. The relation \(=\) (“is equal to”) on the set of real numbers.
  2. The relation “is perpendicular to” on the set of straight lines in a plane.
  3. The relation \({R = \left\{ {\left( {1,1} \right),\left( {1,2} \right),}\right.}\) \({\left.{\kern-2pt\left( {2,1} \right),\left( {1,3} \right),\left( {3,1} \right)} \right\}}\) on the set \(A = \left\{ {1,2,3} \right\}.\)
Logical matrix and digraph of a symmetric binary relation.
Figure 3.

For a symmetric relation, the logical matrix \(M\) is symmetric about the main diagonal. The transpose of the matrix \(M^T\) is always equal to the original matrix \(M.\) In a digraph of a symmetric relation, for every edge between distinct nodes, there is an edge in the opposite direction.

Antisymmetric Relation

A binary relation \(R\) on a set \(A\) is said to be antisymmetric if there is no pair of distinct elements of \(A\) each of which is related by \(R\) to the other. So, an antisymmetric relation \(R\) can include both ordered pairs \(\left( {a,b} \right)\) and \(\left( {b,a} \right)\) if and only if \(a = b.\)

Examples of antisymmetric relations:

  1. The relation \(\ge\) (“is greater than or equal to”) on the set of real numbers.
  2. The subset relation \(\subseteq\) on a power set.
  3. The relation \({R = \left\{ {\left( {1,1} \right),\left( {2,1} \right),}\right.}\) \({\left.{\kern-2pt\left( {2,3} \right),\left( {3,1} \right),\left( {3,3} \right)} \right\}}\) on the set \(A = \left\{ {1,2,3} \right\}.\)
Logical matrix and digraph of an antisymmetric binary relation.
Figure 4.

In a matrix \(M = \left[ {{a_{ij}}} \right]\) representing an antisymmetric relation \(R,\) all elements symmetric about the main diagonal are not equal to each other: \({a_{ij}} \ne {a_{ji}}\) for \(i \ne j.\) The digraph of an antisymmetric relation may have loops, however connections between two distinct vertices can only go one way.

Asymmetric Relation

An asymmetric binary relation is similar to antisymmetric relation. The difference is that an asymmetric relation \(R\) never has both elements \(aRb\) and \(bRa\) even if \(a = b.\)

Every asymmetric relation is also antisymmetric. The converse is not true. If an antisymmetric relation contains an element of kind \(\left( {a,a} \right),\) it cannot be asymmetric. Thus, a binary relation \(R\) is asymmetric if and only if it is both antisymmetric and irreflexive.

Examples of asymmetric relations:

  1. The relation \(\gt\) (“is greater than”) on the set of real numbers.
  2. The family relation “is father of”.
  3. The relation \(R = \left\{ {\left( {2,1} \right),\left( {2,3} \right),\left( {3,1} \right)} \right\}\) on the set \(A = \left\{ {1,2,3} \right\}.\)
Logical matrix and digraph of an asymmetric binary relation.
Figure 5.

The matrix for an asymmetric relation is not symmetric with respect to the main diagonal and contains no diagonal elements. The digraph of an asymmetric relation must have no loops and no edges between distinct vertices in both directions.

Transitive Relation

A binary relation \(R\) on a set \(A\) is called transitive if for all \(a,b,c \in A\) it holds that if \(aRb\) and \(bRc,\) then \(aRc.\)

This condition must hold for all triples \(a,b,c\) in the set. If there exists some triple \(a,b,c \in A\) such that \(\left( {a,b} \right) \in R\) and \(\left( {b,c} \right) \in R,\) but \(\left( {a,c} \right) \notin R,\) then the relation \(R\) is not transitive.

Examples of transitive relations:

  1. The relation \(\gt\) (“is greater than”) on the set of real numbers.
  2. The relation “is parallel to” on the set of straight lines.
  3. The relation \({R = \left\{ {\left( {1,2} \right),\left( {1,3} \right),}\right.}\) \({\left.{\kern-2pt\left( {2,2} \right),\left( {2,3} \right),\left( {3,3} \right)} \right\}}\) on the set \(A = \left\{ {1,2,3} \right\}.\)
Logical matrix and digraph of a transitive binary relation.
Figure 6.

In a matrix \(M = \left[ {{a_{ij}}} \right]\) of a transitive relation \(R,\) for each pair of \(\left({i,j}\right)-\) and \(\left({j,k}\right)-\)entries with value \(1\) there exists the \(\left({i,k}\right)-\)entry with value \(1.\) The presence of \(1’\text{s}\) on the main diagonal does not violate transitivity.


Solved Problems

Click or tap a problem to see the solution.

Example 1

The binary relation \[{R = \left\{ {\left( {a,a} \right),\left( {a,b} \right),}\right.}\kern0pt{\left.{\left( {a,c} \right),\left( {b,b} \right),}\right.}\kern0pt{\left.{\left( {b,c} \right),\left( {c,c} \right),}\right.}\kern0pt{\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

Example 2

The binary relation \[{S = \left\{ {\left( {b,d} \right),\left( {c,a} \right),}\right.}\kern0pt{\left.{\left( {c,b} \right),\left( {c,d} \right),}\right.}\kern0pt{\left.{\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

Example 3

Determine the properties of the binary relation \(R\) represented by the digraph.
digraph of a relation - example1

Example 4

Determine the properties of the binary relation \(T\) represented by the digraph.
digraph of a relation - example2

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),}\right.}\kern0pt{\left.{\left( {a,c} \right),\left( {b,b} \right),}\right.}\kern0pt{\left.{\left( {b,c} \right),\left( {c,c} \right),}\right.}\kern0pt{\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),}\right.}\kern0pt{\left.{\left( {c,b} \right),\left( {c,d} \right),}\right.}\kern0pt{\left.{\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 transitive. The relation contains the overlapping pair of elements \(\left( {3,1} \right)\) \(\left( {1,2} \right), \) and the item \(\left( {3,2} \right). \) For \(\left( {3,2} \right),\) \(\left( {2,4} \right),\) there is the item \(\left( {3,4} \right).\) Similarly, for \(\left( {3,4} \right),\) \(\left( {4,5} \right),\) there is element \(\left( {3,5} \right)\) in the relation.

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