Skip to main content
Logo image

Section 17.3 Properties of relations

Here we list some important properties a relation \(R\) on a set \(A\) can have.

Subsection 17.3.1 Reflexivity

reflexive
\(a \mathrel{R} a\) is true for all \(a \in A\)

Example 17.3.1. A reflexive and a non-reflexive relation on the set of real numbers.

The relation \(\mathord{\le}\) on \(\R\) is reflexive, but the relation \(\mathord{\lt}\) is not.

Subsection 17.3.2 Symmetry and antisymmetry

symmetric
for every pair of elements \(a_1,a_2 \in A\) for which \(a_1 \mathrel{R} a_2\) is true, \(a_2 \mathrel{R} a_1\) is also true

Example 17.3.3. Sibling relation is symmetric, brother/sister relation is not.

On the set of all living humans, the relation “\(a\) is the sibling of \(b\)” is symmetric, but neither the relation “\(a\) is the brother of \(b\)” nor the relation “\(a\) is the sister of \(b\)” is symmetric.
antisymmetric
for every pair of distinct elements \(a_1,a_2 \in A\text{,}\) either \(a_1\ \not R\ a_2\) or \(a_2\ \not R\ a_1\) (or both)

Remark 17.3.5.

The distinct part of the definition is important, since if \(a_1,a_2 \in A\) are not distinct (i.e. \(a_2 = a_1\)), then obviously both \(a_1 \mathrel{R} a_2\) and \(a_2 \mathrel{R} a_1\) can be simultaneously true because they are the same statement.

Example 17.3.6. An antisymmetric relation on real numbers.

The relation \(\mathord{\le}\) on \(\R\) is antisymmetric.

Example 17.3.7. A relation can be neither antisymmetric nor symmetric.

On \(A = \{a,b,c\}\text{,}\) the relation
\begin{equation*} R = \{(a,b),(b,a),(a,c)\} \subseteq A \cartprod A \end{equation*}
is neither antisymmetric nor symmetric.

Example 17.3.8. A relation can be both antisymmetric and symmetric.

The identity relation on any set, where each element is related to itself and only to itself, is both antisymmetric and symmetric.

Remark 17.3.9.

As Example 17.3.7 and Example 17.3.8 demonstrate, antisymmetry is not the opposite of symmetry. However, for a relation \(R\) on set \(A\text{,}\) we may think of symmetry and antisymmetry as being at opposite ends of a spectrum, measuring how often we have both \(a_1 \mathrel{R} a_2\) and \(a_2 \mathrel{R} a_1\) for \(a_1 \ne a_2\text{.}\)
By definition, antisymmetry is when we never have both. On the other hand, symmetry is when we always have both or neither; that is, for every distinct pair \(a_1,a_2 \in A\text{,}\) we either have both \(a_1 \mathrel{R} a_2\) and \(a_2 \mathrel{R} a_1\text{,}\) or we have both \(a_1\ \not R\ a_2\) and \(a_2\ \not R\ a_1\text{.}\) However, a relation can fall between symmetry and antisymmetry on the spectrum, such as in Example 17.3.7, where we sometimes have both (e.g. both \(a \mathrel{R} b\) and \(b \mathrel{R} a\) for that example relation) and we also sometimes have only one (e.g. \(a \mathrel{R} c\) but \(c\ \not R\ a\) for that example relation).
The equality relation on a set is a special case that is both symmetric and antisymmetric. In fact, equality is essentially the only relation that is both symmetric and antisymmetric — see Exercise 17.6.22.
In symbolic language, the definition of antisymmetric relation is
\begin{equation*} (\forall a_1 \in A)(\forall a_2 \in A)({a_1 \neq a_2} \lgcimplies {{a_1\ \not R\ a_2} \lgcor {a_2\ \not R\ a_1}}) \text{.} \end{equation*}
However, in practise we usually prove antisymmetry using one of two logically equivalent formulations.

Remark 17.3.11.

The first formulation for proving antisymmetry provided above can be thought of as just a different way to say that it is not possible to have both \(a_1 \mathrel{R} a_2\) and \(a_2 \mathrel{R} a_1\) for distinct elements \(a_1,a_2\text{.}\) The second formulation essentially says that the only possible way to have both \(a_1 \mathrel{R} a_2\) and \(a_2 \mathrel{R} a_1\) is if \(a_2 = a_1\text{.}\)

Note 17.3.12.

In Exercise 17.6.21 you are asked to prove that each of the two different ways of verifying that a relation is antisymmetric provided in the test above are equivalent.

Subsection 17.3.3 Transitivity

transitive
for every triple of elements \(a_1,a_2,a_3 \in A\) for which both \(a_1 \mathrel{R} a_2\) and \(a_2 \mathrel{R} a_3\) are true, \(a_1 \mathrel{R} a_3\) must also be true

Example 17.3.13. Ancestry is transitive.

The relation on the set of all humans who ever lived defined by “\(a\) is the ancestor of \(b\)” is transitive.