## Section 4.2 Equivalence Relations

¶One particular kind of relation that plays a vital role in mathematics is an equivalence relation. Before defining an equivalence relation, we will consider definitions and examples of each of the properties involved.

###### Definition 4.2.1.

A relation \(R\) is reflexive if \((a, a) \in R\) for every \(a \in A\text{.}\) That is for each \(a \in A\text{,}\) We have \(aRa\text{.}\)

It is important to realize that this definition involves a quantified expression, “for each \(a \in A\text{.}\)” Recall from logic that when such an expression is negated, the quantifier changes. Hence, it follows that a relation is not reflexive if there exists even one element in \(A\) that is not related to itself.

###### Example 4.2.2.

The relation “\(\leq\)” on \(\mathbb Z\) has the reflexive property since every integer is less than or equal to itself.

###### Example 4.2.3.

The relation “\(=\)” on \(\mathbb R\) is reflexive since every real number is equal to itself.

###### Example 4.2.4.

The relation \(R = \{ (2, 3), (2,2), (3,2), (3,3) \}\) is not a reflexive relation on the set \(A = \{ 1, 2, 3\}\) since \(1 \in A\text{,}\) but \((1,1) \notin R\text{.}\) But \(R\) is reflexive when considered as a relation on the set \(B = \{2, 3 \}\text{.}\)

###### Example 4.2.5.

Let \(S\) be nonempty and \(\mathcal P(S)\) be the power set of \(S\text{.}\) Then the subset relation is reflexive on \(\mathcal P(S)\) since every set is a subset of itself.

###### Definition 4.2.6.

A relation \(R\) on \(A\) is symmetric if whenever \((a, b) \in R\text{,}\) then \((b,a) \in R\text{.}\) Alternatively, if \(aRb\text{,}\) then \(bRa\text{.}\)

You should notice a major distinction in the nature of the definitions of these terms. The definition of reflexive is universal in that it must be true for all members of the set upon which it is defined. In contrast, the definition for the symmetric property is stated in the form of a conditional. (Remember from formal logic that a conditional, \(p \rightarrow q\text{,}\) is false only when \(p\) is true and \(q\) is false.) So to show a relation is not symmetric we must be able to find an ordered pair \((a,b)\) in \(R\) such that \((b, a)\) is not in \(R\text{.}\)

###### Example 4.2.7.

Let \(A = \{ 1, 2, 3, 4 \}\) and consider the given relations on \(A\text{.}\) The relations \(R = \{ (1, 2), (2, 1), (3, 4), (4,3)\}\) and \(S = \{ (1,1)\}\) have the symmetric property. However, \(T = \{ (3,3). (2,4), (4,2), (1, 2) \}\) is not symmetric since \((1, 2) \in T\) but \((2, 1) \notin T\text{.}\)

It is important to remember that to show a relation does *not* have a certain property, we need only provide a single counterexample.

###### Example 4.2.8.

The relation “\(\geq\)” is not symmetric on \(\mathbb R\) since \(5 \geq 2\) but \(2 \not\geq 5\text{.}\)

###### Example 4.2.9.

Let \(A\) be the set of rectangles in the Cartesian plane, and let elements of \(A\) be related if they have the same area. Then this relation is symmetric.

###### Definition 4.2.10.

A relation \(R\) on \(A\) is transitive if whenever \((a, b) \in R\) and \((b, c) \in R\text{,}\) then \((a, c) \in R\text{.}\)

A relation \(R\) is not transitive if there exist \(a\text{,}\) \(b\text{,}\) and \(c\) in \(A\) such that \((a,b) \in R\) and \((b, c) \in R\) but \((a, c) \notin R\text{.}\)

###### Example 4.2.11.

The relation “\(\lt\)” is transitive on \(\mathbb R\text{.}\)

###### Example 4.2.12.

Let \(R = \{ (1, 1), (2, 2), (3,3) \}\) on \(\mathbb Z\text{.}\) Then \(R\) is transitive since there do not exist integers \(a\text{,}\) \(b\text{,}\) and \(c\) such that \((a,b) \in R\) and \((b, c) \in R\) but \((a, c) \notin R\text{.}\)

###### Example 4.2.13.

Let \(R = \{ (1, 2), (2, 3) \}\) on \(\mathbb Z\text{.}\) Then \(R\) is not transitive since \((1, 2) \in R\) and \((2, 3) \in R\) but \((1,3) \notin R\text{.}\)

###### Definition 4.2.14.

A relation \(R\) on \(A\) which is reflexive, symmetric, and transitive is called an equivalence relation on \(A\text{.}\) If two elements \(a\) and \(b\) are equivelent, we write \(a \sim b\text{,}\) unless of course there is already a notation in place such as “\(=\text{.}\)”

###### Example 4.2.15.

Let \(A = \{ 1, 2, 3\}\) and \(R = \{ (1, 1), (2, 2) \}\text{.}\) Then \(R\) is not an equivalence relation on \(A\text{.}\) The relation is both transitive and symmetric but is not reflexive since \((3, 3) \notin R\text{.}\)

###### Example 4.2.16.

Let \(A = \{ 1, 2, 3\}\) and

The relation \(S\) is both reflexive and symmetric but is not transitive, since \((1, 2) \in S\) and \((2, 3) \in S\) but \((1, 3) \notin S\text{.}\)

###### Example 4.2.17.

Let \(A = \{a, b\}\) and \(\mathcal P(A)\) be the power set of \(A\text{.}\) Then the subset relation is reflexive and transitive but is not symmetric since \(\{a\} \subseteq \{a, b\}\) but \(\{a, b\} \not\subseteq \{a\}\text{.}\)

###### Example 4.2.18.

Consider the set \(\mathbb Z\) and define \(a \sim b\) if \(5\) divides \(a - b\text{,}\) denoted by \(5 \mid (a - b)\text{;}\) i.e., there is no remainder when \(a - b\) is divided by \(5\text{.}\) Then \(2 \sim 12\text{,}\) since \(5 \mid (2 - 12)\) and \(3 \not\sim 7\text{,}\) since \(5 \not\mid (3 - 7)\text{.}\) We have defined an eqiuivalence relation on \(\mathbb Z\text{.}\) The proof is left as an exercise ((((Unresolved xref, reference "relations-exercise-integers-mod5"; check spelling or use "provisional" attribute))) ).

###### Example 4.2.19.

Consider the set \(\mathbb Z\text{,}\) and let \(n\) be a fixed integer that is not equal to zero. define \(a \sim b\) if \(n \mid (a - b)\text{.}\) The relation is a generalization of Example 4.2.18 and is also an equivalence relation.

###### Example 4.2.20.

Some other equivalence relations are “is the same age as” on the set of all people, “has the same area as” on the set of all rectangles in the Cartesian plane, and “lives on the same street as” on the set of all people living in a given city.

Consider the relation “is the same age as” on the set of all students in a given class. This relation groups the people in the class according to age. Each person in the class is in some group, even if it is a single member group. In addition, no person is in more than one group and all people in a specific group are the same age. These qualities are common to all equivalence relations, leading us to the following formal definition.

###### Definition 4.2.21.

Let \(\sim\) be an equivalence relation on \(A\text{.}\) If \(x \in A\text{,}\) then the equivalence class of \(x\text{,}\) denoted by \(\overline{x}\text{,}\) is defined by \(\overline{x} = \{ y \in A \mid x \sim y \}\text{.}\)

###### Example 4.2.22.

Suppose \(A = \{ 6, 7, 8, 9, 10\} \) and let the relation \(R\) on \(A\) be defined by \(aRb\) if \(a\) and \(b\) have the same remainder when divided by \(2\text{.}\) This relation is an equivalence relation since it is reflexive, symmetric, and transitive. (Verification is left as an exercise.) Then by Definition 4.2.21,

and

Furthermore, \(\overline{6}\) and \(\overline{7}\) are disjoint sets whose union is \(A\text{.}\) So \(A\) has just partitioned into disjoint pieces where each piece can have different names.

The observations for the specific relation considered in Example 4.2.22 lead us to generalize these concepts to any equivalence relation defined on an arbitrary set.

###### Theorem 4.2.23.

Let \(\sim\) be an equivalence relation on \(A\text{.}\) Then:

- Each equivalence class is non-empty.
- Any two equivalence classes are either equal or disjoint
- The set \(A\) is equal to the union of all the equivalence classes.

When given an equivalence relation on a set, we may find the classes generated by that relation by first choosing elements at random from the set. For example, suppose

and let the equivalence relation on be “\(=\text{.}\)” To find the equivalence classes determined by the relation, we may choose any element in \(A\text{,}\) say \(4/6\text{.}\) Then \(4/6 \in \overline{4/6}\text{,}\) since \(4/6 = 4/6\text{.}\) The other elements of \(\overline{4/6}\) are \(2/3\) and \(10/15\text{,}\) since they are the only elements of \(A\) equal to \(4/6\text{.}\) Thus, \(\overline{4/6} = \{ 4/6, 2/3, 10/15 \}\text{.}\) Part (2) of Theorem 4.2.23 implies we might just as easily have chosen \(2/3>\) or \(10/15\text{,}\) and we would have arrived at the same equivalence class. That is, since \(2/3 \in \overline{4/6}\) and \(10/15 \in\overline{4/6}\text{,}\) then \(\overline{2/3} = \overline{4/6} = \overline{10/15}\text{.}\) So we conclude that we may designate an equivalence class completely using any of its elements.

###### TAKS CONNECTION.

How might a student apply the concept of equivalence classes to answer the following question taken from the 2006 Texas Assessment of Knowledge and Skills (TAKS) Grade 5 Mathematics test?

Stan was putting fruit into baskets. He wanted each basket to be more than \(7/10\) full. Which fraction is more than \(7/10\text{?}\)

Which one of the following numbers belongs in the region of the diagram marked by the question mark?

- A. \(4/5\)
- B. \(1/2\)
- C. \(2/3\)
- D. \(3/5\)

###### Example 4.2.24.

Let \(A\) be the set of all ordered pairs of real numbers, and define \((a, b) \sim (c, d)\) if \(a^2 + b^2 = c^2 + d^2)\text{.}\) Before proceeding further, you should find some ordered pairs that are related and then verify that this indeed defines an equivalence relation. Then for any \((x, y) \in \mathbb R \times \mathbb R\text{,}\) we have

These equivalence classes are represented geometrically by circles centered at the origin.

Before leaving this section, we introduce a visual method for representing finite relations. For rather small finite relations, these visual representations, called digraphs, can be very helpful in conceptualizing a relation and its properties.

In general, consider a finite set \(A\) and a relation \(R\) defined on it. Digraphs are constructed by drawing a small dot representing each element of \(A\) and labeling that circle appropriately. These dots are called the vertices of the graph. At each dot, say \(x\text{,}\) draw a directed line segment from it to any other dot, labeled \(y\text{,}\) if and only if \(xRy\text{.}\) These directed line segments are called edges. Then notice that the dots represent \(A\) and the edges represent the ordered pairs in \(R\text{.}\)

###### Example 4.2.25.

Consider the set \(A = \{a, b, c, d \}\)and the relation

Notice that there is an edge representing every ordered pair in \(R\) (Figure 4.2.26). For those elements in \(A\) that are related to themselves, there is an edge that looks like a loop. In this relation there are only two loops since only \(a\) and \(c\) are related to themselves. From this example it is reasonable to conclude that for an arbitrary finite relation \(R\) defined on \(A\text{,}\) the relation will have the reflexive property if and only if each vertex has a loop. Thus, we can quickly see from the digraph that \(R\) is not reflexive. We may also conclude from the digraph that \(R\) is not symmetric and not transitive. Why?

### Exercises 4.2.1 Exercises

###### 1.

Determine whether or not the following relations are reflexive, symmetric, or transitive. Which are equivalence relations on the given sets? Justify your thinking.

- \(R = \{ (1,1), (3,3), (5,5) \}\) on \(A = \{ 1, 3, 5 \}\)
- \(R = \{ (1,1), (2,2), (1,2) \}\) on \(A = \{ 1, 2 \}\)
- \(R = \{ (1,1), (1,2), (2,1) \}\) on \(A = \{ 1, 2 \}\)
- \(R = \{ (1,3), (2,3), (3,2), (3,1) \}\) on \(A = \{ 1, 2, 3 \}\)
- \(R = \{ (1,1), (2,2), (3,3), (4,4), (1,3), (2,4) \}\) on \(A = \{ 1, 2, 3, 4 \}\)
- \(R = \{ (3,4) \}\) on \(A = \{ 3, 4 \}\)
- \(R = \{ (3,3) \}\) on \(A = \{ 3,4 \}\)
- \(R = \{ (1,1), (2,2), (3,3) \}\) on \(A = \{ 1, 2, 3 \}\)
- \(R = \{ (1,1), (2,2), (3,3) \}\) on \(A = \{ 1, 2, 3, 4 \}\)
- \(R = \{ (1,3), (3,1), (1,1), (3,3) \}\) on \(A = \{ 1, 3 \}\)
- \(R = \{ (1,3), (3,1), (1, 1), (3,3) \}\) on \(A = \{ 1, 2, 3 \}\)

###### 2.

Prove the relation described in Example 4.2.18 is an equivalence relation.

###### 3.

Prove the relation described in Example 4.2.19 is an equivalence relation.

###### 4.

Prove the relation described in Example 4.2.22 is an equivalence relation.

###### 5.

Let \(A = \{ 1, 2, 3, 4 \}\text{.}\) For each of the parts below, find an example of a relation on the set that meets the conditions described.

- \(R\) is reflexive and symmetric but not transitive.
- \(R\) is reflexive and transitive but not symmetric.
- \(R\) is symmetric and transitive but not reflexive.
- \(R\) is reflexive but neither symmetric nor transitive.

###### 6.

Define \(\sim\) on \(\mathbb R\) by \(A \sim b\) if and only if \(|a| = |b|\text{.}\) Prove \(\sim\) is an equivalence relation on \(\mathbb R\text{.}\) For an arbitrary \(t \in \mathbb R\text{,}\) find \(\overline{t}\text{.}\)

In Exercise 4.2.1.7–4.2.1.13, a relation \(R\) is defined on a given set. In each case, prove or disprove: (a) \(R\) is reflexive. (b) \(R\) is symmetric, (c) \(R\) is transitive. In each problem where \(R\) is an equivalence relation, find \(\overline{a}\text{,}\) where \(a\) is any element in the set on which the relation is defined.

###### 7.

Define \(R\) on \(\mathbb N\) by \(aRb\) if and only if \(a = 10^kb\) for some \(k \in \mathbb Z\text{.}\)

###### 8.

Define \(R\) on \(\mathbb R\) by \(xRy\) if and only if \(x - y \in \mathbb Z\text{.}\)

###### 9.

Define \(R\) on \(\mathbb N\) by \(xRy\) if and only if \(2 \mid (x + y)\text{.}\)

###### 10.

Define \(R\) on \(\mathbb N\) by \(xRy\) if and only if \(3 \mid (x + y)\text{.}\)

###### 11.

Define \(R\) on \(\mathbb R \times \mathbb R\) by \((a,b)R(c,d)\) if and only if \(a - c \in \mathbb Z\text{.}\)

###### 12.

Define \(R\) on \(\mathbb R \times \mathbb R\) by \((a,b)R(c,d)\) if and only if \(a - c \in \mathbb Z\) and \(b - d \in \mathbb Z\text{.}\)

###### 13.

Define \(R\) on \(\mathbb Z \times \mathbb Z\) by \(R = \{ (a, b) \in \mathbb Z \times \mathbb Z \mid |a - b| \lt 5\}\text{.}\)

###### 14.

Let \(R_1\) and \(R_2\) be relations on \(A\text{.}\)

- If \(R_1\) and \(R_2\) are both reflexive, if \(R_1 \cap R_2\)reflexive? What about \(R_1 \cup R_2\text{?}\) Justify you answers.
- If \(R_1\) and \(R_2\) are both symmetric, if \(R_1 \cap R_2\)reflexive? What about \(R_1 \cup R_2\text{?}\) Justify you answers.
- If \(R_1\) and \(R_2\) are both transitive, if \(R_1 \cap R_2\)reflexive? What about \(R_1 \cup R_2\text{?}\) Justify you answers.

###### 15.

Let \(R\) for a relation on a finite nonempty set \(A\text{.}\) What can be said about the digraph of \(R\) if the relation is

- reflexive?
- not reflexive?
- symmetric?
- not symmetric?
- transitive?
- not transitive?

Jusitify your claim for each part.

###### 16.

Let \(A = \{ 1, 2, 3, 4, 5 \}\) and \(R = \{ (2, 3), (2, 4), (3, 5), (2, 5), (5, 5) \}\text{.}\)

- Draw a digraph of this relation.
- Determine the properties of \(R\text{,}\) explaining in each case how you can tell from your digraph.

###### 17.

Draw a digraph of the relation \(\lt\) on the set \(A = \{ 1, 2, 3, 4 \}\)

###### 18.

Draw a digraph of the relation \(\leq\) on the set \(A = \{ 1, 2, 3, 4 \}\)

###### 19.

Draw a digraph of \(\mathcal P(S)\) under the relation \(\subseteq\text{,}\) where \(S = \{ a,b \}\)