Chapter 9 Relations
A great number of equations that we see in mathematics tell us about the relationship between two objects. For example
- \(a \lt b\) — the number \(a\) is strictly less than the number \(b\text{.}\)
- \(a|b\) — the number \(a\) is a divisor of the number \(b\text{.}\)
- \(a=b\) — the quantities \(a\) and \(b\) are equal.
- \(a \in B\) — the object \(a\) is a member of the set \(B\text{.}\)
- \(a \equiv b \mod n\) — \(a\) and \(b\) have the same remainder when divided by \(n\text{.}\)
We haven’t seen this last one yet, but we will soon — it is a way of generalising the notions of odd and even numbers.
These symbols
\begin{equation*}
\lt \qquad | \qquad = \qquad \in \qquad \equiv
\end{equation*}
all encode relationships between objects. Of course, all the relationships we’ve stated above are quite different however, there is something to be gained from developing a general theory of how relations behave and underline what they have in common.
Consider the symbol that we use to denote divisibility. We say that
\begin{align*}
a | b & \iff b=ak \text{ where } k\in \mathbb{Z}
\end{align*}
You can think of “\(|\)” as some sort of operator that takes two objects and declares some relationship between them. Here, both of those objects come from the same set — namely the integers.
Similarly, the symbol we use to denote set membership
\begin{gather*}
a \in B
\end{gather*}
tells us that the object \(a\) lies inside the object \(B\text{.}\) Again, this symbol “\(\in\)” can be an operator that takes two objects and declares a relationship between them. In this case, in contrast with the previous case, the objects need not come from the same set — \(a\) could be an integer and \(B\) a subset of integers.
In each case, the symbol is declaring a relationship between two objects.
One more. Consider the set \(A= \set{1,2,4,8} \text{,}\) and all the comparisons we can make between those numbers using “is divisible by”. Now since there are 4 numbers, we can make \(4^2\) comparisons:
\begin{align*}
1\mid 1 && 1\mid 2 && 1\mid 4 && 1\mid 8\\
2\nmid 1 && 2\mid 2 && 2\mid 4 && 2 \mid 8\\
4\nmid 1 && 4\nmid 2 && 4\mid 4 && 4\mid 8\\
8\nmid 1 && 8\nmid 2 && 8\nmid 4 && 8 \mid 8
\end{align*}
Notice a couple of things here:
- The comparisons require an ordered pair of numbers,
- When the relation is true we use “\(|\)”, and when it is false, we just draw a line through it and write “\(\nmid\)”.
- The valid comparisons are just a set of ordered pairs — in particular it forms a subset of \(A\times A\text{.}\)
We could form a similar set of comparisons using the “is less than” relation:
\begin{align*}
1 \nless 1 && 1 \lt 2 && 1 \lt 4 && 1 \lt 8\\
2\nless 1 && 2 \nless 2 && 2 \lt 4 && 2 \lt 8\\
4\nless 1 && 4\nless 2 && 4\nless 4 && 4 \lt 8\\
8\nless 1 && 8\nless 2 && 8\nless 4 && 8 \nless 8
\end{align*}
or with the rather silly “starts with an earlier letter when written in German” comparison 107 . We don’t have a ready symbol for this comparison, so we’ll just use \(\rel\) and put a slash through it, \(\nrel\text{,}\) to show when the comparison does not hold.
\begin{align*}
1 \nrel 1 && 1 \rel 2 && 1 \rel 4 && 1 \nrel 8\\
2 \nrel 1 && 2 \nrel 2 && 2 \nrel 4 && 2 \nrel 8\\
4 \nrel 1 && 4 \rel 2 && 4 \nrel 4 && 4 \nrel 8\\
8 \rel 1 && 8 \rel 2 && 8 \rel 4 && 8 \nrel 8
\end{align*}
In each case the pairs of numbers that satisfy the relation form a subset of \(A \times A\text{.}\)
Since this set is small and finite we could also represent the relation pictorially. Consider the following figure
The dots here denote the elements of the set \(A = \set{1,2,3,4}\text{,}\) and an arrow from \(x\) to \(y\) denotes \(x \rel y\text{.}\) This can be a handy way to visualise things, but really only works when the underlying set is small.
Looking at the above pairs, it should be clear that we can specifiy or define the relation using the subset:
\begin{gather*}
R = \set{ (1,2), (1,4), (4,2), (8,1), (8,2), (8,4) }.
\end{gather*}
More generally we can define any relation in this way. This leads us to the formal definition of relation in the next section.
For the non-germanophone or those without ready access to dictionary or online translation service: 1 = ein, 2=zwei, 4=vier, 8=acht.
