17.3: Properties of Relations
- Page ID
- 83491
Here we list some important properties a relation \(R\) on a set \(A\) can have.
Reflexivity
\(a \mathrel{R} a\) is true for all \(a \in A\)
The relation \(\mathord{\le}\) on \(\mathbb{R}\) is reflexive, but the relation \(\mathord{\lt}\) is not.
To verify that relation \(R\) on set \(A\) is reflexive, prove that \((\forall a \in A)(a \mathrel{R} a)\text{.}\)
Symmetry and antisymmetry
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.
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.
To verify that relation \(R\) on set \(A\) is symmetric, prove that
\begin{equation*} (\forall a_1 \in A)(\forall a_2 \in A)({a_1 \mathrel{R} a_2} \Rightarrow {a_2 \mathrel{R} a_1}) \text{.} \end{equation*}
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)
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.
The relation \(\mathord{\le}\) on \(\mathbb{R}\) is antisymmetric.
On \(A = \{a,b,c\}\text{,}\) the relation
\begin{equation*} R = \{(a,b),(b,a),(a,c)\} \subseteq A \times A \end{equation*}
is neither antisymmetric nor symmetric.
The identity relation on any set, where each element is related to itself and only to itself, is both antisymmetric and symmetric.
As Example \(\PageIndex{4}\) and Example \(\PageIndex{5}\) 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 \(\PageIndex{4}\), 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 \Rightarrow a_1\ \not R\ a_2 \lor a_2\ \not R\ a_1 ) \text{.} \end{equation*}
However, in practise we usually prove antisymmetry using one of two logically equivalent formulations.
To verify that relation \(R\) on set \(A\) is antisymmetric, prove either one of the following logical statements.
- \( (\forall a_1 \in A)(\forall a_2 \in A)(a_1 \neq a_2 \land a_1 \mathrel{R} a_2 \Rightarrow a_2\ \not R\ a_1)\)
- \( (\forall a_1 \in A)(\forall a_2 \in A)(a_1 \mathrel{R} a_2 \land a_2 \mathrel{R} a_1 \Rightarrow a_2 = a_1)\)
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{.}\)
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.
Transitivity
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.
The relation on the set of all humans who ever lived defined by “\(a\) is the ancestor of \(b\)” is transitive.
To verify that relation \(R\) on set \(A\) is transitive, prove that
\begin{equation*} (\forall a_1 \in A)(\forall a_2 \in A)(\forall a_3 \in A)(a_1 \mathrel{R} a_2 \land a_2 \mathrel{R} a_3 \Rightarrow a_1 \mathrel{R} a_3) \text{.} \end{equation*}