Skip to main content

Section 4.1 Relations

For convenience, we restate the definition of the Cartesian product of sets with which you might already be familiar.

Definition 4.1.1.

The Cartesian product of two sets \(A\) and \(B\text{,}\) denoted \(A \times B\text{,}\) is the set consisting of all ordered pairs in which the first element comes from set \(A\) and the second element comes from set \(B\text{;}\) that is, \(A \times B = \{ (a,b) \mid a \in A \ \text{and} \ b \in B\}\text{.}\)

Definition 4.1.2.

A relation \(R\) from a set \(A\) to a set \(B\) is a subset of \(A \times B\text{.}\) If \(R\) is a relation from \(A\) to \(A\text{,}\) we say \(R\) is a relation on \(A\text{.}\)

While a relation may be described in a variety of ways, it is really just a set of ordered pairs.

Let \(A = \{a,b,c,d\}\) and \(B = \{1,2,3\}\text{.}\) Consider the following sets.

  1. \(\displaystyle R_1 =\{ (a,2), (b,3), (c,2), (d,3)\}\)
  2. \(\displaystyle R_2 = \{ (a,1), (a, 2), (b,3) \}\)
  3. \(\displaystyle R_3 = \{(a, 1), (b, 3), (c, 2) \}\)
  4. \(\displaystyle R_4 = \{ (a,a), (b,b), (c,c), (d,d) \}\)
  5. \(\displaystyle R_5 = \{ (d, a), (c, a), (d,d) \}\)

Each of the sets \(R_1\text{,}\) \(R_2\text{,}\) and \(R_3\) is a relation from \(A\) to \(B\) because the first elements in the ordered pairs are from \(A\) and the second elements are from \(B\text{,}\) while \(R_4\) and \(R_5\) are relations on \(A\) because both first and second elements are from \(A\text{.}\)

Although relations are actually sets of ordered pairs, such collections of ordered pairs may be indicated in many ways. Notice that a relation is essentially a pairing of elements according to some criteria. For example, we may “pair” a person's name with his or her social security number, age, height, or the names of cities lived in. Sometimes relations are specified simply by listing these pairs in set form as in the example above. When relations are described in this form, the rules or criteria for the pairing are often not known. For instance, in \(R_1\) of Example 4.1.3, we know that \(b\) and \(d\) are both related to \(3\text{,}\) but we do not know why. Similarly, relations may be indicated in table or graphical form as in the below.

pictorial representation R from A to B
Figure 4.1.4. Pictorial representation \(R\) from \(A\) to \(B\)

Figure 4.1.4 is a pictorial representation of of the relation \(R = \{(1, 4), (6, 4), (3, 3), (10, 2)\}\) from \(A = \{1, 3, 6, 10\}\) to \(B = \{2, 3, 4\}\text{.}\) The arrow diagram below is a different way of representing the same relation.

arrow representation R from A to B

A third representation of \(R\) is given in table form below.

\(a\) \(b\)
1 4
3 3
6 4
10 2
Table 4.1.6. A table representation \(R\) from \(A\) to \(B\)

In many cases, listing all the ordered pairs in a relation is tedious or simply impossible. Under those circumstances the relation may be described in many different ways; associated ordered pairs are indicated by specifying a defining rule.

The equation \(x + y = 4\) describes a relation, \(R\text{,}\) consisting of an infinite set of ordered pairs whose components will satisfy the equation. Hence, the ordered pairs \((2, 2)\text{,}\) \(( 3/2, 5/2 )\text{,}\) \((-7, 11)\text{,}\) and \((0, 4)\) are a few of the elements in the relation. Precisely stated,

\begin{equation*} R(x,y) = \{ (x, y) \in \mathbb R \times \mathbb R \mid x + y = 4 \} \end{equation*}

That is, the relation described by the equation is actually the infinite set of ordered pairs of real numbers whose sum is equal to \(4\text{.}\) In the following figure, we have indicated all the ordered pairs which satisfy the linear equation; this is sometimes called the graphical representation of the equation.

pictorial representation R from A to B
Figure 4.1.8. Graphical representation of \(x + y = 4\)

Let \(A = \{ 1, 2, 3, 4\}\) and define a relation \(R\) on \(A\) by

\begin{equation*} R(x,y) = \{ (x, y) \in A \times A \mid x \leq y \}. \end{equation*}

That is, \(R\) is the set of all ordered pairs whose components both come from the set \(A\) and in which the first component is less than or equal to the second. In this case we could enumerate \(R\) as follows:

\begin{equation*} R = \{ (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4) \} \end{equation*}

Notice in Example 4.1.9 that it is merely inconvenient to have to list all the ordered pairs implied by the rule given. However, if the set A were the set of all integers instead of the finite set \(\{1, 2, 3, 4\}\text{,}\) the same rule applied to A would yield an infinite set of ordered pairs that would be impossible to list. In such cases, it is convenient to use notation that refers to the relation by the criteria used for comparison. We say the relation \(R\) is “less than or equal to” or “\(\leq\)” rather than the actual set of ordered pairs, and instead of saying \((1, 3) \in R\text{,}\) we say \(1 \leq 3\text{.}\)

Remark 4.1.10.

In general, we often substitute the notation \(aRb\) for \((a, b) \in R\text{.}\)

Then to determine whether two elements in the set are related, we simply substitute our familiar relation for \(R\) in the expression \(aRb\text{.}\) For example, instead of asking if the ordered pair \((3, 2)\) is an element of the relation “is greater than,” we ask if \(3\) “is greater than” \(2\text{;}\) that is, we usually write \(3 > 2\) instead of writing \((3,2) \in\) “\(>\)”.

In considering each of the examples given in this section, it is clear that a relation between sets \(A\) and \(B\) need not “use up” all of both sets. This idea leads us to consider those subsets of \(A\) and \(B\) whose elements are paired by the relation, namely the domain and range.

Definition 4.1.11.

If \(R\) is a relation from \(A\) to \(B\text{,}\) then the domain of \(R\text{,}\) \(\domain(R)\) is defined by

\begin{equation*} \domain(R) = \{a \in A \mid (a, b) \in R \text{ for some } b \in B\}. \end{equation*}

The range, denoted by \(\range(R)\text{,}\) is defined by

\begin{equation*} \range(R) = \{b \in B \mid (a, b) \in R \text{ for some } a \in A\}. \end{equation*}

By Definition 4.1.11, it is clear that \(\domain(R)\) is a subset of \(A\) and \(\range(R)\) is a subset of \(B\text{.}\)

Informally, we designate the domain of a relation \(R\) as the set of all elements of the set \(A\) that are actually paired with (or mapped to) at least one element in \(B\text{.}\) The range of a relation R may be described as the set of all elements in the set \(B\) to which at least one element of \(A\) is mapped. These concepts are defined formally in the definition below.

Consider the sets \(R_1, R_2, \ldots, R_5\) as defined in Example 4.1.3. Then

  1. \(\domain(R_1) = A\) and \(\range(R_1) = \{ 2, 3 \}\text{.}\)
  2. \(\domain(R_2) = \{ a, b\}\) and \(\range(R_2) = B\text{.}\)
  3. \(\domain(R_3) = \{a, b, c\}\) and \(\range(R_3) = B\text{.}\)
  4. \(\domain(R_4) = A\) and \(\range(R_4) = A\text{.}\)
  5. \(\domain(R_5) = \{c, d \}\) and \(\range(R_5) = \{ a, d \}\text{.}\)

Consider the equation \(x^2 + y^2 = 1\) defined on \(\mathbb R\text{.}\) Let

\begin{equation*} R = \{ (x, y) \in \mathbb R \times \mathbb R \} \mid x^2 + y^2 = 1 \}. \end{equation*}

Then \(\domain(R) = \{ x \mid -1 \leq x \leq 1 \}\) and \(\range(R) = \{ y \mid -1 \leq y \leq 1 \}\) since substituting numbers whose squares are greater than \(1\) for either variable yields an equation with only complex solutions.

We will investigate the concepts of domain and range in more detail in the study of functions. However, the reader may suspect that although these sets are sometimes easily found, often they will require some insight and work to determine!

Earlier we considered the relation “\(\leq\text{.}\)” If we were to consider the associated pairs in reverse order, we might describe this new list of ordered pairs by the relation “\(\geq\text{.}\)” Thus we see that relations are in some sense reversible, and we formalize this concept in the definition that follows.

Definition 4.1.14.

If \(R\) is a relation from \(A\) to \(B\text{,}\) then the inverse relation of \(R\text{,}\) denoted by \(R^{-1}\text{,}\) is defined by

\begin{equation*} R^{-1} = \{(b, a) \mid (a, b) \in R \}. \end{equation*}

Thus, \(R^{-1}\) is a new relation from \(B\) to \(A\) and consists of ordered pairs from \(R\) with the components reversed. Hence, the inverse relation of \(R = \{ (2,3), (4, 7), (2, 9), (6,9) \}\) is the relation \(R^{-1} = \{ (3,2), (7,4), (9,2), (9, 6) \}\text{.}\)

Consider the relation in Figure 4.1.15. The inverse relation \(R^{-1}\) from \(B\) to \(A\) can be found by simply reversing the arrows (Figure 4.1.16). In this case, \(\domain(R) = \range(R^{-1}\) and \(\range(R) = \domain(R^{-1})\text{.}\)

two overlapping circles with the common part shaded
Figure 4.1.15. The relation \(R\) from \(A\) to \(B\)
two overlapping circles with the common part shaded
Figure 4.1.16. The relation \(R^{-1}\) from \(B\) to \(A\)