7 Equivalence Relations

7.1 Relations

7.1.1 Beginning Activity 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)\mid a\in A$ 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\mid 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:

   1. $B=\{y\in A\mid ($Michigan, $y)\in R\}$

   2. $C=\{x\in A\mid (x$, Michigan$)\in R\}$

   3. $D=\{y\in A\mid ($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.

$$\text{ For all }x,y\in A\text{, if }(x,y)\in R\text{, then }(y,x)\in R\text{. }$$

7.1.2 Beginning Activity 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 ℝ\times ℝ\mid 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 (solution set) of the equation $4x^2+y^2=16$.

3. Describe each of the following sets as an interval of real numbers:

   1. $A=\{x\in ℝ\mid$ there exists a $y\in ℝ$ such that $4x^2+y^2=16\}$.

   2. $B=\{y\in ℝ\mid$ there exists an $x\in ℝ$ such that $4x^2+y^2=16\}$.

7.1.3 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(mod3),5\equiv 2(mod3),\text{ and }5\equiv -1(mod3),$$

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

Definition. Let $A$ and $B$ be sets. A relation $𝑹$ from the set $𝑨$ to the set $𝑩$ 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 $𝑨$. 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. 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 $\mathrm{dom}(R)$ for the domain of $R$ and $\mathrm{range}(R)$ for the range of $R$. So using set builder notation,

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

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

7.1.4 Example 7.1 (Domain and Range)

A relation was studied in each of the beginning activities for this section. For

Beginning Activity 2, the set $S=\{(x,y)\in ℝ\times ℝ\mid 4x^2+y^2=16\}$ is a subset of $ℝ\times ℝ$ and, hence, $S$ is a relation on $ℝ$. In Problem (3) of Beginning Activity 2, we actually determined the domain and range of this relation.

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

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

So from the results in Beginning Activity 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]$.

7.1.5 Progress Check 7.2 (Examples of Relations)

1. Let $T=\{(x,y)\in ℝ\times ℝ\mid x^2+y^2=64\}$.

   1. Explain why $T$ is a relation on $ℝ$.

   2. Find all values of $x$ such that $(x,4)\in T$. Find all values of $x$ such that $(x,9)\in T$.

   3. What is the domain of the relation $T$? What is the range of $T$?

   4. Since $T$ is a relation on $ℝ$, its elements can be graphed in the coordinate plane. Describe the graph of the relation $T$.

2. From Beginning Activity 1, $A$ is the set of all states in the United States, and

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

1. Explain why $R$ is a relation on $A$.

2. What is the domain of the relation $R$? What is the range of the relation $R$?

3. Are the following statements true or false? Justify your conclusions.

   1. For all $x,y\in A$, if $(x,y)\in R$, then $(y,x)\in R$.

   2. For all $x,y,z\in A$, if $(x,y)\in R$ and $(y,z)\in R$, then $(x,z)\in R$.

7.1.6 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 $ℝ$. If $x,y\in ℝ$ and $x$ is less than $y$, we often write . As a set of ordered pairs, this relation is , where

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.

Name	Open Sentence	Relation as a Set of Ordered Pairs
The "less than" relation on $ℝ$
The "equality" relation on $ℝ$	$x=y$	$\{(x,y)\in ℝ\times ℝ\mid x=y\}$
The "divides" relation on $\mathbb{Z}$	$m\mid n$	$\{(m,n)\in \mathbb{Z}\times \mathbb{Z}\mid m$ divides $n\}$
The "subset" relation on $𝒫(U)$	$S\subseteq T$	$\{(S,T)\in 𝒫(U)\times 𝒫(U)\mid S\subseteq T\}$
The "element of" relation from $U$ to $𝒫(U)$	$x\in S$	$\{(x,S)\in U\times 𝒫(U)\mid x\in S\}$
The "congruence modulo $n$" relation on $\mathbb{Z}$	$a\equiv b(modn)$	$\{(a,b)\in \mathbb{Z}\times \mathbb{Z}\mid a\equiv b(modn)\}$

Table 7.1: Standard Mathematical Relations

7.1.7 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
used symbol is "˜", read "tilde" or "squiggle" or "is related to." When we do this, we will write

7.1.8 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}\mid m\text{ divides }n\}$$

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

$$m\mid n\text{ 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.

   1. For every nonzero integer $a,a\mid a$.

   2. For all nonzero integers $a$ and $b$, if $a\mid b$, then $b\mid a$.

   3. For all nonzero integers $a,b$, and $c$, if $a\mid b$ and $b\mid c$, then $a\mid c$.

7.1.9 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))\mid a\in A\}\text{ or }f=\{(a,b)\in A\times B\mid b=f(a)\}$$

This means that $f$ is a relation from $A$ to $B$. Since, $\mathrm{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\ne 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.

$$T=\{(x,y)\in ℝ\times ℝ\mid x^2+y^2=64\}$$

This relation fails condition (2) above since a counterexample comes from the facts that $(0,8)\in T$ and $(0,-8)\in T$ and $8\ne -8$.

7.1.10 Progress Check 7.4 (A Set of Ordered Pairs)

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

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:

   1. $A=\{x\in ℝ\mid (x,4)\in F\}$

   2. $B=\{x\in ℝ\mid (x,10)\in F\}$

   3. $C=\{y\in ℝ\mid (5,y)\in F\}$

   4. $D=\{y\in ℝ\mid (-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 $ℝ$ to $ℝ$. Draw a graph of this function.

7.1.11 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 $ℝ$ to $ℝ$. 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 ℝ\times ℝ\mid 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 $ℝ$ to a subset of $ℝ$, 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 ℝ\times ℝ\mid y\ge x^2\},$$

Figure 7.2: Directed Graph for a Relation

7.1.12 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\mid x$ divides $y\},T=\{(x,y)\in A\times A\mid x+y$ is even $\}$.

Figure 7.3: Vertices for $A$

7.1.13 Exercises 7.1

1. $(\star )$ 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)\}$.

   1. 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$.

   2. Explain why $R$ is a relation from $A$ to $B$.

   3. What is the domain of $R$? What is the range of $R$?

2. $(\star )$ 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.

   1. For each $x\in A,xRx$.

   2. For every $x,y\in A$, if $xRy$, then $yRx$.

   3. For every $x,y,z\in A$, if $xRy$ and $yRz$, then $xRz$.

   4. $R$ is a function from $A$ to $A$.

3. Let $A$ be the set of all female citizens of the United States. Let $D$ be the relation on $A$ defined by

   $$D=\{(x,y)\in A\times A\mid x\text{ is a daughter of }y\}$$

   That is, $xDy$ means that $x$ is a daughter of $y$.

   1. $(\star )$ Describe those elements of $A$ that are in the domain of $D$.

   2. $(\star )$ Describe those elements of $A$ that are in the range of $D$.

   3. Is the relation $D$ a function from $A$ to $A$? Explain.

4. $(\star )$ Let $U$ be a nonempty set, and let $R$ be the "subset relation" on $𝒫(U)$. That is,

   $$R=\{(S,T)\in 𝒫(U)\times 𝒫(U)\mid S\subseteq T\}$$

   1. Write the open sentence $(S,T)\in R$ using standard subset notation.

   2. What is the domain of this subset relation, $R$?

   3. What is the range of this subset relation, $R$?

   4. Is $R$ a function from $𝒫(U)$ to $𝒫(U)$? Explain.

5. Let $U$ be a nonempty set, and let $R$ be the "element of" relation from $U$ to $𝒫(U)$. That is,

   $$R=\{(x,S)\in U\times 𝒫(U)\mid x\in S\}$$

   1. What is the domain of this "element of" relation, $R$?

   2. What is the range of this "element of" relation, $R$?

   3. Is $R$ a function from $U$ to $𝒫(U)$? Explain.

6. $(\star )$ Let $S=\{(x,y)\in ℝ\times ℝ\mid x^2+y^2=100\}$.

   1. 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$.

   2. Determine the domain and range of the relation $S$ and write each set using set builder notation.

   3. Is the relation $S$ a function from $ℝ$ to $ℝ$? Explain.

   4. Since $S$ is a relation on $ℝ$, 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 $ℝ$ defined by

   $$S=\{(x,y)\in ℝ\times ℝ\mid 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 $ℝ$ and sketch the graph of each relation.

   1. $R=\{(x,y)\in ℝ\times ℝ\mid x^2+y^2=10\}$

   2. $S=\{(x,y)\in ℝ\times ℝ\mid y^2=x+10\}$

   3. $T=\{(x,y)\in ℝ\times ℝ||x|+|y|=10\}$

   4. $R=\{(x,y)\in ℝ\times ℝ\mid x^2=y^2\}$

9. Let $R$ be the relation on $\mathbb{Z}$ where for all $a,b\in \mathbb{Z},aRb$ if and only if $|a-b|\le 2$.

   1. $(\star )$ Use set builder notation to describe the relation $R$ as a set of ordered pairs.

   2. $(\star )$ Determine the domain and range of the relation $R$.

   3. Use the roster method to specify the set of all integers $x$ such that $xR5$ and the set of all integers $x$ such that $5Rx$.

   4. If possible, find integers $x$ and $y$ such that $xR8,8Ry$, but $x\mathit{R̸}y$.

   5. If $b\in \mathbb{Z}$, use the roster method to specify the set of all $x\in \mathbb{Z}$ such that $xRb$.

10. Let . This means that is the "less than" relation on $ℝ$.

    1. What is the domain of the relation ?

    2. What is the range of the relation ?

    3. Is the relation a function from $ℝ$ to $ℝ$? 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.

7.1.14 Explorations and Activities

1. The Inverse of a Relation. (The results of this section will be termed Theorem 7.6.) 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

$f^{-1}$ $=\{(b,a)\in B\times A\mid f(a)=b\}$

$=\{(b,a)\in B\times A\mid (a,b)\in f\}$

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

$R^{-1}=\{(y,x)\in B\times A\mid (x,y)\in R\},\text{ or}$

$R^{-1}=\{(y,x)\in B\times A\mid xRy\}.$

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

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}\mid m\text{ divides }n\}$$