Processing math: 86%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

7.2: Equivalence Relations

( \newcommand{\kernel}{\mathrm{null}\,}\)

Preview Activity 7.2.1: Properties of Relations

In previous mathematics courses, we have worked with the equality relation. For example, let R be the relation on Z defined as follows: For all a,bZ, a R b if and only if a=b. We know this equality relation on Z has the following properties:

  • For each aZ, a=b and so a R a.
  • For all a,bZ, if a=b, then b=a. That is, if a R b, then b R a.
  • For all a,b,cZ, if a=b and b=c, then a=c. That is, if a R b and b R c, then a R c.

In mathematics, when something satisfies certain properties, we often ask if other things satisfy the same properties. Before investigating this, we will give names to these properties.

Definition

Let A be nonempty set and let R be a relation on A.

  • The relation R is reflexive on A provided that for each xA, x R x or, equivalently, (x,x)R.
  • The relation R is symmetric provided that for every x,yA, if x R y, then y R x or, equivalently, for every x,yA, if (x,y)R, then (y,x)R.
  • The relation R is transitive provided that for every x,y,zA, if x R y and y R z, then x R z or, equivalently, for every x,y,zA, if (x,y)R and (y,z)R, then (x,z)R.

Before exploring examples, for each of these properties, it is a good idea to understand what it means to say that a relation does not satisfy the property. So let A be a nonempty set and let R be a relation on A.

  1. Carefully explain what it means to say that the relation R is not reflexive on the set A.
  2. Carefully explain what it means to say that the relation R is not symmetric.
  3. Carefully explain what it means to say that the relation R is not transitive.
    To illustrate these properties, we let A={1,2,3,4} and define the relations R and T on A as follows:
    R={(1,1),(2,2),(3,3),(4,4),(1,3),(3,2)}T={(1,1),(1,4),(2,4),(4,1),(4,2)}
  4. Draw a directed graph for the relation R. Then explain why the relation R is reflexive on A, is not symmetric, and is not transitive.
  5. Draw a directed graph for the relation T. Is the relation T reflexive on A? Is the relation T symmetric? Is the relation T transitive? Explain.
Preview Activity 7.2.2: Review of Congruence Modulo n
  1. Let a,bZ and let nN. On page 92 of Section 3.1, we defined what it means to say that a is congruent to b modulo n. Write this definition and state two different conditions that are equivalent to the definition.
  2. Explain why congruence modulo n is a relation on Z.
  3. Carefully review Theorem 3.30 and the proofs given on page 148 of Section 3.5. In terms of the properties of relations introduced in Preview Activity 7.2.1, what does this theorem say about the relation of congruence modulo non the integers?
  4. Write a complete statement of Theorem 3.31 on page 150 and Corollary 3.32.
  5. Write a proof of the symmetric property for congruence modulo n. That is, prove the following:

Let a,bZ and let nN. If ab (mod n), then ba (mod n).

Directed Graphs and Properties of Relations

In Section 7.1, we used directed graphs, or digraphs, to represent relations on finite sets. Three properties of relations were introduced in Preview Activity 7.2.1 and will be repeated in the following descriptions of how these properties can be visualized on a directed graph.

Let A be a nonempty set and let R be a relation on A.

  • The relation R is reflexive on A provided that for each xA, x R x or, equivalently, .(x,x)R. This means that if a reflexive relation is represented on a digraph, there would have to be a loop at each vertex, as is shown in the following figure.

屏幕快照 2019-04-05 下午3.26.30.png

  • The relation R is symmetric provided that for every x,yA, if x R y, then y R x or, equivalently, for every x,yA, if (x,y)R, then (y,x)R.

    This means that if a symmetric relation is represented on a digraph, then anytime there is a directed edge from one vertex to a second vertex, there would be a directed edge from the second vertex to the first vertex, as is shown in the following figure.

屏幕快照 2019-04-05 下午3.28.25.png

  • The relation R is transitive provided that for every x,y,zA, if x R y and y R z, then x R z or, equivalently, for every x,y,zA, if (x,y)R and (y,z)R, then (x,z)R. So if a transitive relation is represented by a digraph, then anytime there is a directed edge from a vertex x to a vertex y and a directed edge from y to a vertex z, there would be a directed edge from x to z.

    In addition, if a transitive relation is represented by a digraph, then anytime there is a directed edge from a vertex x to a vertex y and a directed edge from y to the vertex x, there would be loops at x and y. These two situations are illustrated as follows:

屏幕快照 2019-04-05 下午3.32.52.png

Progress Check 7.7: Properties of Relations

Let A={a,b,c,d} and let R be the following relation on A:

R={(a,a),(b,b),(a,c),(c,a),(b,d),(d,b)}.

Draw a directed graph for the relation R and then determine if the relation R is reflexive on A, if the relation R is symmetric, and if the relation R is transitive.

Answer

Add texts here. Do not delete this text first.

Definition of an Equivalence Relation

In mathematics, as in real life, it is often convenient to think of two different things as being essentially the same. For example, when you go to a store to buy a cold soft drink, the cans of soft drinks in the cooler are often sorted by brand and type of soft drink. The Coca Colas are grouped together, the Pepsi Colas are grouped together, the Dr. Peppers are grouped together, and so on. When we choose a particular can of one type of soft drink, we are assuming that all the cans are essentially the same. Even though the specific cans of one type of soft drink are physically different, it makes no difference which can we choose. In doing this, we are saying that the cans of one type of soft drink are equivalent, and we are using the mathematical notion of an equivalence relation.

An equivalence relation on a set is a relation with a certain combination of properties that allow us to sort the elements of the set into certain classes. In this section, we will focus on the properties that define an equivalence relation, and in the next section, we will see how these properties allow us to sort or partition the elements of the set into certain classes.

Definition: equivalence relation

Let A be a nonempty set. A relation on the set A is an equivalence relation provided that is reflexive, symmetric, and transitive. For a,bA, if is an equivalence relation on A and a b, we say that a is equivalent to b.

Most of the examples we have studied so far have involved a relation on a small finite set. For these examples, it was convenient to use a directed graph to represent the relation. It is now time to look at some other type of examples, which may prove to be more interesting. In these examples, keep in mind that there is a subtle difference between the reflexive property and the other two properties. The reflexive property states that some ordered pairs actually belong to the relation R, or some elements of A are related. The reflexive property has a universal quantifier and, hence, we must prove that for all xA, x R x. Symmetry and transitivity, on the other hand, are defined by conditional sentences. We often use a direct proof for these properties, and so we start by assuming the hypothesis and then showing that the conclusion must follow from the hypothesis.

Example 7.8: A Relation that Is Not an Equivalence Relation

Let M be the relation on Z defined as follows:

For a,bZ, a M b if and only if a is a multiple of b.

So a M b if and only if there exists a kZ such that a=bk.

  • The relation M is reflexive on Z since for each xZ, x=x1 and, hence, x M x.
  • Notice that 4 M 2, but 屏幕快照 2019-04-05 下午3.45.34.png So there exist integers x and y such that x M y but 屏幕快照 2019-04-05 下午3.46.17.png Hence, the relation M is not symmetric.
  • Now assume that x M y and y M z. Then there exist integers p and q such that
    x=yp and y=zq.
    Using the second equation to make a substitution in the first equation, we see that x=z(pq). Since pqZ, we have shown that x is a multiple of z and hence x M z. Therefore, M is a transitive relation.

The relation M is reflexive on Z and is transitive, but since M is not symmetric, it is not an equivalence relation on Z.

Solution

Add text here.

Progress check 7.9 (a relation that is an equivalence relation)

Define the relation on Q as follows: For all a,bQ, a b if and only if abZ. For example:

  • 34 74 since 3474=1 and 1Z.
  • 3412 since 3412=14 and 14Z.

To prove that is reflexive on Q, we note that for all qQ, aa=0. Since 0Z, we conclude that a a. Now prove that the relation is symmetric and transitive, and hence, that is an equivalence relation on Q.

Answer

Add texts here. Do not delete this text first.

Congruence Modulo n

One of the important equivalence relations we will study in detail is that of congruence modulo n. We reviewed this relation in Preview Activity 7.2.2.

Theorem 3.30 tells us that congruence modulo n is an equivalence relation on Z. Recall that by the Division Algorithm, if aZ, then there exist unique integers q and r such that

a=nq+r and 0r<n.

Theorem 3.31 and Corollary 3.32 then tell us that ar (mod n). That is, a is congruent modulo n to its remainder r when it is divided by n. When we use the term “remainder” in this context, we always mean the remainder r with 0r<n that is guaranteed by the Division Algorithm. We can use this idea to prove the following theorem.

Theorem 7.10

Let nN and let a,bZ. Then ab (mod n) if and only if a and b have the same remainder when divided by n.

Proof

Let nN and let a,bZ. We will first prove that if a and b have the same remainder when divided by n, then ab (mod n). So assume that a and bhave the same remainder when divided by n, and let r be this common remainder. Then, by Theorem 3.31,

ar (mod n) and br (mod n).

Since congruence modulo n is an equivalence relation, it is a symmetric relation. Hence, since br (mod n), we can conclude that rb (mod n). Combining this with the fact that ar (mod n), we now have

ar (mod n) and rb (mod n)

We can now use the transitive property to conclude that ab (mod n). This proves that if a and b have the same remainder when divided by n, then ab (mod n).

We will now prove that if ab (mod n), then a and b have the same remainder when divided by n. Assume that ab (mod n), and let r be the least nonnegative remainder when b is divided by n. Then 0r<n and, by Theorem 3.31,

br (mod n).

Now, using the facts that ab (mod n) and br (mod n), we can use the transitive property to conclude that

ar (mod n)

This means that there exists an integer q such that ar=nq or that

a=nq+r.

Since we already know that 0r<n, the last equation tells us that r is the least nonnegative remainder when a is divided by n. Hence we have proven that if ab (mod n), then a and b have the same remainder when divided by n.

Examples of Other Equivalence Relations
  1. The relation on Q from Progress Check 7.9 is an equivalence relation.
  2. Let A be a nonempty set. The equality relation on A is an equivalence relation. This relation is also called the identity relation on A and is denoted by IA, where
    IA={(x,x) | xA}.
  3. Define the relation on R as follows:
    For a,bR, a b if and only if there exists an integer k such that ab=2kπ.

    We will prove that the relation ~ is an equivalence relation on R. The relation is reflexive on R since for each aR, aa=0=20π.
    Now, let a,bR and assume that a b. We will prove that b a. Since a b, there exists an integer k such that
    ab=2kπ.
    By multiplying both side of this equation by -1, we obtain
    (1)(ab)=(1)(2kπ)ba=2(k)π.
    Since kZ, the last equation proves that b a. Hence, we have proven that if a b, then b a and, therefore, the relation is symmetric.

    To prove transitivity, let a,b,cR and assume that a b and b c. We will prove that a c. Now, there exist integers k and n such that
    ab=2kπ and bc=2nπ.
    By adding the corresponding sides of these two equations, we see that
    (ab)+(bc)=2kπ+2nπac=2(k+n)π.

    By the closure properties of the integers, k+nZ. So this proves that a c and, hence the relation is transitive.

    We have now proven that is an equivalence relation on R. This equivalence relation is important in trigonometry. If ab, then there exists an integer k such that ab=2kπ and, hence, a=b+k(2π). Since the sine and cosine functions are periodic with a period of 2π, we see that

    sin a=sin(b+k(2π))=sin b, and cos a=cos(b+k(2π))=cos b.
    Therefore, when ab, each of the trigonometric functions have the same value at a and b.
  4. For an example from Euclidean geometry, we define a relation P on the set L of all lines in the plane as follows:

    Forl1,l2L, l1 P l2 if and only if l1 is parallel to l2 or l1=l2.

    We added the second condition to the definition of P to ensure that P is reflexive on L. Theorems from Euclidean geometry tell us that if l1 is parallel to l2, then l2 is parallel to l1, and if l1 is parallel to l2 and l2 is parallel to l3, then l1 is parallel to l3. (Drawing pictures will help visualize these properties.) This tells us that the relation P is reflexive, symmetric, and transitive and, hence, an equivalence relation on L.

Progress Check 7.11: Another Equivalence Relation

Let U be a finite, nonempty set and let P(U) be the power set of U. Recall that P(U) consists of all subsets of U. (See page 222.) Define the relation on P(U) as follows:

For A,BP(U), AB if and only if card(A) = card(B).

For the definition of the cardinality of a finite set, see page 223. This relation states that two subsets of U are equivalent provided that they have the same number of elements. Prove that is an equivalence relation on

Answer

Add texts here. Do not delete this text first.

Exercise 7.2
  1. Let A={a,b} and let R={(a,b)}. Is R an equivalence relation on A? If not, is R reflexive, symmetric, or transitive? Justify all conclusions.
  2. Let A={a,b,c}. For each of the following, draw a directed graph that represents a relation with the specified properties.

    (a) A relation on A that is symmetric but not transitive
    (b) A relation on A that is transitive but not symmetric
    (c) A relation on A that is symmetric and transitive but not reflexive on A
    (d) A relation on A that is not reflexive on A, is not symmetric, and is not transitive
    (e) A relation on A, other than the identity relation, that is an equivalence relation on A
  3. Let A={1,2,3,4,5}. The identity relation on A is
    IA={(1,1),(2,2),(3,3),(4,4),(5,5)}.
    Determine an equivalence relation on A that is different from IA or explain why this is not possible.
  4. Let R={(x,y)R×R | |x|+|y|=4}. Then R is a relation on R. Is R an equivalence relation on R? If not, is R reflexive, symmetric, or transitive? Justify all conclusions.
  5. A relation R is defined on Z as follows: For all a,b in Z, a R b if and only if |ab|3. Is R an equivalence relation on R? If not, is R reflexive, symmetric, or transitive. Justify all conclusions.
  6. Let f:RR be defined by f(x)=x24 for each xR. Define a relation on R as follows:
    For a,bR, ab if and only if f(a)=f(b).
    (a) Is the relation an equivalence relation on R?Justify your conclusion.
    (b) Determine all real numbers in the set C={xR | x5}.
  7. Repeat Exercise (6) using the function f:RR that is defined by f(x)=x23x7 for each xR.
  8. (a) Repeat Exercise (6a) using the function f:RR that is defined by f(x)=sin x for each xR.
    (b) Determine all real numbers in the set C={xR | xπ}.
  9. Define the relation on Q as follows: For a,bQ, ab if and only if abZ. In progress Check 7.9, we showed that the relation is a equivalence relation on Q.

    (a) List four different elements of the set C={xQ | x57}.
    (b) Use set builder notation (without using the symbol sim) to specify the set C.
    (c) Use the roster method to specify the set C.
  10. Let and be relation on Z defined as follows:

    For a,bZ, ab if and only if 2 divides a+b.
    For a,bZ, ab if and only if 3 divides a+b.

    (a) Is an equivalence relation on Z? If not, is this relation reflexive, symmetric, or transitive?
    (b)Is an equivalence relation on Z? If not, is this relation reflexive, symmetric, or transitive?
  11. Let U be a finite, nonempty set and let P(U) be the power set of U. That is, P(U) is the set of all subsets of U. Define the relation on P(U) as follows: For A,BP(U), AB if and only if AB=. That is, the ordered pair (A,B) is in the relaiton if and only if A and B are disjoint.
    Is the relation an equivalence relation on P(U)? If not, is it reflexive, symmetric, or transitive? Justify all conclusions.
  12. Let U be a nonempty set and let P(U) be the power set of U. That is, P(U) is the set of all subsets of U.
    For A and B in P(U), define AB to mean that there exists a bijection f:AB. Prove that is an equivalence relation on P(U).
    Hint: Use results from Sections 6.4 and 6.5.
  13. Let and be relation on Z defined as follows:

    For a,bZ, ab if and only if 2a+3b0 (mod 5).
    For a,bZ, ab if and only if a+3b0 (mod 5).

    (a) Is an equivalence relation on \mathbb{Z}? If not, is this relation reflexive, symmetric, or transitive?
    (b)Is \approx an equivalence relation on \mathbb{Z}? If not, is this relation reflexive, symmetric, or transitive?
  14. Let \sim and \approx be relation on \mathbb{R} defined as follows:

    \bullet For a, b \in Z, a \sim b if and only if xy \ge 0.
    \bullet For a, b \in Z, a \approx b if and only if xy \le 0.

    (a) Is \sim an equivalence relation on \mathbb{R}? If not, is this relation reflexive, symmetric, or transitive?
    (b)Is \approx an equivalence relation on \mathbb{R}? If not, is this relation reflexive, symmetric, or transitive?
  15. Define the relation \approx on \mathbb{R} \times \mathbb{R} as follows: For (a, b), (c, d) \in \mathbb{R} \times \mathbb{R}, (a, b) \approx (c, d) if and only if a^2 + b^2 = c^2 + d^2.

    (a) Prove that \approx is an equivalence relation on \mathbb{R} \times \mathbb{R}.
    (b) List four different elements of the set
    C = \{(x, y) \in \mathbb{R} \times \mathbb{R}\ |\ (x, y) \approx (4, 3)\}.
    (c) Give a geometric description of set C.
  16. Evaluation of proofs
    See the instructions for Exercise (19) on page 100 from Section 3.1.
    (a)

    Proposition. Let R be a relation on a set A. If R is symmetric and transitive, then R is reflexive.

    Proof

    Let x, y \in A. If x\ R\ y, then y\ R\ x since R is symmetric. Now, x\ R\ y and y\ R\ x, and since R is transitive, we can conclude that x\ R\ x. Therefore, R is reflexive.

    (b)

    Proposition. Let \sim be a relation on \mathbb{Z} where for all a, b \in \mathbb{Z}, a \sim b if and only if (a + 2b) \equiv 0 (mod 3). The relation \sim is an equivalence relation on \mathbb{Z}.

    Proof

    Assume a \sim a. Then (a + 2a) \equiv 0 (mod 3) since (3a) \equiv 0 (mod 3). Therefore, \sim is reflexive on \mathbb{Z}. In addition, if a \sim b, then (a + 2b) \equiv 0 (mod 3), and if we multiply both sides of this congruence by 2, we get

    \begin{array} {rcl} {2(a + 2b)} &\equiv & {2 \cdot 0 \text{ (mod 3)}} \\ {(2a + 4b)} &\equiv & {0 \text{ (mod 3)}} \\ {(a + 2b)} &\equiv & {0 \text{ (mod 3)}} \\ {(b + 2a)} &\equiv & {0 \text{ (mod 3)}.} \end{array}

    This means that b\ \sim\ a and hence, \sim is symmetric.

    We now assume that (a + 2b) \equiv 0 (mod 3) and (b + 2c) \equiv 0 (mod 3).

    By adding the corresponding sides of these two congruences, we obtain

    \begin{array} {rcl} {(a + 2b) + (b + 2c)} &\equiv & {0 + 0 \text{ (mod 3)}} \\ {(a + 3b + 2c)} &\equiv & {0 \text{ (mod 3)}} \\ {(a + 2c)} &\equiv & {0 \text{ (mod 3)}.} \end{array}

    Hence, the relation \sim is transitive and we have proved that \sim is an equivalence relation on \mathbb{Z}.

Explorations and Activities

17. Other Types of Relations. In this section, we focused on the properties of a relation that are part of the definition of an equivalence relation. However, there are other properties of relations that are of importance. We will study two of these properties in this activity.

A relation R on a set A is a circular relation provided that for all x, y, and z in A, if x\ R\ y and y\ R\ z, then z\ R\ x.

(a) Carefully explain what it means to say that a relation R on a set A is not circular.

(b) Let A = \{1, 2, 3\}. Draw a directed graph of a relation on A that is circular and draw a directed graph of a relation on A that is not circular.
(c) Let A = \{1, 2, 3\}. Draw a directed graph of a relation on A that is circular and not transitive and draw a directed graph of a relation on A that is transitive and not circular.

(d) Prove the following proposition:
A relation R on a set A is an equivalence relation if and only if it is reflexive and circular.

A relation R on a set A is an antisymmetric relation provided that for all x, y \in A, if x\ R\ y and y\ R\ x, then x = y.

(e) Carefully explain what it means to say that a relation on a set A is not antisymmetric.

(f) Let A = \{1, 2, 3\}. Draw a directed graph of a relation on A that is antisymmetric and draw a directed graph of a relation on A that is not antisymmetric.

(g)Are the following propositions true or false? Justify all conclusions.

  • If a relation R on a set A is both symmetric and antisymmetric, then R is transitive.
  • If a relation R on a set A is both symmetric and antisymmetric, then R is reflexive.
Answer

Add texts here. Do not delete this text first.


This page titled 7.2: Equivalence Relations is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Ted Sundstrom (ScholarWorks @Grand Valley State University) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?