Section 9.1 Relations
Definition 9.1.1.
Let \(A\) be a set. Then a relation, \(R\text{,}\) on \(A\) is a subset \(R \subseteq A \times A\text{.}\) If the ordered pair \((x,y)\in R\text{,}\) we denote this as \(x \rel y\text{,}\) while if \((x,y)\notin R\) we write \(x \nrel y\text{.}\)
So while we introduced relations in this chapter by starting with relations you already knew — like “is a divisor of” and “is an element of” — the above defines relations as subsets. This allows us much more flexibility and we can use set-builder notation to define specific relations. For example
\begin{align*}
R &= \set{ (x,x) \in \mathbb{R}\times \mathbb{R} \so x\in \mathbb{R}}
\end{align*}
is the relation “=” on the set of real numbers. While
\begin{align*}
S &= \set{ (x,y) \in \mathbb{Z}\times\mathbb{Z} \so x-y \in \mathbb{N}}
\end{align*}
is the relation “\(\gt \)” on the set of integers.
The definition of relation allows us to take any subset of \(A \times A\) to be a relation. For example,
\(R = \es \) gives the relation in which \(x \nrel y\) for all \(x,y \in A\text{.}\)
\(R = A\times A \) gives the relation in which \(x \rel y\) for all \(x,y \in A\text{.}\)
The first of these is sometimes called the empty relation, while the latter is called the universal relation. Unsurprisingly, the vast majority of other subsets \(R \subset A \times A\text{,}\) won’t be particularly interesting or useful or have especially natural or nice definitions. We will, shortly, start to impose additional requirements or properties onto the relations in order to make them more useful and interesting.
For a great many purposes, we define relationships between objects coming from the same set. However, there are situations in which we want to describe relationships between objects from different sets. For example the relation “is an element of”, one object will be an element, while the other will be a set. Or, as another example, we could have a set of children and a set of parents, with the relation “is a child of”. Consequently, the above definition is often generalised as follows:
Definition 9.1.2. Definition Definition 9.1.1 generalised.
Let \(A,B\) be sets. Then a relation, \(R\text{,}\) between \(A\) and \(B\) is a subset \(R \subseteq A \times B\text{.}\) If the ordered pair \((x,y)\in R\text{,}\) we denote this as \(x \rel y\text{,}\) while if \((x,y)\notin R\) we write \(x \nrel y\text{.}\)
Though the above generalisation will be important when we start to consider functions, most of what we will do in this chapter concerns relations that compare elements from a single set, rather than between two sets.
