Loading [MathJax]/jax/output/HTML-CSS/jax.js
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}\,}\)

As we have seen in the previous section, the notions of reflexive, symmetric, and transitive are independent of each other. That is, a relation may have some combination of these properties, possibly none of them and possibly all of them. However, we have a special name for when a relation satisfies all three properties.

Definition 7.35. Let be a relation on a set A. Then is called an equivalence relation on A if is reflexive, symmetric, and transitive.

The symbol “" is usually pronounced as “twiddle" or “tilde" and the phrase “ab" could be read as “a is related to b" or “a twiddles b".

Problem 7.36. Let A={1,2,3,4,5,6} and define R={(1,1),(1,6),(2,2),(2,3),(2,4),(3,3),(3,2),(3,4),(4,4),(4,2),(4,3),(5,5),(6,6),(6,1)}. Using R, complete each of the following.

  1. Draw the digraph for R.
  2. Determine whether R is an equivalence relation on A.
  3. Find Rel(R) by determining rel(x) for each xA.

Problem 7.37. Let A={a,b,c,d,e}.

  1. Make up an equivalence relation on A by drawing a digraph such that a is not related to b and c is not related to b.
  2. Using your digraph, find Rel() by determining rel(x) for each xA.

Problem 7.38. Given a finite set A and an equivalence relation on A, describe what the corresponding digraph would have to look like.

Problem 7.39. Determine which relations given in Problem 7.34 are equivalence relations.

Problem 7.40. Let T be the set of all triangles and define on T via T1T2 if T1 is similar to T2. Determine whether is an equivalence relation on T.

Problem 7.41. If possible, construct an equivalence relation on the empty set. If this is not possible, explain why.

Theorem 7.42. Suppose is an equivalence relation on a set A and let a,bA. Then rel(a)=rel(b) if and only if ab.

Theorem 7.43. Suppose is an equivalence relation on a set A. Then

  1. aA rel(a)=A, and
  2. [thm:equiv yields partition b] For all a,bA, either rel(a)=rel(b) or rel(a)rel(b)=.

In light of Theorem 7.43, we have the following definition.

Definition 7.44. If is an equivalence relation on a set A, then for each aA, we refer to rel(a) as the equivalence class of a.

When is an equivalence relation on a set A, it is common to write each equivalence class rel(a) as [a] (or sometimes ¯a). The element a inside the square brackets is called the representative of the equivalence class [a]. Theorem 7.42 implies that an equivalence class can be represented by any element of the equivalence class. For example, in Problem 7.36, we have [1]=[6] since 1 and 6 are in the same equivalence class. The collection of equivalence classes Rel() is often denoted by A/, which is read as “A modulo " or “A mod ". The collection A/ is sometimes referred to as the quotient of A by .

Example 7.45. Let P denote the residents of a particular town and define on P via ab if a and b have the same last name. It is easily seen that this relation is reflexive, symmetric, and transitive, and hence is an equivalence relation on P. The equivalence classes correspond to collections of individuals with the same last name. For example, Maria Garcia, Anthony Garcia, and Ariana Garcia all belong to the same equivalence class. Any Garcia can be used as a representative for the corresponding equivalence class, so we can denote it as [Maria Garcia], for example. The collection P/ consists of the various sets of people with the same last name. In particular, [Maria Garcia]P/.

Example 7.46. The five distinct sets of relatives that you identified in Problem 7.22 are the equivalence classes for 5 on Z. These equivalence classes are often called the congruence classes modulo 5.

The upshot of Theorem 7.43 is that given an equivalence relation, every element lives in exactly one equivalence class. In the next section, we will see that we can run this in reverse. That is, if we separate out the elements of a set so that every element is an element of exactly one subset, then this determines an equivalence relation.

Problem 7.47. If is an equivalence relation on a finite set A, describe A/ in terms of the digraph corresponding to .

Problem 7.48. For each of the equivalence relations you identified in Problem 7.39, succinctly describe the corresponding equivalence classes.

Problem 7.49. Suppose R and S are both equivalence relations on a set A. Is RS an equivalence relation on A? If so, prove it. Otherwise, provide a counterexample.

Problem 7.50. Suppose R and S are both equivalence relations on a set A. Is RS an equivalence relation on A? If so, prove it. Otherwise, provide a counterexample.


This page titled 7.2: Equivalence Relations is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Dana Ernst via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?