Remark 17.1.1.
Compare this working definition of relation with our working definition of function in Section 10.1.
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{.}\)
Note 17.1.5.
With this formal definition, a relation on a set \(A \) means a subset of \(A \cartprod A \text{.}\)
Remark 17.1.6.
Recall that our formal definition of function states that a function \(A \to B \) is a special kind of subset of \(A \cartprod B \text{.}\) But every subset of \(A \cartprod B \) can be considered as a relation, so a function is a special kind of relation.
The difference is that a function \(A \to B \) must assign exactly one element of \(B \) to each element of \(A \text{,}\) whereas a relation from \(A \) to \(B \) can assign any number of elements of \(B \) (even zero) to each element of \(A \text{.}\) That is, a relation does not have to be well-defined (see Example 10.1.17), and can be left undefined on some elements of \(A \) (see Example 10.1.16).
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{.}\)
