17.1: Basics
- Page ID
- 83489
a rule which assigns to some elements of a set \(A\) several elements from a set \(B\)
element \(a \in A\) is related to element \(b \in B\) by relation \(R\)
a relation between elements of the same set
Compare this working definition of relation with our working definition of function in Section 10.1.
As the name implies, a relation describes some relationship of elements of a set \(A\) to elements of a set \(B\text{.}\)
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{.}\)
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{.}\)
One type of relationship between elements of \(\mathbb{N}_{<0}\) 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.
a subset of a Cartesian product
With this formal definition, writing \(R \subseteq A \times 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{.}\)
With this formal definition, a relation on a set \(A\) means a subset of \(A \times A\text{.}\)
Recall that our formal definition of function states that a function \(A \to B\) is a special kind of subset of \(A \times B\text{.}\) But every subset of \(A \times 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, and can be left undefined on some elements of \(A\text{.}\)
- See.
Consider
\begin{equation*} R = \{(a,C) : a \in C \} \subseteq A \times \mathscr{P}(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.
a subset of \(A \times B \times C\) for sets \(A,B,C\)
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{.}\)