Here we list some important properties a relation \(R\) on a set \(A\) can have.
Subsection17.3.1Reflexivity
reflexive
\(a \mathrel{R} a\) is true for all \(a \in A\)
Example17.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.
Test17.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{.}\)
Subsection17.3.2Symmetry 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
Example17.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.
Test17.3.4.Symmetric relation.
To verify that relation \(R\) on set \(A\) is symmetric, prove that
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)
Remark17.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.
Example17.3.6.An antisymmetric relation on real numbers.
The relation \(\mathord{\le}\) on \(\R\) is antisymmetric.
Example17.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.
Example17.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.
Remark17.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
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{.}\)
Note17.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.
Subsection17.3.3Transitivity
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
Example17.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.
Test17.3.14.Transitive relation.
To verify that relation \(R\) on set \(A\) is transitive, prove that