7.1: Relations

PREVIEW ACTIVITY $\PageIndex{1}$: The United States of America

Recall from Section 5.4 that the Cartesian product of two sets $A$ and $B$, written $A \times B$, is the set of all ordered pairs $(a, b)$, where $a \in A$ and $b \in B$. That is, $A \times B = \{(a, b)\ |\ a \in A \text{ and } b \in B\}$.

Let $A$ be the set of all states in the United States and let

$R = \{(x, y) \in A \times A\ |\ x \text{ and } y \text{ have a land border in common}\}$.

For example, since California and Oregon have a land border, we can say that (California, Oregon) $\in R$ and (Oregon, California) $\in R$. Also, since California and Michigan do not share a land border, (California, Michigan) $\notin R$ and (Michigan, California) $\notin R$.

1. Use the roster method to specify the elements in each of the following sets:
   
   (a) $B = \{y \in A\ |\ (\text{Michigan}, y) \in R\}$
   (b) $C = \{x \in A\ |\ (x, \text{Michigan}) \in R\}$
   (c) $D = \{y \in A\ |\ (\text{Wisconsin}, y) \in R\}$
2. Find two different examples of two ordered pairs $(x, y)$ and $(y, z)$ such that $(x, y) \in R$, $(y, z) \in R$, but $(x, z) \notin R$, or explain why no such example exists. Based on this, is the following conditional statement true or false?
   
   For all $x, y, z \in A$, if $(x, y) \in R$ and $(y, z) \in R$, then $(x, z) \in R$.
3. Is the following conditional statement true or false? Explain.
   
   For all $x, y \in A$, if $(x, y) \in R$ then $(y, x) \in R$.

PREVIEW ACTIVITY $\PageIndex{2}$: The Solution Set of an Equation with Two Variables

In Section 2.3, we introduced the concept of the truth set of an open sentence with one variable. This was defined to be the set of all elements in the universal set that can be substituted for the variable to make the open sentence a true proposition. Assume that $x$ and $y$ represent real numbers. Then the equation

$4x^2 + y^2 = 16$

is an open sentence with two variables. An element of the truth set of this open sentence (also called a solution of the equation) is an ordered pair $(a, b)$ of real numbers so that when a is substituted for $x$ and $b$ is substituted for $y$, the predicate becomes a true statement (a true equation in this case). We can use set builder notation to describe the truth set $S$ of this equation with two variables as follows:

$S = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ 4x^2 + y^2 = 16\}.$

When a set is a truth set of an open sentence that is an equation, we also call the set the solution set of the equation.

1. List four different elements of the set $S$.
2. The graph of the equation $4x^2 + y^2 = 16$ in the xy-coordinate plane is an ellipse. Draw the graph and explain why this graph is a representation of the truth set (solutions set) of the equation $4x^2 + y^2 = 16$.
3. Describe each of the following sets as an interval of real numbers:
   
   (a) $A = \{x \in \mathbb{R}\ |\ \text{there exists a } y \in \mathbb{R} \text{ such that } 4x^2 + y^2 = 16\}.$
   (b) $B = \{y \in \mathbb{R}\ |\ \text{there exists an } x \in \mathbb{R} \text{ such that } 4x^2 + y^2 = 16\}.$

Introduction to Relations

In Section 6.1, we introduced the formal definition of a function from one set to another set. The notion of a function can be thought of as one way of relating the elements of one set with those of another set (or the same set). A function is a special type of relation in the sense that each element of the first set, the domain, is “related” to exactly one element of the second set, the codomain.

This idea of relating the elements of one set to those of another set using ordered pairs is not restricted to functions. For example, we may say that one integer, $a$, is related to another integer, $b$, provided that $a$ is congruent to $b$ modulo 3. Notice that this relation of congruence modulo 3 provides a way of relating one integer to another integer. However, in this case, an integer $a$ is related to more than one other integer. For example, since

$5 \equiv 5$ (mod 3), $5 \equiv 2$ (mod 3), and $5 \equiv -1$ (mod 3),

we can say that 5 is related to 3, 5 is related to 2, and 5 is related to -1. Notice that, as with functions, each relation of the form $a \equiv b$ (mod 3) involves two integersa and $b$ and hence involves an ordered pair $(a, b)$, which is an element of $\mathbb{Z} \times \mathbb{Z}$.

Definition: relations

Let $A$ and $B$ be sets. A relation $R$ from the set $A$ to the set $B$ is a subset of $A \times B$. That is, $R$ is a collection of ordered pairs where the first coordinate of each ordered pair is an element of $A$, and the second coordinate of each ordered pair is an element of $B$.

A relation from the set $A$ to the set $A$ is called a relation on the set $A$. So a relation on the set $A$ is a subset of $A \times A$.

In Section 6.1, we defined the domain and range of a function. We make similar definitions for a relation.

Definition: Domain and Range

If $R$ is a relation from the set $A$ to the set $B$, then the subset of $A$ consisting of all the first coordinates of the ordered pairs in $R$ is called the domain of $R$. The subset of $B$ consisting of all the second coordinates of the ordered pairs in $R$ is called the range of $R$.

We use the notation dom($R$) for the domain of $R$ and range($R$) for the range of $R$. So using set builder notation,

dom($R$) $= \{u \in A\ |\ (u, y) \in R \text{ for at least one } y \in B\}$

range($R$) $= \{v \in B\ |\ (x, v) \in R \text{ for at least one } x \in A\}$.

Example 7.1: Domain and Range

A relation was studied in each of the Preview Activities for this section. For Preview Activity 2, the set $S = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ 4x^2 + y^2 = 16\}$ is a subset of $\mathbb{R} \times \mathbb{R}$ and, hence, $S$ is a relation on $\mathbb{R}$. In Problem (3) of Preview Activity $\PageIndex{2}$, we actually determined the domain and range of this relation.

dom($S$) $= A = \{x \in \mathbb{R}\ |\ \text{there exists a } y \in \mathbb{R} \text{ such that } 4x^2 + y^2 = 16\}$

range($S$) $= B = \{y \in \mathbb{R}\ |\ \text{there exists an } x \in \mathbb{R} \text{ such that } 4x^2 + y^2 = 16\}$

So from the results in Preview Activity $\PageIndex{2}$, we can say that the domain of the relation $S$ is the closed interval [-2, 2] and the range of S is the closed interval [-4, 4].

Progress Check 7.2: Examples of Relations

1. Let $T = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ x^2 + y^2 = 64\}$.
   
   (a) Explain why $T$ is a relation on $\mathbb{R}$.
   (b) Find all values of $x$ such that $(x, 4) \in T$. Find all values of $x$ such that $(x, 9) \in T$.
   (c) What is the domain of the relation $T$? What is the range of $T$?
   (d) Since $T$ is a relation on $\mathbb{R}$, its elements can be graphed in the coordinate plane. Describe the graph of the relation $T$.
2. From Preview Activity $\PageIndex{1}$, $A$ is the set of all states in the United States, and
   $$R = \{(x, y) \in A \times A\ |\ x \text{ and } y \text{ have a border in common}\}.$$
   (a) Explain why $R$ is a relation on $A$.
   (b) What is the domain of the relation $R$? What is the range of the relation $R$?
   (c) Are the following statements true or false? Justify your conclusions.
   i. For all $x, y \in A$, if $(x, y) \in R$, then $(y, x) \in R$.
   ii. For all $x, y, z \in A$, if $(x, y) \in R$ and $(y, x) \in R$, then $(x, z) \in R$.

Answer

Add texts here. Do not delete this text first.

Some Standard Mathematical Relations

There are many different relations in mathematics. For example, two real numbers can be considered to be related if one number is less than the other number. We call this the "less than" relation on $\mathbb{R}$. If $x, y \in \mathbb{R}$ and $x$ is less than $y$, we often write $x < y$. As a set of ordered pairs, this relation is $R_{<}$, where

\{R_{<} = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ x < y\}\).

With many mathematical relations, we do not write the relation as a set of ordered pairs even though, technically, it is a set of ordered pairs. Table 7.1 describes some standard mathematical relations.

Notation for Relations

The mathematical relations in Table 7.1 all used a relation symbol between the two elements that form the ordered pair in $A \times B$. For this reason, we often do the same thing for a general relation from the set $A$ to the set $B$. So if $R$ is a relation from $A$ to $B$, and $x \in A$ and $y \in B$, we use the notation

In some cases, we will even use a generic relation symbol for defining a new relation or speaking about relations in a general context. Perhaps the most commonly use symbol is "~", read “tilde” or “squiggle” or “is related to.” When we do this, we will write

$$\begin{array} {rcl} {x\ ~\ y} & \text{means the same thing as} & {(x, y) \in R;\text{ and}} \\ {x \nsim y} & \text{means the same thing as} & {(x, y) \notin R.} \end{array}$$

Progress Check 7.3: The Divides Relation

Whenever we have spoken about one integer dividing another integer, we have worked with the “divides” relation on $\mathbb{Z}$. In particular, we can write

$D = \{(m, n) \in \mathbb{Z} \times \mathbb{Z}\ |\ m \text{ divides } n\}.$

In this case, we have a specific notation for “divides,” and we write

$m\ |\ n$ if and only if $(m, n) \in D$.

1. What is the domain of the “divides” relation? What is the range of the “divides” relation?
2. Are the following statements true or false? Explain.

   (a) For every nonzero integer $a$, $a\ |\ a$.
   (b) For all nonzero integers $a$ and $b$, if $a\ |\ b$, then $b\ |\ a$.
   (c) For all nonzero integers $a$, $b$, and $c$,if $a\ |\ b$ and $b\ |\ c$, then $a\ |\ c$.

Answer

Add texts here. Do not delete this text first.

Functions as Relations

If we have a function $f: A \to B$, we can generate a set of ordered pairs $f$ that is a subset of $A \times B$ as follows:

$f = \{(a, f(a))\ |\ a \in A\}$ or $f = \{(a, b) \in A \times B\ |\ b = f(a)\}.$

This means that $f$ is a relation from $A$ to $B$. Since, dom($f$) $= A$, we know that

(1) For every $a \in A$, there exists $a, b \in B$ such that $(a, b) \in f$.

When $(a, b) \in f$., we write $b = f(a)$. In addition, to be a function, each input can produce only one output. In terms of ordered pairs, this means that there will never be two ordered pairs $(a, b)$ and $a, c)$ in the function $f$, where $a \in A$, $b, c \in B$, and $b = c$. We can formulate this as a conditional statement as follows:

(2) For every $a \in A$ and every $b, c \in B$, if $(a, b) \in f$ and $(a, c) \in f$, then $b = c$.

This means that a function $f$ from $A$ to $B$ is a relation from A to B that satisfies conditions (1) and (2). (See Theorem 6.22 in Section 6.5.) Not every relation, however, will be a function. For example, consider the relation $T$ in Progress Check 7.2.

Progress Check 7.4: A Set of Ordered Pairs

Let $F = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ y = x^2\}$. The set $F$ can then be considered to be relation on $\mathbb{R}$ since it is a subset of $\mathbb{R} \times \mathbb{R}$.

1. List five different ordered pairs that are in the set $F$.
2. Use the roster method to specify the elements of each of the following the sets:
   
   (a) $A = \{x \in \mathbb{R}\ |\ (x, 4) \in F\}$
   (b) $B = \{x \in \mathbb{R}\ |\ (x, 10) \in F\}$
   (c) $C = \{y \in \mathbb{R}\ |\ (5, y) \in F\}$
   (d) $D = \{y \in \mathbb{R}\ |\ (-3, y) \in F\}$
3. Since each real number $x$ produces only one value of $y$ for which $y = x^2$, the set $F$ can be used to define a function from the set $\mathbb{R}$ to $\mathbb{R}$. Draw a graph of this function.

Answer

Add texts here. Do not delete this text first.

Visual Representations of Relations

In Progress Check 7.4, we were able to draw a graph of a relation as a way to visualize the relation. In this case, the relation was a function from $\mathbb{R}$ to $\mathbb{R}$. In addition, in Progress Check 7.2, we were also able to use a graph to represent a relation. In this case, the graph of the relation $T = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ x^2 + y^2 = 64\}$ is a circle of radius 8 whose center is at the origin.

When $R$ is a relation from a subset of the real numbers $\mathbb{R}$ to a subset of $\mathbb{R}$, we can often use a graph to provide a visual representation of the relation. This is especially true if the relation is defined by an equation or even an inequality. For example, if

$R = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ y \ge x^2\}$,

then we can use the following graph as a way to visualize the points in the plane that are also in this relation.

The points $(x, y)$ in the relation $R$ are the points on the graph of $y = x^2$ or are in the shaded region. This because for these points, $y \ge x^2$. One of the shortcomings of this type of graph is that the graph of the equation and the shaded region are actually unbounded and so we can never show the entire graph of this relation. However, it does allow us to see that the points in this relation are either on the parabola defined by the equation $y = x^2$ or are “inside” the parabola.

When the domain or range of a relation is infinite, we cannot provide a visualization of the entire relation. However, if $A$ is a (small) finite set, a relation $R$ on $A$ can be specified by simply listing all the ordered pairs in $R$. For example, if $A = \{1, 2, 3, 4\}$, then

$R = \{(1, 1), (4, 4), (1, 3), (3, 2), (1, 2), (2, 1)\}$

is a relation on $A$. A convenient way to represent such a relation is to draw a point in the plane for each of the elements of $A$ and then for each $(x, y) \in R$ (or $x\ R\ y$), we draw an arrow starting at the point $x$ and pointing to the point $y$. If $(x, x) \in R$ (or $x\ R\ x$), we draw a loop at the point $x$. The resulting diagram is called a directed graph or a digraph. The diagram in Figure 7.2 is a digraph for the relation $R$.

In a directed graph, the points are called the vertices. So each element of $A$ corresponds to a vertex. The arrows, including the loops, are called the directed edges of the directed graph. We will make use of these directed graphs in the next section when we study equivalence relations.

Progress Check 7.5: The Directed Graph of a Relation

Let $A = \{1, 2, 3, 4, 5, 6\}$. Draw a directed graph for the following two relations on the set $A$. For each relation, it may be helpful to arrange the vertices of $A$ as shown in Figure 7.3.

$R = \{(x, y) \in A \times A\ |\ x \text{ divides } y\}$, $T = \{(x, y) \in A \times A\ |\ x + y \text{ is even}\}$.

Answer

Add texts here. Do not delete this text first.

Exercise 7.1

1. Let $A = \{a, b, c\}$, $B = \{p, q, r\}$, and let $R$ be the set of ordered pairs defined by $R = \{(a, p), (b, q), (c, p), (a, q)\}$.
   
   (a) Use the roster method to list all the elements of $A \times B$. Explain why $A \times B$ can be considered to be a relation from $A$ to $B$.
   (b) Explain why $R$ is a relation from $A$ to $B$.
   (c) What is the domain of $R$? What is the range of $R$?
2. Let $A = \{a, b, c\}$ and let $R = \{(a, a), (a, c), (b, b), (b, c), (c, a), (c, b)\}$ (so $R$ is a relation on $A$). Are the following statements true or false? Explain.
   
   (a) For each $x \in A$, $x\ R\ x$.
   (b) For every $x, y \in A$, if $x\ R\ y$, then $y\ R\ x$.
   (c) For every $x, y, z \in A$, if $x\ R\ y$ and $y\ R\ z$, then $x\ R\ z$.
   (d) $R$ is a function from $A$ to $A$.
3. Let $A$ be the set of all females citizens of the United States. Let $D$ be the relation on $A$ defined by
   $$D = \{(x, y) \in A \times A\ |\ x \text{ is a daughter of } y\}.$$
   That is, $x\ D\ y$ means that $x$ is a daughter of $y$.
   
   (a) Describe those elements of $A$ that are in the domain of $D$.
   (b) Describe those elements of $A$ that are in the range of $D$.
   (c) Is the relation $D$ a function from $A$ to $A$? Explain.
4. Let $U$ be a nonempty set, and let $R$ be the “subset relation” on $\mathcal{P}(U)$. That is,
   $$R = \{(S, T) \in \mathcal{P}(U) \times \mathcal{P}(U)\ |\ S \subseteq T\}.$$
   
   (a) Write the open sentence $(S, T) \in R$ using standard subset notation.
   (b) What is the domain of this subset relation, $R$?
   (c) What is the range of this subset relation, $R$?
   (d) Is $R$ a function from $\mathcal{P}(U)$ to $\mathcal{P}(U)$? Explain.
5. Let $U$ be a nonempty set, and let $R$ be the "element of" relation from $U$ to $\mathcal{P}(U)$. That is,
   $$R = \{(x, S) \in U \times \mathcal{P}(U)\ |\ x \in S\}.$$
   (a) What is the domain of this “element of” relation, $R$?
   (b) What is the range of this "element of" relation, $R$?
   (c) Is $R$ a function from $U$ to $\mathcal{P}(U)$? Explain.
6. Let $S = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ x^2 + y^2 = 100\}$.
   
   (a) Determine the set of all values of $x$ such that $(x, 6) \in S$, and determine the set of all values of $x$ such that $(x, 9) \in S$.
   (b) Determine the domain and range of the relation $S$ and write each set using set builder notation.
   (c) Is the relation $S$ a function from $\mathbb{R}$ to $\mathbb{R}$? Explain.
   (d) Since $S$ is a relation on $\mathbb{R}$, its elements can be graphed in the coordinate plane. Describe the graph of the relation $S$. Is the graph consistent with your answers in Exercises (6a) through (6c)? Explain.
7. Repeat Exercise( 6) using the relation on $\mathbb{R}$ defined by
   $$S = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ y = \sqrt{100 - x^2}\}.$$
   What is the connection between this relation and the relation in Exercise (6)?
8. Determine the domain and range of each of the following relations on $\mathbb{R}$ and sketch the graph of each relation.
   
   (a) $R = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ x^2 + y^2 = 10\}$
   (b) $S = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ y^2 = x + 10\}$
   (c) $T = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ |x| + |y| = 10\}$
   (d) $R = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ x^2 = y^2\}$
9. Let $R$ be the relation on $\mathbb{Z}$ where for all $a, b \in \mathbb{Z}$, $a\ R\ b$ if and only if $|a - b| \le 2$.
   
   (a) Use set builder notation to describe the relation $R$ as a set of ordered pairs.
   (b) Determine the domain and range of the relation $R$.
   (c) Use the roster method to specify these to fall integers $x$ such that $x\ R\ 5$ and the set of all integers $x$ such that $5\ R\ x$.
   (d) If possible, find integers $x$ and $y$ such that $x\ R\ 8$, $8\ R\ y$, but .
   (e) If $a \in \mathbb{Z}$, use the roster method to specify the set of all $x \in \mathbb{Z}$ such that $x\ R\ a$.
10. Let $R_{<} = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ x < y\}$. This means that $R_{<}$ is the "less than" relation on $\mathbb{R}$.
    
    (a) What is the domain of the relation $R_{<}$?
    (b) What is the range of the relation $R_{<}$?
    (c) Is the relation $R_{<}$ a function from $\mathbb{R}$ to $\mathbb{R}$? Explain.
    
    Note: Remember that a relation is a set. Consequently, we can talk about one relation being a subset of another relation. Another thing to remember is that the elements of a relation are ordered pairs.
    
    Explorations and Activities
11. The Inverse of a Relation. In Section 6.5, we introduced the inverse of a function. If $A$ and $B$ are nonempty sets and if $f: A \to B$ is a function, then the inverse of $f$, denoted by $f^{-1}$, is defined as
    $$\begin{array} {rcl} {f^{-1}} &= & {\{(b, a) \in B \times A\ |\ f(a) = b\}} \\ {} &= & {\{(b, a) \in B \times A\ |\ (a, b) \in f\}.} \end{array}$$
    Now that we know about relations, we see that $f^{-1}$ is always a relation from $B$ to $A$. The concept of the inverse of a function is actually a special case of the more general concept of the inverse of a relation, which we now define.

    Definition

    Let $R$ be a relation from the set $A$ to the set $B$. The inverse of $R$, written $R^{-1}$ and read "$R$ inverse," is the relation from $B$ to $A$ defined by
    $$\begin{array} {rcl} {R^{-1}} &= & {\{(y, x) \in B \times A\ |\ (x, y) \in R\},\text{ or}} \\ {R^{-1}} &= & {\{(y, x) \in B \times A\ |\ x\ R\ y\}.} \end{array}$$

    That is, $R^{-1}$ is the subset of $B \times A$ consisting of all ordered pairs $(y, x)$ such that $x\ R\ y$.

    For example, let $D$ be the “divides” relation on $\mathbb{Z}$. See Progress Check 7.3. So
    $$D = \{(m, n) \in \mathbb{Z} \times \mathbb{Z}\ |\ m \text{ divides } n\}.$$
    

    This means that we can write $m\ |\ n$ if and only if $(m, n) \in D$. So, in this case,
    $$\begin{array} {rcl} {D^{-1}} &= & {\{(n, m) \in \mathbb{Z} \times \mathbb{Z}\ |\ (m, n) \in D\}} \\ {} &= & {\{(n, m) \in \mathbb{Z} \times \mathbb{Z}\ |\ m \text{ divides } n\}.} \end{array}$$
    Now, if we would like to focus on the first coordinate instead of the second coordinate in $D^{-1}$, we know that “$m$ divides $n$” means the same thing as “$n$ is a multiple of $m$.” Hence,
    $$D^{-1} = \{(n, m) \in \mathbb{Z} \times \mathbb{Z}\ |\ n \text{ is a multiple of } m\}.$$
    We can say that the inverse of the “divides” relation on $\mathbb{Z}$ is the “is a multiple of” relation on $\mathbb{Z}$.
    Theorem 7.6, which follows, contains some elementary facts about inverse.

    Theorem 7.6.

    Let $R$ be a relation from the set $A$ to the set $B$. Then

    • The domain of $R^{-1}$ is the range of $R$. That is, dom($R^{-1}$) = range($R$).
    • The range of $R^{-1}$ is the domain of $R$. That is, range($R^{-1}$) = dom($R$).
    • The inverse of $R^{-1}$ is R. That is, $(R^{-1})^{-1} = R$.

    To prove the first part of Theorem 7.6, observe that the goal is to prove that two sets are equal,

    dom($R^{-1}$) = range($R$)

    One way to do this is to prove that each is a subset of the other. To prove that dom($R^{-1}$) $\subseteq$ range($R$), we can start by choosing an arbitrary element of dom($R^{-1}$). So let $y \in$ dom($R^{-1}$). The goal now is to prove that $y \in$ range($R$). What does it mean to say that $y \in$ dom($R^{-1}$)? It means that there exists an $x \in A$ such that

    $(y, x) \in R^{-1}$.

    Now what does it mean to say that $(y, x) \in R^{-1}$? It means that $(x, y) \in R$. What does this tell us about $y$?

    Complete the proof of the first part of Theorem 7.6. Then, complete the proofs of the other two parts of Theorem 7.6.

    Proof

    Add proof here and it will automatically be hidden

Answer

Add texts here. Do not delete this text first.