Section 17.1 Basics
- relation (working definition)
a rule which assigns to some elements of a set \(A\) several elements from a set \(B\)
- \(a \mathrel{R} b\)
element \(a \in A\) is related to element \(b \in B\) by relation \(R\)
- relation on a set
a relation between elements of the same set
As the name implies, a relation describes some relationship of elements of a set \(A\) to elements of a set \(B\text{.}\)
Example 17.1.2. Pet relation.
Let \(C\) represent the set of living cats, and let \(H\) represent the set of living humans. Then one relationship between elements of these two sets can be expressed by writing \(c \mathrel{R} h\) to mean that cat \(c\) is the pet of human \(h\text{.}\)
Example 17.1.3. Parent relation.
Let \(H\) represent the set of living humans. Then one type of relationship between elements of this set can be expressed by writing \(h_1 \mathrel{R} h_2\) to mean that human \(h_1\) is the parent of human \(h_2\text{.}\)
Example 17.1.4. Division relation.
One type of relationship between elements of \(\posset{\N}\) can be expressed by writing \(m \mid n\) to mean that nonzero natural number \(m\) divides nonzero natural number \(n\text{.}\)
Just as with functions, we want to avoid the use of the undefinable word “rule”. Notice that a relation just pairs elements of a set \(A\) with elements of a set \(B\text{;}\) we have seen this before.
- relation (formal definition)
a subset of a Cartesian product
With this formal definition, writing \(R \subseteq A \cartprod B\) becomes the same as saying “\(R\) is a relation between elements of \(A\) and \(B\text{,}\)” and writing \((a,b) \in R\) becomes the same as writing \(a \mathrel{R} b\text{.}\)
Example 17.1.7. Identity relation.
Consider
\begin{equation*}
R = \setdef{(a,a)}{a \in A} \subseteq A \cartprod A \text{.}
\end{equation*}
Then \(a_1 \mathrel{R} a_2\) means \(a_1 = a_2\text{.}\) This relation is the same as the identity function \(\funcdef{\id_A}{A}{A}\text{.}\)
Example 17.1.8. Element relation.
Consider
\begin{equation*}
R = \setdef{(a,C)}{a \in C} \subseteq A \cartprod \powset{A} \text{.}
\end{equation*}
Then \(a \mathrel{R} C\) means \(a \in C\text{.}\) This relation is in general not a function, since it is not well-defined: an element of \(A\) can be contained in several subsets of \(A\text{.}\)
A relation between pairs of objects, such as the ones we have considered so far, is sometimes called a binary relation. But we can consider relationships between collections of more than two objects.
- ternary relation
a subset of \(A \cartprod B \cartprod C\) for sets \(A,B,C\)
Example 17.1.9. A human (usually) has two biological parents.
Let \(H\) represent the set of all living humans. Then we can define a ternary relation \(R \subseteq H^3\) by taking \((h_1,h_2,h_3) \in R\) to mean that humans \(h_1,h_2\) are the parents of human \(h_3\text{.}\)