Section 7.5 Equivalence Relations

We have seen examples of equivalence in this textbook, including logical equivalence and isomorphic graphs. You may have seen geometric equivalences such as congruent or similar triangles. In this section, we formalize the notion of equivalence by defining an equivalence relation and equivalence classes.

Subsection 7.5.A Properties of Relations

There are three properties that an relation needs to satisfy in order to be an equivalence relation.

Definition 7.5.1 Equivalence Relation.

Consider a relation \(R\) on a set \(X\text{.}\)

The relation \(R\) is reflexive if \((x,x) \in R\) for all \(x \in X\text{.}\) If the relation is defined by \(\sim\text{,}\) then we need \(x \sim x\) for all \(x \in X\text{.}\) For example, the relation

\begin{equation*} R=\{ (a,b) \mid a, b\in \mathbb{Z} \text{ and } ab \ge 0\} \end{equation*}

is reflexive on \(\mathbb{Z}\text{,}\) because for any \(a \in \mathbb{Z}\) we have \(aa=a^2 \ge 0\text{.}\) Thus \((a,a) \in R\text{.}\)
The relation \(R\) is symmetric if whenever \((x,y) \in R\text{,}\) then also \((y,x)\in R\) for all \(x,y \in X\text{.}\) If the relation is defined by \(\sim\text{,}\) then we need if \(x \sim y\text{,}\) then \(y \sim x\) for all \(x,y \in X\text{.}\) For example, the relation

\begin{equation*} R=\{ (a,b) \mid a, b\in \mathbb{Z} \text{ and } ab = 0\} \end{equation*}

is symmetric on \(\mathbb{Z}\text{,}\) because for any \(a,b \in \mathbb{Z}\) with \((a,b) \in R\) we have \(ab=0\text{.}\) Thus \(ba=0\) and so \((b,a) \in R\text{.}\)
The relation \(R\) is transitive if whenever \((x,y) \in R\) and \((y,z) \in R\text{,}\) then \((x,z)\in R\) for all \(x,y,z \in X\text{.}\) If the relation is defined by \(\sim\text{,}\) then we need if \(x \sim y\) and \(y \sim z\text{,}\) then \(x \sim z\) for all \(x,y,z \in X\text{.}\) For example, the relation

\begin{equation*} R=\{ (a,b) \mid a, b\in \mathbb{Z} \text{ and } a \le b\} \end{equation*}

is transitive on \(\mathbb{Z}\text{,}\) because for any \(a,b,c \in \mathbb{Z}\) with \((a,b) \in R\) and \((b,c) \in R\) we have \(a \le b\) and \(b \le c\text{.}\) Thus \(a \le c\) and so \((a,c) \in R\text{.}\)
The relation \(R\) is an equivalence relation if it is reflexive, symmetric, and transitive. For example, The relation

\begin{equation*} R=\{ (a,b) \mid a, b\in \mathbb{Z} \text{ and } a^2=b^2\} \end{equation*}

is an equivalence relation.

Let’s look at an example of relations on a finite set.

Example 7.5.2 Properties of Relations on a Finite Set.

Consider the relation \(R\) whose directed graph is drawn in Figure 7.5.3.

Figure 7.5.3. The relation \(R\) is transitive but not reflexive and not symmetric.

Is \(R\) reflexive? Justify your answer.
Solution.

No, while there is a loop at 1, there are no loops at 2 or 3. Thus \((1,1)\in R\text{,}\) but \((2,2)\notin R\) and \((3,3) \notin R\text{.}\) To be reflexive, we’d need a loop at every point.
Is \(R\) symmetric? Justify your answer.
Solution.

No, we have single-headed arrows. For example, there is an arrow from 2 to 1 but no arrow from 1 to 2. Thus \((1,2) \in R\text{,}\) but \((2,1) \in R\text{.}\) To be symmetric, we’d need only double-headed arrows and loops.

Is \(R\) transitive? Justify your answer.

Solution.

Yes. We need to check if \((x,y) \in R\) and \((y,z) \in R\text{,}\) then \((x,z) \in R\text{.}\) It turns out that there are four \((x,y)\text{,}\) \((y,z)\) pairs to check as shown in Table 7.5.4. Since for all four pairs \((x,z) \in R\text{,}\) the relation is transitive.

Table 7.5.4. Justifying that the relation \(R\) drawn in Figure 7.5.3 is transitive

\((x,y)\)	\((y,z)\)	\((x,z)\)	in \(R\text{?}\)

\((1,1)\)	\((1,1)\)	\((1,1)\)	Yes
\((1,1)\)	\((1,3)\)	\((1,3)\)	Yes
\((2,1)\)	\((1,1)\)	\((2,1)\)	Yes
\((2,1)\)	\((1,3)\)	\((2,3)\)	Yes

Your turn to work with properties of relations

Activity 7.5.A Properties of relations.

For parts (a)-(d), consider the relations on \(X = \{1,2,3\}\) defined by

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

and

\begin{equation*} V = \{(1,1), (2,3), (3,2)\}\text{.} \end{equation*}

Figure 7.5.6 shows their directed graph.

Figure 7.5.6. The relations \(T\) and \(V\) from Activity 7.5.A.

Give a counterexample to show that \(V\) is not reflexive. Is \(T\) reflexive? Explain.
Give a counterexample to show that \(T\) is not symmetric. Is \(V\) symmetric? Explain.
Give a counterexample to show that \(T\) is not transitive.
Give a counterexample to show that \(V\) is not transitive. Hint: The values of \(x\text{,}\) \(y\text{,}\) and \(z\) do not need to be distinct.
Consider the relation on \(\mathbb{Z}\) defined by

\begin{equation*} \{(a,b) \mid a, b \in \mathbb{Z} \text{ and } \fn{gcd}(a,b)=1\}\text{.} \end{equation*}

Decide which properties \(R\) has: reflexive, symmetric, transitive. No justification is required if the relation has the property, but provide a counterexample if not.
Consider the relation \(\sim\) on \(\mathbb{R}^2\) defined by \((x_1,y_1) \sim (x_2,y_2)\) if \(y_2-y_1=3(x_2-x_1)\text{.}\) Check that \(\sim\) is an equivalence relation. Hint: For transitive, note that \((y_3-y_2)+(y_2-y_1)=y_3-y_1\text{.}\)

Each of the relations \(T\) and \(V\) in Activity 7.5.A was not transitive, but for fundamentally different reasons. Let’s take a closer look at transitivity of relations on a finite set.

Example 7.5.7 When is a relation on finite set transitive?

We saw in Example 7.5.2 how to use the directed graph of a relation on a finite set to determine whether the relation is reflexive or symmetric. How can we use the directed graph of a relation on a finite set to determine whether the relation is transitive?

Solution.

Suppose \(R\) is a relation on a finite set \(X\) and that \((x,y) \in R\) and \((y,z) \in R\text{.}\) There are four cases, as drawn in Figure 7.5.8.

Figure 7.5.8. Shortcuts and barbells: checking transitivity on finite relation.

Case 1: First, consider when \(x\text{,}\) \(y\text{,}\) and \(z\) are three distinct elements of \(X\text{.}\) Then the directed graph has arrows from \(x\) to \(y\) and from \(y\) to \(z\text{.}\) We need to check if \((x,z) \in R\text{,}\) indicated by the dashed arrow from \(x\) to \(z\) in our diagram. To be transitive, any time we have a two-step path in the directed graph, we must also have the shortcut (vector sum).

Case 2: Next, consider when \(x=y\) or \(y=z\text{.}\) If \(x=y\text{,}\) then \((x,z) =(y,z)\in R\text{.}\) If \(y=z\text{,}\) then \((x,z) =(x,y)\in R\text{.}\) In either case \((x,z)\) is automatically in \(R\) so we can ignore this case.

Case 3: The remaining case is when \(x = z\text{.}\) We need to check \((x,x)=(x,z) \in R\text{.}\) Swapping order, we also need to check \((z,z)=(z,x)\in R\text{.}\) That is, any time there is a double-headed arrow in the graph, we need to have a loop at each end, or barbells, which we draw in our diagram with dashed loops.

Equivalence relations can be defined on all types of discrete objects.

Example 7.5.9 Examples of equivalence relations on graphs.

Consider the set \(G_6\text{,}\) the set of all graphs on six vertices. Give some examples of equivalence relations on \(G_6\text{.}\)

Solution.

There are many different examples. Here are a few:

\(G \sim H\) if \(G\) and \(H\) have the same number of edges.
\(G \sim H\) if \(G\) and \(H\) have the same degree sequence.
\(G \sim H\) if \(G\) and \(H\) contain the same number of 3-cycles.
\(G \sim H\) if \(G \cong H\text{,}\) where \(\cong\) denotes that the graphs are isomorphic.

Subsection 7.5.B Equivalence Relations and Equivalence Classes

An important construction in advanced theoretical mathematics is to take a set \(X\) and an equivalence relation \(\sim\) on \(X\) and define a new set consisting of the equivalence classes of \(X\) under \(R\text{.}\) We begin with the definitions.

Definition 7.5.10 Equivalence classes.

Consider a set \(X\) and an equivalence relation \(R\) (or \(\sim\)) on \(X\text{.}\)

For any element \(a \in X\text{,}\) the equivalence class containing \(a\) is the set

\begin{equation*} [a]=\{b \in X \mid (a,b) \in R\} = \{b \in X \mid a \sim b\}\text{.} \end{equation*}

For example, for the relation

\begin{equation*} R=\{ (a,b) \mid a, b\in \mathbb{Z} \text{ and } a^2 =b^2 \}\text{,} \end{equation*}

the equivalence class of \(3\) is \([3] = \{3,-3\}\text{.}\) Note that \([-3]=\{3,-3\}\) is the same set.
The quotient space, denoted \(X/R\) and pronounced “\(X\) mod \(R\)”, is the set of all equivalence classes. For example, for the relation \(R = \{(a,b) \mid a, b\in \mathbb{Z} \text{ and } a+b \text{ is even } \}\text{,}\) there are two equivalence classes: \([0]=\) the even integers and \([1]=\) the odd integers. Thus \(\mathbb{Z}/R = \{[0],[1]\}\text{.}\)

Let’s look at an example.

Example 7.5.11 Equivalence classes for an equivalence relation on \(\{1,2,3,4,5\}\).

Consider the equivalence relation \(R\) on \(X = \{1,2,3,4,5\}\) defined by the directed graph drawn in Figure 7.5.12.

Figure 7.5.12. An equivalence relation on \(\{1,2,3,4,5\}\text{.}\)

Calculate \([1]\text{.}\)
Solution.

There are three arrows out of 1 or, equivalently, three ordered pairs of the form \((1,\underline{~})\text{,}\) namely \((1,1)\text{,}\) \((1,3)\text{,}\) and \((1,4)\text{.}\) Thus \([1]=\{1,3,4\}\text{.}\)
Calculate \([2]\text{.}\)
Solution.

There are two arrows out of 2 or, equivalently, two ordered pairs of the form \((2,\underline{~})\text{,}\) namely \((2,2)\) and \((2,5)\text{.}\) Thus \([2]=\{2,5\}\text{.}\)
How many different equivalence classes are there?
Solution.

We can check that \([3]=\{1,3,4\}\text{,}\) \([4]=\{1,3,4\}\text{,}\) and \([5]=\{2,5\}\text{.}\) Therefore, there are only two equivalence classes: \(\{1,3,4\}\) and \(\{2,5\}\text{.}\) It is convenient to refer to these equivalence classes using the smallest possible representative as \([1]\) and \([2]\text{.}\)
Describe the quotient space \(X/R\text{.}\)
Solution.

The quotient space consists of two equivalence classes: \(X/R=\{[1],[2]\}\text{.}\)

Try working with equivalence classes.

Activity 7.5.B Equivalence classes.

Consider the relation \(R\) on \(\{1,2,3,4\}\) defined by \(R= \{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}\text{.}\) Identify the equivalence classes \([1]\text{,}\) \([2]\text{,}\) \([3]\text{,}\) and \([4]\text{.}\) How many distinct equivalence classes are there?
Draw the directed graph of the equivalence relation on \(\{1,2,3,4,5,6\}\) with equivalence classes \(\{1,2,3\}\text{,}\) \(\{4\}\text{,}\) and \(\{5,6\}\text{.}\)
Consider the equivalence relation \(R\) on \(\mathbb{Z}\) defined by

\begin{equation*} R=\{ (a,b) \mid a, b\in \mathbb{Z} \text{ and } a^2 =b^2 \}\text{.} \end{equation*}

Calculate \([2]\text{,}\) \([-4]\text{,}\) and \([0]\text{.}\)
Consider the equivalence relation \(\sim\) on \(\mathbb{R}^2\) defined by \((x_1,y_1) \sim (x_2,y_2)\) if \(y_2-y_1=3(x_2-x_1)\text{.}\) Describe the equivalence class \([(0,2)]\text{.}\)
Let \(\mathbb{B}_5\) be the set of all bit strings of length 5. Consider the equivalence relation on \(\mathbb{B}_5\) defined by \(b \sim c\) if the bit strings \(b\) and \(c\) start with the same three bits. For example, \(\bs{11111} \sim \bs{11100}\) and \(\bs{10111} \sim \bs{10110}\text{.}\) Calculate \([11111]\) and \([10111]\text{.}\)
Continuing with the relation \(\sim\) on \(\mathbb{B}_5\) defined in (e). How many (distinct) equivalence classes are there and how many bit strings are in each equivalence class?
Give an example of an equivalence relation on \(\mathbb{B}_5\text{,}\) the bit strings of length 5, that has exactly two equivalence classes. Now give a different one.

In Example 7.5.11, we had an equivalence relation on the set \(\{1,2,3,4,5\}\) and the equivalence classes were \(\{1,3,4\}\) and \(\{2,5\}\text{.}\) Note that \(\{1,3,4\} \cup \{2,5\}\) is a partition of the set \(\{1,2,3,4,5\}\text{,}\) as defined in Definition 7.3.1. Conversely, in Activity 7.5.B (b), we had a partition \(\{1,2,3\} \cup \{4\} \cup \{5,6\}\) of the set \(\{1,2,3,4,5,6\}\) and we determined the directed graph of an equivalence relation \(R\) on \(\{1,2,3,4,5,6\}\) having those subsets as equivalence classes. This connection between equivalence classes and partitions of a set holds in general.

Remark 7.5.14 Equivalence classes and partitions.

Let \(X\) be a set.

If \(R\) is an equivalence relation on \(X\text{,}\) then the distinct equivalence classes under \(R\) form a partition of the set \(X\text{.}\)
If \(T_1 \cup T_2 \cup \cdots \cup T_k\) is a partition of \(X\text{,}\) then the relation on \(R\) defined by \((x,y) \in R\) if \(x\) and \(y\) are both in the same set \(T_i\) for some \(i\) is an equivalence relation. Moreover, its equivalence classes are exactly \(T_1, T_2, \ldots, T_k\text{.}\)

Subsection 7.5.C Congruence mod \(n\)

An important equivalence relation on \(\mathbb{Z}\) is defined using \(\fn{mod}\text{.}\)

Definition 7.5.15 Congruence mod \(n\).

For a positive integer \(n\text{,}\) the integers \(a\) and \(b\) are congruent modulo \(n\text{,}\) denoted \(a \equiv b ~(\fn{mod} ~n)\text{,}\) if \(a \fn{~mod~} n = b \fn{~mod~} n\text{,}\) that is, if \(a\) and \(b\) have the same remainder when divided by \(n\text{.}\) For example, \(73 \equiv 13 ~(\fn{mod} ~10)\) because \(73 \fn{~mod~} 10 = 3\) and \(73 \fn{~mod~} 10 = 3\text{.}\) As another example, for any integer \(a\text{,}\) if \(a ~\fn{mod}~ n=r\text{,}\) then that \(a \equiv r ~(\fn{mod} ~n)\text{.}\) For example, \(73 \equiv 3 ~(\fn{mod} ~10)\text{.}\) It turns out that congruence modulo \(n\) is an equivalence relation.
For a positive integer \(n\text{,}\) the congruence class mod \(n\) of \(a\) is

\begin{equation*} [a]_n = \{ b \in \mathbb{Z} \mid a \equiv b ~(\fn{mod} ~n)\}\text{.} \end{equation*}

Note that the congruence class is the equivalence class under the congruence relation. For example,

\begin{equation*} [3]_{10} = \{\ldots, -17, -7, 3, 13, 23, 33, 43, \ldots\}\text{.} \end{equation*}
The integers mod \(n\) introduced in Section 4.3 is formally defined as

\begin{equation*} \mathbb{Z}_n = \{[0]_n, [1]_n, \ldots, [n-1]_n\}\text{.} \end{equation*}

For example, \(\mathbb{Z}_3 = \{[0]_3, [1]_3, [2]_3\}\text{.}\)

Note that if \(a \fn{ mod } n = b \fn{ mod } n\text{,}\) then \(a\) and \(b\) end at the same number on the \(\fn{mod } n\) clock. Therefore, \(a\) and \(b\) differ by some number of complete rotations, which is multiple of \(n\text{.}\) We have the following result.

Theorem 7.5.16 Alternate characterization of congruence \(\fn{mod}\) \(n\).

Let \(a\text{,}\) \(b\text{,}\) and \(n\) be integers with \(n > 1\text{.}\) Then \(a \equiv b ~(\fn{mod } n)\) if and only if \(n | (a-b)\text{.}\)

Let’s look at some examples.

Example 7.5.17 Using the alternate characterization of congruence \(\fn{mod}\) \(n\).

Use Theorem 7.5.16 to show that \(73 \equiv 13 ~(\fn{mod } 10)\text{.}\)
Solution.

We can check that \(73-13 = 60 = 10(6)\) and so \(10 \mid (73-13)\text{.}\) Thus \(73 \equiv 13 ~(\fn{mod } 10)\text{.}\)
Prove that if \(a \equiv b ~(\fn{mod } n)\text{,}\) then \(2a \equiv 2b ~(\fn{mod } n)\) for any integers \(a\text{,}\) \(b\text{,}\) and \(n\) with \(n > 1\text{.}\)
Solution.

Since we are proving a conditional statement, we use Theorem 5.3.13.

Proof Let \(a\text{,}\) \(b\text{,}\) and \(n\) be integers with \(n > 1\text{.}\) Assume \(a \equiv b ~(\fn{mod } n)\text{.}\) By Theorem 7.5.16, it follows that \(n \mid (a-b)\text{.}\) By Definition 4.1.8, we can write \(a-b = nk\) for some integer \(k\text{.}\) Then

\begin{equation*} 2a - 2b = 2(a-b) = 2(nk) = n(2k) = nk' \end{equation*}

where \(k' = 2k\) is an integer. By Definition 4.1.8, it follows that \(n \mid (2a-2b)\text{.}\) By Theorem 7.5.16, it follows that \(2a \equiv 2b ~(\fn{mod } n)\text{.}\)
State the converse of the statement from (b) and construct a counterexample to show that the converse is false.
Solution.

The converse is: if \(2a \equiv 2b ~(\fn{mod } n)\text{,}\) then \(a \equiv b ~(\fn{mod } n)\) for any integers \(a\text{,}\) \(b\text{,}\) and \(n\) with \(n > 1\text{.}\) For a counterexample we need integers \(a\text{,}\) \(b\text{,}\) and \(n\) with \(n > 1\) such that the promise is broken. That is, we want \(2a \equiv 2b ~(\fn{mod } n)\) but \(a \not\equiv b ~(\fn{mod } n)\text{.}\) A counterexample is \(a=2\) and \(b=7\) because \(4 \equiv 14 ~(\fn{mod } 10)\) but \(2 \not\equiv 7 ~(\fn{mod } 10)\text{.}\)

Try working with congruence mod \(n\text{.}\)

Activity 7.5.C Congruence \(\fn{mod}\) \(n\).

True or false? \(73 \equiv 13 ~(\fn{mod } 2)\)
True or false? \(73 \equiv 13 ~(\fn{mod } 3)\)
True or false? \(73 \equiv 13 ~(\fn{mod } 4)\)
True or false? \(73 \equiv 13 ~(\fn{mod } 5)\)
Find a counterexample to the statement \(73 \equiv 13 ~(\fn{mod } n)\) for all integers \(n >1\text{.}\) Hint: \(73-13=60\text{.}\)
Describe the integers in \([0]_2\text{.}\)
Describe the integers in \([0]_3\text{.}\)
How many congruence classes are there \(\fn{mod}\) 10? Explain.
Explain why congruence \(\fn{mod}\) \(n\) is reflexive, symmetric, and transitive.

Subsection 7.5.D Exercises

Subsubsection Exercises for 7.5.A Properties of Relations

1. Practice.

Construct a counterexample to show the relation

\begin{equation*} \{ (a,b) \mid a, b \in \mathbb{Z} \text{ and } a \lt b \} \end{equation*}

is not reflexive.
Construct a counterexample to show the relation

\begin{equation*} \{ (a,b) \mid a, b \in \mathbb{Z}^+ \text{ and } a \mid b \} \end{equation*}

is not symmetric.
Construct a counterexample to show the relation

\begin{equation*} \{ (a,b) \mid a, b \in \mathbb{Z} \text{ and } ab = 0 \} \end{equation*}

is is not transitive.

Check.

Hint: One possible counterexample is \((5,5)\) because \(5\lt 5\) is false. Provide a different counterexample.
Hint: Find integers \(a\) and \(b\) where \(a \mid b\) but \(b \nmid a\text{.}\)
Hint: Use one of \(a\) or \(b\) equal to 0.

2. Practice.

Construct a counterexample to show the relation

\begin{equation*} \{ (x,y) \mid x, y \in \mathbb{R} \text{ and } x + y = 5 \} \end{equation*}

is not reflexive.
Construct a counterexample to show the relation

\begin{equation*} \{ (x,y) \mid x, y \in \mathbb{R} \text{ and } x \ge y \} \end{equation*}

is not symmetric.
Construct a counterexample to show the relation

\begin{equation*} \{ (x,y) \mid x, y \in \mathbb{R} \text{ and } |x - y | \lt 3 \} \end{equation*}

is not transitive.

Check.

Hint: One possible counterexample is \((2,2)\) because \(2+2 \neq 5\text{.}\)
Hint: Find real numbers \(x\) and \(y\) with \(x \ge y\) but not \(y \ge x\text{.}\)
Hint: Try some examples.

3. Practice.

Construct a counterexample to show that the relation \(\{(0,0), (0,1), (1,1), (1,2), (2,0), (2,2)\}\) is not transitive.
Construct a counterexample to show that the relation \(\{(0,0), (0,1), (1,0), (2,2)\}\) is not transitive.
Show how to check that the relation \(\{(0,0), (0,1), (1,1), (1,2), (0,2), (2,2)\}\) is transitive. Note: It is okay to not check loops.

Check.

Hint: Find a missing shortcut.
Hint: Barbells
Hint: For example, check \((0,1)\) and \((1,2)\) are in the relation and \((0,2)\) is too.

4. Understand.

For each relation, draw the directed graph on \(\{0,1,2\}\) and then decide if the relation is reflexive, symmetric, and transitive. For each part, no justification required if the relation has the property, but provide counterexample if not.

\(\displaystyle \{(0,0), (0,1), (1,0), (1,1), (1,2), (2,2)\}\)
\(\displaystyle \{(0,0), (0,1), (0,2), (1,1), (1,2), (2,2)\}\)
\(\displaystyle \{(0,0), (0,1), (1,0), (1,1), (2,2)\}\)

Check.

Hint: It is reflexive, but not symmetric and not transitive.
Hint: It has two of the three properties.
Hint: It is an equivalence relation.

5. Understand.

On this problem, no justification is required.

Draw the directed graph for each relation on \(\{0,1\}\) that is reflexive.
Draw the directed graph for each relation on \(\{0,1\}\) that is symmetric and reflexive.
Draw the directed graph for each relation on \(\{0,1\}\) that not transitive. Hint: Barbells
Draw the directed graph for each equivalence relations on \(\{0,1\}\text{.}\) Hint: Use your lists from 5.(b) and 5.(c).

6. Understand.

Let \(X\) be a nonempty set. For each relation, decide whether it is reflexive, whether it is symmetric, and whether it is transitive. No justification required if the relation has the property, but provide counterexample if not.

The relation \(\varnothing\)
The relation \(X^2\)

7. Understand.

For each relation, decide whether it is reflexive, whether it is symmetric, and whether it is transitive. No justification required if relation has the property, but provide counterexample if not.

\(\displaystyle \{(a,b) \mid a,b \in \mathbb{Z}^+ \text{ and } ab \text{ is even } \}\)
\(\displaystyle \{(a,b) \mid a,b \in \mathbb{Z}^+ \text{ and } ab \text{ is odd } \}\)
\(\{(a,b) \mid a,b \in \mathbb{Z}^+ \text{ and } \fn{gcd}(a,b)\neq1~ \}\) As usual, \(\fn{gcd}\) denotes the greatest common divisor, as defined in Definition 4.5.1.

Check.

Hint: It is not reflexive and not transitive.
Hint: The only way \(ab\) is odd is if \(a\) is odd and \(b\) is odd.
Hint: It is not reflexive but there’s only one possible counterexample.

8. Understand.

Consider the unit circle

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

which is drawn in Figure 6.3.9. For each part, no justification is required if \(U\) has the property, but provide counterexample if not.

Is \(U\) reflexive?
Is \(U\) symmetric?
Is \(U\) transitive?

9. Understand.

Consider the relation defined on \(\mathbb{R}^2\) by \((x_1,y_1) \sim (x_2,y_2)\) if

\begin{equation*} \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2} \le 5\text{.} \end{equation*}

Is \((1,2) \sim (1,7)\text{?}\) Explain.
Is \((1,2) \sim (5,0)\text{?}\) Explain.
Is \(\sim\) reflexive? Explain.
Construct a counterexample to show that \(\sim\) is not transitive.

Check.

Hint: Yes
Hint: No
Hint: Yes
Hint: Try using \((0,0)\) as the second ordered pair to construct a counterexample.

10. Understand.

For each relation, decide whether it is transitive. Explain briefly if it is transitive and construct a counterexample if not transitive.

As usual \(\mathbb{B}^*\) denotes the set of all (non-empty) bit strings. Define a relation on \(\mathbb{B}^*\) by \(b \sim c\) if \(b\) is a substring of \(c\text{;}\) that is, if the bit string \(b\) appears in consecutive order within the bit string \(c\text{.}\) For example, \(\bs{101} \sim \bs{111010}\) as we can see \(\bs{11}\underline{\bs{101}}\bs{0}\text{.}\)
Consider the set \(\mathbb{B}_3\text{,}\) the set of all bit strings of length 3. Define the relation \(b \sim c\) if the bit strings \(b\) and \(c\) differ in exactly one bit. For example, \(100 \sim 110\) and \(100 \sim 000\text{.}\)

Check.

Hint: It is transitive.
Hint: It is not transitive.

11. Understand.

Consider the following relations on \(\mathscr{P}(\{1,2,3\})\text{.}\)

Give a counterexample to show that \(\{(A,B) \mid ~ A \cup B = S ~ \}\) is not reflexive.
Give a counterexample to show that \(\{(A,B) \mid ~ A \subseteq B~ \}\) is not symmetric.
Give a counterexample to show that \(\{(A,B) \mid ~ A \cap B = \varnothing ~ \}\) is not transitive.

Check.

Recall that \(\mathscr{P}(\{1,2,3\})\) is the power set of \(\{1,2,3\}\text{,}\) the set of all subsets of \(\{1,2,3\}\text{.}\)

Hint: One counterexample is \((\{1,2\},\{1,2\})\text{.}\)
Hint: Find subsets \(A\) and \(B\) where \(A \subseteq B\) but not \(B \subseteq A\text{.}\)
Hint: Start with subsets \(A\) and \(B\) such that \(A \cap B = \varnothing\text{.}\) Then try to find a set \(C\) with \(B \cap C = \varnothing\) but \(A \cap C \neq \varnothing\text{.}\)

12. Understand.

For the set \(\mathscr{P}(\{1,2,3, \ldots, n\})\text{,}\) define \(A \sim B\) if \(|A| = |B|\) (meaning \(A\) and \(B\) have the same number of elements). Check that \(\sim\) is an equivalence relation. Show how to check each property in general.

13. Recap.

Do you know …

How to decide if a relation is reflexive, symmetric, or transitive?
How to construct a counterexample to show that a relation is not reflexive, not symmetric, or not transitive?

14. Explore.

A relation \(R\) on a set \(X\) is antisymmetric if whenever \((x,y) \in R\) with \(x \neq y\) we have \((y,x) \notin R\text{.}\) No justification required if "yes", but provide counterexample if "no".

Is the relation R on \(\{(0,0), (0,1), (1,0), (2,2)\}\) antisymmetric?
Is the relation \(\{(0,0), (0,1), (1,1), (1,2), (0,2), (2,2)\}\) antisymmetric?
Is the relation \(\{ (a,b) \mid a, b \in \mathbb{Z} \text{ and } a \lt b \}\) antisymmetric?
Is the relation \(\{ (a,b) \mid a, b \in \mathbb{Z}^+ \text{ and } a \mid b \}\) antisymmetric? As usual, \(\mid\) denotes divides, as defined in Definition 4.1.8.

15. Explore.

In Exercise 14 we defined antisymmetric. In each part, give an example of a relation on \(\{0,1,2,3\}\) meeting the conditions. No justification required.

Antisymmetric and not symmetric.
Symmetric and not antisymmetric.
Neither symmetric nor antisymmetric.
Both symmetric and antisymmetric.

16. Explore.

A relation \(R\) on a set \(X\) is a partial order if \(R\) is reflexive, antisymmetric, and transitive. Prove that the relation \(\{ (x,y) \mid x, y \in \mathbb{R} \text{ and } x \le y \}\) is a partial order on \(\mathbb{R}\text{.}\) (By the way, some other examples of partial orders are \(\le\) or \(\ge\) on any sets of real numbers, \(\mid\) (divides) on the positive integers, \(\subseteq\) on the power set of any set, and contains as a substring on the set of all (non-empty) bit strings, as in Exercise 10.)

Subsubsection Exercises for 7.5.B Equivalence Relations and Equivalence Classes

17. Practice.

Consider the equivalence relation on \(\{1,2,3,4,5,6,7\}\) defined by

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

\begin{equation*} (4,3), (4,4), (5,1), (5,2), (5,5), (6,6), (6,7), (7,6), (7,7)\} \end{equation*}

Calculate \([5]\text{.}\)
Calculate \([6]\text{.}\)
How many distinct equivalence classes are there? Explain briefly.
Draw the directed graph of a new equivalence relation on \(\{1,2,3,4,5,6,7\}\) with exactly two distinct equivalence classes: \(\{1,2,3,4\}\) and \(\{5,6,7\}\text{.}\)

Check.

\(\displaystyle \{1,2,5\}\)
Hint: There are two elements in \([6]\text{.}\)
Hint: Calculate \([3]\text{.}\) Then count the distinct ones.
Hint: Make sure you have included all the necessary loops and double-headed arrows.

18. Practice.

For each equivalence relation on \(\mathbb{R}^+\) (the positive real numbers), describe the equivalence class [7.3]. Hint: If you are not sure where to start, find examples of real numbers \(y\) such that \(7.3 \sim y\text{.}\)

The equivalence relation defined by \(x \sim y\) if \(\lfloor x \rfloor = \lfloor y \rfloor\text{.}\)
The equivalence relation defined by \(x \sim y\) if \(x-\lfloor x \rfloor = y-\lfloor y \rfloor\text{.}\)
Restate the relation from 18.(a) in the form ``\(x \sim y\) if \(x\) and \(y\) have the same \(\underline{\hspace{1in}}\text{.}\) Repeat for the relation from 18.(b).

19. Practice.

Consider the equivalence relation defined on \(\mathbb{R}^2\) by \((x_1,y_1) \sim (x_2,y_2)\) if \(y_2-y_1=3(x_2-x_1)\) that we saw in Section 7.4 Exercise 25.

Describe \([(0,0)]\text{.}\)
Describe \([(1,0)]\text{.}\)
In general, describe each equivalence class. Hint: It is a set in the \(xy\)-plane.

Check.

It is the line \(y = 3x\) which has slope 3 and \(y\)-intercept 0.
Hint: It is a different line.
Hint: What do the lines have in common?

20. Practice.

Consider the equivalence relation defined on \(\mathbb{R}^2\) by \((x_1,y_1) \sim (x_2,y_2)\) if \(x_1=x_2\)

Describe \([(0,0)]\text{.}\)
Describe \([(1,0)]\text{.}\)
In general, describe each equivalence class. Hint: It is a set in the \(xy\)-plane.

Check.

It is the line \(x=0\) which is the \(y\)-axis.
Hint: It is a different line.
Hint: What do the lines have in common?

21. Understand.

Draw the directed graphs for both equivalence relation on \(X = \{1,2\}\) and list the equivalence classes for each.
Repeat for \(X = \{1,2,3\}\text{.}\) Hint: There are five different equivalence relations.
How many different equivalence relations are there on \(X = \{1,2,3,4\}\text{?}\) Explain your count.

22. Understand.

For any set \(X\text{,}\) equality \(E = \{(x,y) \mid x=y\}\) is the smallest possible equivalence relation.If \(X\) is finite, what does the directed graph of \(E\) look like? Describe the equivalence classes of \(E\text{.}\)
At the other extreme, \(X^2\) itself is an equivalence relation on \(X\text{.}\) If \(X\) is finite, what does the directed graph of \(X^2\) look like? How many equivalence classes are there?

23. Understand.

Consider the set \(\mathbb{B}_5\text{,}\) the set of all bit strings of length 5. Define the equivalence relation on \(\mathbb{B}_5\) by \(b \sim c\) if the bit strings \(b\) and \(c\) have the same weight, that is if \(b\) and \(c\) have the same number of \(\bs{1}\) s. For example, \(\bs{00111} \sim \bs{11010}\) and only \(\bs{11111} \sim \bs{11111}\text{.}\)

Calculate \([\bs{00111}]\) and \([\bs{11111}]\text{.}\)
How many (distinct) equivalence classes are there?
For each equivalence class, state how many bit strings are in that equivalence class.

Check.

Hint: There are ten bit strings in \([\bs{00111}]\) but only one bit string in \([\bs{11111}]\text{.}\)
Hint: The answer is not five.
Hint: Different classes may contain different number of bit strings.

24. Understand.

Consider the set \(\mathbb{B}_5\text{,}\) the set of all bit strings of length 5. Define the equivalence relation \(b \sim c\) if the bit strings \(b\) and \(c\) start with the same two bits. For example, \(11111 \sim 11000\) and \(10111 \sim 10101\text{.}\)

Calculate \([11111]\) and \([10111]\text{.}\)
How many (distinct) equivalence classes are there?
How many bit strings are in each equivalence class?

Check.

Hint: \([\bs{11111}] = \{\bs{11000}, \bs{11001}, \ldots, \bs{11111}\}\) and \([\bs{10111}]\) contains the same number of bit strings.
Four
Hint: They each contain the same number of bit strings.

25. Understand.

For \(\mathscr{P}(\{1,2,3,4,5\})\text{,}\) we saw in Exercise 12 that the relation \(A \sim B\) if \(|A| = |B|\text{,}\) meaning that \(A\) and \(B\) have the same number of elements, is an equivalence relation.

Calculate \([\{1,3\}]\) and [\(\phi\)].
How many (distinct) equivalence classes are there?
For each equivalence class, state how many subsets are in that equivalence class.
Comment on how this exercise relates to Exercise 23.

26. Understand.

For any set \(X\) and any function \(f:X \to X\text{,}\) the relation on \(X\) defined by \(x_1 \sim x_2\) if \(f(x_1) = f(x_2)\) is always an equivalence relation.

For readers who are familiar with trigonometry, describe \([0]\) where \(f: \mathbb{R} \to \mathbb{R}\) is defined by \(f(x) = \fn{sin}(x)\text{.}\)
For the function \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n) = n^2\text{,}\) explain why the equivalence classes are

\begin{equation*} \{0\}, \{1,-1\}, \{2,-2\}, \{3,-3\}, \{4,-4\}, \ldots \end{equation*}

Now give two more examples of functions with the same equivalence classes.
What can we say about a function \(f\) if each equivalence class is a singleton (one element set)?

27. Understand.

Define an equivalence relation on \(\mathbb{Z}\) by \(a \sim b\) if \(a\) and \(b\) have the same 2-part, that is, \(a \sim b\) if \(a = 2^km\) and \(b=2^kn\) for some nonnegative integer \(k\) and odd integers \(m\) and \(n\text{.}\)

Verify that \(12 \sim 20\text{.}\)
Verify that \(35 \sim 11\text{.}\)
Describe the equivalence class \([1]\text{.}\)
Describe the equivalence class \([2]\text{.}\)

28. Understand.

Define the equivalence relation on \(\mathbb{Z} \times\mathbb{Z}^\ast\) by \((a_1,b_1) \sim (a_2,b_2)\) if \(a_1b_2 = a_2b_1\text{.}\) By the way, the rational numbers \(\mathbb{Q}\) is the quotient space \(\mathbb{Z}/\sim\text{.}\)

Verify that \((4,6) \sim (2,3)\text{.}\)
Describe the equivalence class \([(2,3)]\text{.}\)

29. Recap.

Do you know …

What three properties a relation needs to satisfy in order to be an equivalence relation?
How to find the equivalence class of an element under a relation?
What we mean by “distinct” equivalence classes?
What the connection is between equivalence classes and partitions of a set?

30. Explore.

Consider the set \(X\) consisting of all \(2 \times 2\) grids where each of the four smaller squares is colored either gray or white. An example is drawn in Figure 7.5.49.

Figure 7.5.49. An example of a \(2 \times 2\) gray-and-white grid for Exercise 30.

How many different \(2 \times 2\) grids are there? Note that any number of the squares can be gray or white, not necessarily two of each as shown.
For grids \(G\) and \(H\text{,}\) define an equivalence relation on \(X\) by \(G \sim H\) if we can rotate \(G\) to obtain \(H\text{.}\) Calculate \([G]\) where \(G\) is the square drawn in Figure 7.5.49.
Under \(\sim\text{,}\) how many different equivalence classes of \(2 \times 2\) grids are there? Draw one \(2 \times 2\) grid from each equivalence class.

Check.

Hint: Count using steps with Step 1 is deciding if the upper left-hand corner is gray or white. Then continue with each of the four squares.
Hint: There are four squares in \([G]\text{,}\) one of which is \(G\) itself.
Hint: Draw one \(2 \times 2\) grid from each equivalence class, being sure that no two grids you draw are equivalent. Then count how many grids you drew.

31. Explore.

For readers who have studied calculus, consider the set \(X\) of all differentiable functions \(f: \mathbb{R} \to \mathbb{R}\text{.}\) Define an equivalence relation on \(X\) by \(f \sim g\) if \(f' = g'\text{,}\) meaning \(f'(x) = g'(x)\) for all \(x \in \mathbb{R}\text{.}\) That is, two functions are equivalent if they have the same derivative function.

Describe \([f]\) where \(f: \mathbb{R} \to \mathbb{R}\) is defined by \(f(x) = 3x+1\text{.}\)
Describe \([g]\) where \(g: \mathbb{R} \to \mathbb{R}\) is defined by \(g(x) = xe^x\text{.}\) Hint: you do not need to know what \(g'(x)\) is, just which functions have the same derivative as \(g\text{.}\)

Subsubsection Exercises for 7.5.C Congruence mod \(n\)

32. Practice.

Briefly justify your answers.

Is \(70 \equiv 34 ~(\fn{mod }5)\text{?}\)
Is \(70 \equiv 34 ~(\fn{mod }6)\text{?}\)
Is \(70 \equiv 34 ~(\fn{mod }11)\text{?}\)

Check.

Hint: Two answers are no.

33. Understand.

State the converse Definition 5.4.1 of each statement and then prove that the converse is false by constructing a counterexample. Each statement refers to all integers \(a\text{,}\) \(b\text{,}\) and \(n\) with \(n>1\text{.}\)

If \(a \equiv b ~(\fn{mod }n)\text{,}\) then \(3a \equiv 3b\text{ (mod } n)\text{.}\)
If \(a \equiv b \text{ (mod } n)\text{,}\) then \(a^2 \equiv b^2\text{ (mod } n)\text{.}\)
If \(a \equiv 0 ~(\fn{mod }n)\) or \(b \equiv 0 ~(\fn{mod }n)\text{,}\) then \(ab \equiv 0 ~(\fn{mod }n)\text{.}\)

Check.

Hint: Make \(n\) a multiple of 3.
Hint: Try \(n=10\) because \(\fn{mod}\) 10 is easy to compute (just the last digit)
Hint: Try \(n=10\) again.

34. Understand.

Let \(a\text{,}\) \(b\text{,}\) and \(n\) be integers with \(n>1\text{.}\) Prove each of the following statements using Theorem 7.5.16. Hint: Copy and edit the proof in Example 7.5.17 (b) .

If \(a \equiv b ~(\fn{mod }n)\text{,}\) then \(3a \equiv 3b\text{ (mod } n)\text{.}\)
If \(a \equiv b \text{ (mod } n)\text{,}\) then \(a+2 \equiv b+2\text{ (mod } n)\text{.}\)
If \(a \equiv b \text{ (mod } n)\text{,}\) then \(a^2 \equiv b^2\text{ (mod } n)\text{.}\) Hint: \(a^2-b^2=(a+b)(a-b)\text{.}\)

35. Recap.

Do you know …

What \(a \equiv b ~(\fn{mod}~n)\) means?
How to prove statements involving congruences?
How to find counterexamples to false statements involving congruences?
How the congruence class \(\fn{mod}\) \(n\) is defined?

Prev Top Next