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.
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.
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. 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
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.
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.
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{.}\)
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{.}\)
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.
\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{.}\)
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
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.
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
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.
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.
