Section 9.2 Properties of relations
Since a relation on \(A\) is just a subset of \(A \times A\text{,}\) there are a huge number of possible relations on any given set. As noted above, the vast majority of these will unstructured and be neither useful nor interesting. Typically we require relations to have some additional structure.
Consider the relation “is divisible by” on the set of integers. This has some very useful properties:
For every \(n \in \mathbb{Z}\text{,}\) it is always true that \(n \mid n\text{,}\)
If \(a\mid b\) and \(b \mid c\) then we must have \(a \mid c\text{.}\)
The relation “is less than” on the set of reals, on the other hand, satisfies the second of these, but not the first. These properties (and others) are useful and interesting so let’s formalise them.
Definition 9.2.1.
Let \(R\) be a relation on a set \(A\text{.}\)
We say that the relation \(R\) is reflexive when \(a \rel a\) for every \(a \in A\text{.}\)
The relation \(R\) is symmetric when for any \(a,b \in A\text{,}\) \(a \rel b\) implies \(b \rel a\text{.}\)
The relation \(R\) is transitive when for any \(a,b,c \in A\text{,}\) \(a \rel b\) and \(b \rel c\) implies \(a \rel c\text{.}\)
Notice that in the definition of transitive we do not require that \(a,b,c\) are different.
Notice that we can write these using quantifiers quite nicely:
\begin{align*}
& \text{reflexive: }&& \forall a \in A, (a \rel a)\\
& \text{symmetric: }&& \forall a,b \in A, (a \rel b) \implies (b\rel a)\\
& \text{transitive: }&& \forall a,b,c \in A, (a \rel b) \land (b\rel c) \implies (a \rel c)
\end{align*}
We can visualise these using dot-arrow diagrams (as in
Figure 9.0.1). Note that these diagrams are not supposed to represent the entire relation, but rather just enough to illustrate the definitions.
-
Reflexive:
Every element \(x\) must have a loop from \(x\) back to itself.
-
Symmetric:
If there is an arc from \(x\) to \(y\) then there must also be an arc from \(y\) to \(x\text{.}\)
-
Transitive:
If there is an arc from \(x\) to \(y\) and another from \(y\) to \(z\) then there must also be an arc from \(x\) to \(z\text{.}\)
With a little work (and some proofs!) we can show that the following table holds for the relations \(\lt , \leq, =, \mid \) on the set of integers.
| R |
\(\lt \) |
\(\leq \) |
\(= \) |
\(\mid \) |
| Reflexive |
false |
true |
true |
true |
| Symmetric |
false |
false |
true |
false |
| Transitive |
true |
true |
true |
true |
Example 9.2.2.
Let \(R\) be the relation “has the same parity as” on the set of integers. This relation is defined by
\begin{align*}
R &= \set{(a,b) \in \mathbb{Z}\times \mathbb{Z} \so a,b \text{ both even or } a,b \text{ both odd}}\\
&= \set{(a,b) \in \mathbb{Z}\times \mathbb{Z} \so 2 \mid (a-b)}
\end{align*}
Notice that the second definition is equivalent to the first since
\begin{gather*}
(a,b \text{ have same parity}) \iff ( 2\mid(a-b)).
\end{gather*}
Prove that this relation is reflexive, symmetric and transitive.
Scratchwork.
We explore each in turn:
Reflexive. We need to show that for every single \(a \in \mathbb{Z}\) that \(a \rel a\text{.}\) Hence we need to show that for every integer \(a\text{,}\) that \(a\) has the same parity as \(a\text{.}\) This is pretty obvious, but to write it a little more mathematically — since \(a-a = 0\) and \(2|0\text{,}\) we know that \(a \rel a\text{.}\)
Symmetric. We need to show that if \(a \rel b\) then \(b \rel a\text{.}\) So we start by assuming that \(a \rel b\text{,}\) so \(2 \mid (a-b)\text{.}\) We need to show that \(2 \mid (b-a) \text{.}\) This, again, is quite obvious, but we can make it more mathematical by saying something like — since \(2 \mid (a-b)\) we know that \(a-b=2 k\text{,}\) so \(b-a = 2(-k)\text{,}\) and thus \(2 \mid (b-a) \)
Transitive. We need to show that if
\(a\rel b\) and
\(b \rel c\) then
\(a\rel c\text{.}\) So we assume that
\(a \rel b\) and
\(b\rel a\text{.}\) This means that
\(2\mid(a-b)\) and
\(2\mid (b-c)\text{.}\) So there are integers
\(k,\ell\) so that
\begin{align*}
a-b &= 2k & b-c &= 2\ell.
\end{align*}
Now we need to show something about
\(a-c\text{.}\) It is easy to isolate
\(a = 2k+b\) and
\(c=2\ell+b\text{,}\) so
\(a-c = 2k-2\ell \text{.}\) Hence
\(2\mid (a-c)\) as we need.
We are not done until we write it up nicely. So we do that now.
Proof.
Let the relation be as defined in the statement. We prove each property in turn.
Reflexive — Let \(a \in \mathbb{Z}\text{.}\) Since \(a-a = 0\) and \(2\mid 0\text{,}\) we know that \(a \rel a\text{.}\)
Symmetric — Let \(a,b\in \mathbb{Z}\) so that \(a \rel b\text{.}\) We know that \(2 \mid a-b\) and so we can write \(a-b = 2k\) for some \(k \in \mathbb{Z}\text{.}\) But then \(b-a=2(-k)\text{,}\) and so \(2\mid (b-a)\) and thus \(b \rel a\text{.}\)
Transitive — Let \(a,b,c\in \mathbb{Z}\) with \(a\rel b\) and \(b \rel c\text{.}\) Thus we know that \(a-b = 2k\) and \(b-c = 2\ell\) for some integer \(k,\ell \text{.}\) But then \(a-c = 2(k+\ell)\) and thus \(2\mid (a-c)\text{.}\) Hence \(a \rel c\) as required.
More examples:
Example 9.2.3.
Let \(A\) be the set of students at UBC, and consider the relation “attended highschool with”.
Reflexive — It is reflexive since every student went to highschool with themselves.
Symmetric — It is symmetric, because if student \(a\) went to highschool with \(b\text{,}\) then \(b\) went to the same highschool as \(a\text{.}\)
Transitive — It is not transitive, just because \(a\) went to school with \(b\) and \(b\) went to school with \(c\text{,}\) it does not mean that \(a\) went to school with \(c\text{.}\) It is possible that \(b\) went to two different highschools, one they attended with \(a\) and the second they attended with \(c\text{.}\)
Another student flavoured example.
Example 9.2.4.
Let \(A\) be the set of students in the student union building at 1pm, and let \(R\) be the relation “is within 2 metres of”.
Reflexive — It is reflexive since each student is less than 2m from themselves.
Symmetric — It is symmetric, because if student \(a\) is less than 2m from student \(b\text{,}\) then \(b\) is less than 2m from \(a\text{.}\)
Transitive — It is not transitive, just because \(a\) is 2m from \(b\) and \(b\) is 2m from \(c\text{,}\) it does not mean that \(a\) is 2m from \(c\text{.}\) If the students are arranged in a line with 1.5m between each of them, then \(a\) is 3m from \(c\text{.}\)
Example 9.2.5.
Let \(R\) be the relation “is a subset of” on the set of all subsets of the integers.
Reflexive — The relation is reflexive since for all sets \(X\text{,}\) we have \(X \subseteq X\text{.}\)
Symmetric — The relation is not symmetric. Let \(X = \es, Y = \set{1} \text{,}\) then \(X \subseteq Y\) but \(Y \not\subseteq X\text{.}\)
Transitive — The relation is transitive. Assume \(A \subseteq B\) and \(B \subseteq C\text{.}\) Now let \(a \in A\text{.}\) Since \(A \subseteq B\) we know \(a \in B\text{.}\) And since \(B \subseteq C\text{,}\) we know \(a \in C\text{.}\) Hence \(A \subseteq C\) as required.
These aren’t the only interesting properties of relations. Here are some others we won’t really use, except maybe for some examples and exercises.
A relation is
total (also called
connex) when
\begin{gather*}
\forall a,b \in A, (a\rel b) \lor (b \rel a).
\end{gather*}
The relation
\(\leq \) on the set of reals is total.
A relation is
trichotomous when
\begin{gather*}
\forall a,b \in A, \text{ exactly one of }(a\rel b) \text{ or } (b \rel a) \text{ or } (a=b).
\end{gather*}
The relation
\(\lt \) is trichotomous.
A relation is
anti-symmetric when
\begin{gather*}
\forall a,b \in A, (a\rel b) \land (b \rel a) \implies a=b.
\end{gather*}
The relation
\(\subseteq\) is anti-symmetric, so is
\(\mid \) on natural numbers. However
\(\mid \) is not anti-symmetric on the set of all integers. If
\(b=-a\text{,}\) then
\(a\mid b\) and
\(b \mid a\text{,}\) but
\(a \neq b\text{.}\)
A relation is
dense when
\begin{equation*}
\forall a,b \in A, \exists c \in A \st (a \rel c) \land (c \rel b).
\end{equation*}
One very important relation on the integers is congruence - recall
Definition 5.3.1. It is not hard to prove that congruence has nice properties.
Theorem 9.2.6.
Let \(n \in \mathbb{N}\) then congruence modulo \(n\) is reflexive, symmetric and transitive.
Proof.
Let \(n\) be a fixed natural number. We prove each of the properties in turn.
Reflexive — Let \(a \in \mathbb{Z}\text{.}\) Then since \(a-a=0\) and \(n\mid 0\text{,}\) we know that \(a \equiv a \mod n\text{.}\)
Symmetric — Let \(a,b \in \mathbb{Z}\) and assume that \(a \equiv b \mod n\text{.}\) Hence we know that \(n \mid (a-b)\text{,}\) and so we can write \(a-b=n k\) for some integer \(k\text{.}\) Thus \(b-a = n(-k)\) and so \(n \mid (b-a)\) and \(b \equiv a \mod n\text{.}\)
Transitive — Let \(a,b,c \in \mathbb{Z}\) and assume that \(a \equiv b \mod n\) and \(b\equiv c \mod n\text{.}\) This implies that \(n \mid (a-b)\) and \(n \mid (b-c)\text{,}\) and so we can write \((a-b)=nk, (b-c=n\ell)\) for some integers \(k,l\text{.}\) Consequently \((a-c) = (a-b)+(b-c) = n(k+\ell)\) and \(n \mid (a-c)\text{.}\) Hence \(a \equiv c \mod n\text{.}\)
Notice that one immediate consequence of this theorem is that since congruence modulo \(n\) is symmetric, we can be a little bit more relaxed when discussing it. In particular, in the examples above we have been very careful to say
“\(19\) is congruent to \(5\) modulo 7”
“\(11\) is congruent to \(27\) modulo 4”
“\(13\) is congruent to \(7\) modulo 5”
where there is a definite first number and a definite second number in the relation. However since congruence is symmetric, we can instead say
“\(19\) and \(5\) are congruent modulo 7”
“\(11\) and \(27\) are congruent modulo 4”
“\(13\) and \(7\) are not congruent modulo 5”
where the order of the two numbers in the relation no longer matters. Of course we must still be careful with the modulus; we cannot mix that up with the other numbers.
We will return to congruences in more detail shortly.
Another example:
Example 9.2.7. Fractions.
Let \(F\) be the set of all fractions:
\begin{equation*}
F = \set{ \frac{a}{b} \so a,b \in \mathbb{Z}, b \neq 0}.
\end{equation*}
Consider the following fractions that are different elements of \(F\text{:}\)
\begin{equation*}
\frac{2}{4}\qquad \frac{3}{6} \qquad \frac{-7}{-14} \qquad \frac{9}{18}
\end{equation*}
All of these are just different ways of writing “one half” and so correspond to the same single element of \(\mathbb{Q}\text{.}\) We typically avoid this duplication by representing each rational number by a single reduced fraction. This is an example of an equivalence class, but we will get to those in the next section.
But before that, let us formalise how two fractions are related. We’ve been doing that since primary school — they are related when they are the same rational number. That is
\begin{equation*}
\frac{a}{b} \rel \frac{c}{d} \iff \frac{a}{b} = \frac{c}{d}
\end{equation*}
Notice the “\(=\)” in the equation on the right does not mean that the fractions are identical rather it means that they represent the same number. We can make this condition a little more comfortable by writing it as
\begin{equation*}
\frac{a}{b} \rel \frac{c}{d} \iff ad = bc
\end{equation*}
Let us show that this relation is reflexive, symmetric and transitive.
Proof.
We show that the relation on the set of fractions defined above is reflexive, symmetric and transitive.
Reflexive — Let \(\frac{a}{b} \in F\text{.}\) Then since \(ab=ab\text{,}\) it follows that \(\frac{a}{b} \rel \frac{a}{b}\text{.}\) Hence the relation is reflexive.
Symmetric — Let \(\frac{a}{b}, \frac{c}{d} \in F\text{.}\) Assume that \(\frac{a}{b}\rel \frac{c}{d}\text{.}\) Hence \(ad=bc\text{,}\) and so \(bc=ad\text{.}\) Thus \(\frac{c}{d}\rel \frac{a}{b}\text{.}\) So the relation is symmetric.
Transitive — Let \(\frac{a}{b}, \frac{c}{d}, \frac{e}{f} \in F\text{.}\) Assume that \(\frac{a}{b}\rel \frac{c}{d}\) and \(\frac{c}{d} \rel \frac{e}{f}\text{.}\) Hence we know that
\begin{equation*}
ad=bc \qquad \text{ and } \qquad cf=de.
\end{equation*}
Multiply the first of these equations by \(f\) and the second by \(b\text{.}\) This gives
\begin{equation*}
adf=bcf \qquad \text{ and } \qquad bcf = deb
\end{equation*}
Using the transitivity of equality we know that
\begin{equation*}
adf = deb
\end{equation*}
and since \(d \neq 0\) we have
\begin{equation*}
af = eb
\end{equation*}
Thus \(\frac{a}{b} \rel \frac{e}{f}\) and so the relation is transitive.
