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.
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 \)
Test 17.3.2. Reflexive relation.
To verify that relation \(R \) on set \(A \) is reflexive, prove that \((\forall a \in A)(a \mathrel{R} a) \text{.}\)
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.
Test 17.3.4. Symmetric relation.
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} \lgcimplies {a_2 \mathrel{R} a_1}) \text{.}
\end{equation*}
- antisymmetric
-
for every pair of distinct elements \(a_1,a_2 \in A \text{,}\) either \(a_1 \nmathrel{R} a_2 \) or \(a_2 \nmathrel{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 (so that \(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 \nmathrel{R} a_2 \) and \(a_2 \nmathrel{R} a_1 \text{.}\) However, a relation can fall between symmetry and antisymmetry on the spectrum, such as in Example 17.3.7. That is, for that relation \(R \) on \(A \) there are examples of distinct elements \(a_1,a_2 \in A \) where we have both \(a_1 \mathrel{R} a_2 \) and \(a_2 \mathrel{R} a_1 \text{,}\) and there are also examples of distinct elements \(a_1',a_2' \in A \) where we have \(a_1' \mathrel{R} a_2' \) but \(a_2' \nmathrel{R} a_1' \text{.}\)
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 \nmathrel{R} a_2} \lgcor {a_2 \nmathrel{R} a_1}}) \text{.}
\end{equation*}
However, in practise we usually prove antisymmetry using one of two logically equivalent formulations.
Test 17.3.10. Antiymmetric relation.
To verify that relation \(R \) on set \(A \) is antisymmetric, prove either one of the following logical statements.
-
\(\displaystyle (\forall a_1 \in A)(\forall a_2 \in A)({{a_1 \neq a_2} \lgcand {a_1 \mathrel{R} a_2}} \lgcimplies {a_2\ \not R\ a_1})\)
-
\(\displaystyle (\forall a_1 \in A)(\forall a_2 \in A)({{a_1 \mathrel{R} a_2} \lgcand {a_2 \mathrel{R} a_1}} \lgcimplies {a_2 = a_1})\)
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.
Test 17.3.14. Transitive relation.
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} \lgcand {a_2 \mathrel{R} a_3}} \lgcimplies {a_1 \mathrel{R} a_3}) \text{.}
\end{equation*}
