Let $$\sim$$ be an equivalence relation on a nonempty set $$A$$. Consequences of these properties will be explored in the exercises. But by definition of , all we need to show is --which is clear since both sides are . In a similar manner, if we use congruence modulo 2, we simply divide the integers into two classes. In any case, always remember that when we are working with any equivalence relation on a set A if $$a \in A$$, then the equivalence class [$$a$$] is a subset of $$A$$. In Exercise (6) of Section 7.2, we proved that $$\sim$$ is an equivalence relation on $$\mathbb{R}$$. \end{array}\], The main results that we want to use now are Theorem 3.31 and Corollary 3.32 on page 150. that . For each $$a, b \in \mathbb{Z}$$, $$a \equiv b$$ (mod $$n$$) if and only if $$[a] = [b]$$. PREVIEW ACTIVITY $$\PageIndex{1}$$: Sets Associated with a Relation. consists of exactly the elements , , \ldots, . Two elements of $$A$$ are equivalent if and only if their equivalence classes are equal. The results of Theorem 7.14 are consistent with all the equivalence relations studied in the preview activities and in the progress checks. Question 1: Let assume that F is a relation on the set R real numbers defined by xFy if and only if x-y is an integer. Let $$A = \mathbb{Z} \times (\mathbb{Z} - \{0\})$$. The set of rational numbers is . E.g. Proof. Notice that the quotient of by an equivalence relation is a set of sets of elements of . An equivalence relation ~ on a set S is a rule or test applicable to pairs of elements ... notion of equality among the set of integers is an example of an equivalence relation. Technically, each pair of distinct subsets in the collection must be disjoint. Every element of $$A$$ is in its own equivalence class. For each $$a \in \mathbb{Z}$$, let $$[a]$$ represent the congruence class of $$a$$ modulo $$n$$. (See Exercise (13) in Section 7.2). We should note, however, that the sets $$S[y]$$ were not equal and were not disjoint. We will illustrate this with congruence modulo 3. Equivalence Classes • “In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation) defined on them, then one may naturally split the set S into equivalence classes. Claim. $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$, [ "article:topic", "license:ccbyncsa", "showtoc:no", "authorname:tsundstrom2", "Equivalence Classes", "Congruence Classes" ], https://math.libretexts.org/@app/auth/2/login?returnto=https%3A%2F%2Fmath.libretexts.org%2FBookshelves%2FMathematical_Logic_and_Proof%2FBook%253A_Mathematical_Reasoning__Writing_and_Proof_(Sundstrom)%2F7%253A_Equivalence_Relations%2F7.3%253A_Equivalence_Classes, $$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$, ScholarWorks @Grand Valley State University, Congruence Modulo $$n$$ and Congruence Classes, $$C$$ consisting of all integers with a remainder of 0 when divided by 3, $$C$$ consisting of all integers with a remainder of 1 when divided by 3, $$C$$ consisting of all integers with a remainder of 2 when divided by 3. iff . Let $$A = \{a, b, c, d, e\}$$ and let $$\sim$$ be the relation on $$A$$ that is represented by the directed graph in Figure 7.4. We often use something like $$[a]_{\sim}$$, or if $$R$$ is the name of the relation, we can use $$R[a]$$ or $$[a]_R$$ for the equivalence class of a determined by $$R$$. Exercise. Congruence and Congruence Classes Definition 11.1. Proof. Let be a set and be an equivalence relation on . One class will consist of all the integers that have a remainder of 0 when divided by 2, and the other class will consist of all the integers that have a remainder of 1 when divided by 2. Consider an equivalence class consisting of $$m$$ elements. Definition. But as we have seen, there are really only three distinct equivalence classes. Then . Let $$\sim$$ be an equivalence relation on the nonempty set $$A$$, and let $$\mathcal{C}$$ be the collection of all equivalence classes determined by $$\sim$$. is the set of all pairs of the form . In Progress Check 7.9 of Section 7.2, we showed that the relation $$\sim$$ is an equivalence relation on $$\mathbb{Q}$$. For example, in Preview Activity $$\PageIndex{2}$$, we used the equivalence relation of congruence modulo 3 on $$\mathbb{Z}$$ to construct the following three sets: \[\begin{array} {rcl} {C} &= & {\{a \in \mathbb{Z}\ |\ a \equiv 0\text{ (mod 3)}\},} \\ {C} &= & {\{a \in \mathbb{Z}\ |\ a \equiv 1\text{ (mod 3)}\},\text{ and}} \\ {C} &= & {\{a \in \mathbb{Z}\ |\ a \equiv 2\text{ (mod 3)}\}.} Since an integer $$a$$ is congruent to 0 modulo 3 if an only if 3 divides $$a$$, we can use the roster method to specify this set as follows: $$C = \{..., -9, -6, -3, 0, 3, 6, 9, ...\}.$$. What are the equivalence classes for your example? So for $$a \in \mathbb{Z}$$, $$[a] = \{x \in \mathbb{Z}\ |\ x \equiv a \text{ (mod \(n$$)}\}.\). The definition of equivalence classes is given and several properties of equivalence classes are introduced. This proves that $$[a] \subseteq [b]$$. (sometimes, it is denoted a ≡ b ) The equivalence class of a is { b | a ~ b }, denoted [a]. Consider the relation on given by if . Then and certainly overlap--they both contain , for example. $$c\ S\ d$$ $$d\ S\ c$$. Have questions or comments? This theorem shows, for example, that there are in no redundancies on the list , , \ldots, of equivalence classes modulo . Let a;b2A. As we will see in this section, the relationships between these sets is typical for an equivalence relation. Without using the terminology at that time, we actually determined the equivalence classes of the equivalence relation $$R$$ in Preview Activity $$\PageIndex{1}$$. Let $$\mathbb{Z}_9 = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}$$. That is, congruence modulo 2 simply divides the integers into the even and odd integers. Also assume that it is known that. the equivalence classes of R form a partition of the set S. More interesting is the fact that the converse of this statement is true. Prove each of the following. A relation R tells for any two members, say x and y, of S whether x is in that relation to y. Equivalent Class Partitioning is very simple and is a very basic way to perform testing - you divide the test data into the group and then has a representative for each group. 5. The objective is to determine the relation R. $$[a] \cap [b] = \emptyset$$ or $$[a] \cap [b] \ne \emptyset$$. Which of the sets $$S[a]$$, $$S[b]$$, $$S[c]$$, $$S[d]$$, and $$S[e]$$ are equal? The following table restates the properties in Theorem 7.14 and gives a verbal description of each one. The second part of this theorem is a biconditional statement. For each $$a \in A$$, the equivalence class of $$a$$ determined by $$\sim$$ is the subset of $$A$$, denoted by [$$a$$], consisting of all the elements of $$A$$ that are equivalent to $$a$$. If you've ever served in the military or listened to the BBC World Service, you're familiar with arithmetic modulo 24 as well. EXAMPLE 29. Let R be the equivalence relation on A × A defined by (a, b)R(c, d) iff a + d = b + c . The following definition makes this idea precise. Since is transitive, we have . Hence, Corollary 7.16 gives us the following result. Let . We will see that, in a similar manner, if $$n$$ is any natural number, then the relation of congruence modulo $$n$$ can be used to sort the integers into $$n$$ classes. Find the distinct equivalence classes of {eq}R {/eq} . We then say that the collection of subsets is pairwise disjoint. Hence 1 and 3 must be in different equivalence classes. That is, $$A = \{(a, b) \in \mathbb{Z} \times \mathbb{Z}\ |\ b \ne 0\}$$. Also, see Exercise (9) in Section 7.2. For any a A we define the equivalence class of a, written [a], by [a] = { x A : x R a}. This means that $$x \in [a]$$ and $$x \in [b]$$. Hence by the definition of $$[b]$$, we conclude that $$a \sim b$$. Transcript. For each $$a, b \in A$$, $$[a] = [b]$$ or $$[a] \cap [b] = \emptyset$$. You've actually dealt with modular arithmetic for most of your life: the clock face represents arithmetic with modulus 12. Now, to gure out the equivalence classes, let’s think about the four possibilities for an integer: it can be congruent to 0, 1, 2, or 3 modulo 4. To see why for example C 1 is an equivalence class, notice that 1 − 5 = 4 and 1 − 9 = 8 are divisible by 4, so 1 is equivalent to 5 and 9 with respect to R. However, 1 is not equivalent to for example 3, because 1 − 3 = 2 is not divisible by 4. Determine the equivalence classes of 5, -5, 10, -10, $$\pi$$, and $$-\pi$$. $$a\ R\ e$$ $$e\ R\ a$$ $$c\ R\ d$$ $$d\ R\ c$$. Then: Let $$A = \{a, b, c, d\}$$, and let $$S$$ be the relation on the set $$A$$ defined as follows: $$b\ S\ b$$ $$c\ S\ c$$ $$d\ S\ d$$ $$e\ S\ e$$ Definition. In the above example, for instance, the class of 0, , may We also acknowledge previous National Science Foundation support under grant numbers 1246120, 1525057, and 1413739. Exercise. Do not delete this text first. We introduce the following formal definition. It is very useful to have a symbol for all of the one-o'clocks, a symbol for all of the two-o'clocks, etc., so that we can write things like. Theorem 7.1.15. Let $$f: \mathbb{R} \to \mathbb{R}$$ be defined by $$f(x) = x^2 - 4$$ for each $$x \in \mathbb{R}$$. To get the other set inclusion, suppose is an equivalence class. Proof. In Preview Activity $$\PageIndex{2}$$, we used the notation $$C[k]$$ for the set of all integers that are congruent to $$k$$ modulo 3. It is of course enormously important, but is not a very interesting example, since no two distinct objects are related by equality. What are the equivalence classes under the relation ? If we apply the lemma to this example, it states simply that if two coins are equivalent (that is, have the same value), they are in the same pile. For each $$y \in A$$, define the subset $$R[y]$$ of $$A$$ as follows: That is, $$R[y]$$ consists of those elements in $$A$$ such that $$x\ R\ y$$. of all elements of which are equivalent to . Consequently, $$\mathcal{C}$$, the collection of all equivalence classes determined by $$\sim$$, satisfies the first two conditions of the definition of a partition. If is the equivalence relation on given by if , then is the set of circles centered at the origin. So we assume that $$[a] \cap [b] \ne \emptyset$$; and will show that $$[a] = [b]$$. We will prove it by proving two conditional statements. We are asked to show set equality. The proof is found in your book, but I reproduce it here. Since Ris re exive, we know aRa. This means that we can conclude that if $$a \sim b$$, then $$[a] = [b]$$. For more information contact us at info@libretexts.org or check out our status page at https://status.libretexts.org. }\) This is not a coincidence! of distinct equivalence classes of $$P(A)$$ under $$\sim$$ is a partition of $$P(A)\text{. This is done by means of certain subsets of \(A$$ that are associated with the elements of the set $$A$$. This means that if two equivalence classes are not disjoint then they must be equal. Consider the set .. R is an equivalence relation on A such that the three distinct equivalence classes are and .. The equivalence class of under the equivalence is the set. In terms of the equivalence classes, this means that each equivalence class is nonempty since each element of $$A$$ is in its own equivalence class. Let $$A = \{0, 1, 2, 3, ..., 999, 1000\}$$. Define the relation $$R$$ on $$A$$ as follws: Determine all of the congruence classes for the relation of congruence modulo 5 on the set of integers. So if we take equivalence classes do not overlap" too literally it cannot be true. equivalence classes. Give an example of an equivalence relation R on the set A = { v, w, x, y, z } such that there are exactly three distinct equivalence classes. For each $$V \in \mathcal{C}$$, $$V \ne \emptyset$$. There is a movie for Movie Theater which has rate 18+. Because of the importance of this equivalence relation, these results for congruence modulo n are given in the following corollary. Do not use fractions in your proof. This proves that $$y \in [a]$$ and, hence, that $$[b] \subseteq [a]$$. . Proof. This means that $$y \sim b$$, and hence by the symmetric property, that $$b \sim y$$. The relation $$R$$ is symmetric and transitive. Thus , and since , we have shown that is on our list of equivalence classes. For example 1. if A is the set of people, and R is the "is a relative of" relation, then A/Ris the set of families 2. if A is the set of hash tables, and R is the "has the same entries as" relation, then A/Ris the set of functions with a finite d… In addition, we see that $$S[a] = \emptyset$$ since there is no x 2 A such that.x;a/ 2 S. 6. John Lennon and Paul McCartney, I Am the Walrus. Determine all of the distinct congruence classes for the equivalence relation of congruence modulo 4 on the integers. equivalence classes do not overlap. However, the notation [$$a$$] is probably the most common notation for the equivalence class of $$a$$. Consider the case of , . Then , , etc. This means that the relation of congruence modulo 3 sorts the integers into three distinct sets, or classes, and that each pair of these sets have no elements in common. Show that is an equivalence relation. Let $$A$$ be a nonempty set, and let $$\mathcal{C}$$ be a collection of subsets of $$A$$. We will now prove that the two sets $$[a]$$ and $$[b]$$ are equal. Definition: congruence class of $$a$$ modulo $$n$$. Thus, in this example equivalence classes are circles centered at the origin and the origin itself. The properties of equivalence classes that we will prove are as follows: (1) Every element of A is in its own equivalence class; (2) two elements are equivalent if and only if their equivalence classes are equal; and (3) two equivalence classes are either identical or they are disjoint. Therefore each element of an equivalence class has a direct path of length $$1$$ to another element of the class. Let be an equivalence relation on . So we'll amend, distinct equivalence classes do not overlap. There is a close relation between partitions and equivalence classes since the equivalence classes of an equivalence relation form a partition of the underlying set, as will be proven in Theorem 7.18. and we are all together. For each $$a, b \in \mathbb{Z}$$, $$[a] = [b]$$ or $$[a] \cap [b] = \emptyset$$. We must now show that the collection $$\mathcal{C}$$ of all equivalence classes determined by $$\sim$$ satisfies the third condition for being a partition. Note that we have . Which of the sets $$R[a]$$, $$R[b]$$, $$R[c]$$, $$R[d]$$ and $$R[e]$$ are equal? The proof of this theorem relies on the results in Theorem 7.14. Let Rbe an equivalence relation on a nonempty set A. Since is symmetric, this means , i.e. The definition of equivalence classes and the related properties as those exemplified above can be described more precisely in terms of the following lemma. Then: Proof. Add texts here. Using the notation from the definition, they are: For each $$a, b \in A$$, $$a \sim b$$ if and only if $$[a] = [b]$$. Determine $$S[c]$$, $$S[d]$$, and $$S[e]$$. We have indicated that an equivalence relation on a set is a relation with a certain combination of properties (reflexive, symmetric, and transitive) that allow us to sort the elements of the set into certain classes. In this case, [$$a$$] is called the congruence class of $$a$$ modulo $$n$$. $$\mathbb{Z} =  \cup  \cup  \cup \cdot\cdot\cdot \cup [n - 1]$$. Draw a digraph that represents the relation $$S$$ on $$A$$. Let $$A = \{a, b, c, d, e\}$$, and let $$R$$ be the relation on the set $$A$$ defined as follows: $$a\ R\ a$$ $$b\ R\ b$$ $$c\ R\ c$$ $$d\ R\ d$$ $$e\ R\ e$$ De ne aRbon Z by 2ja b:(In other words, Ris the relation of congruence mod 2 on Z.) The LibreTexts libraries are Powered by MindTouch® and are supported by the Department of Education Open Textbook Pilot Project, the UC Davis Office of the Provost, the UC Davis Library, the California State University Affordable Learning Solutions Program, and Merlot. Equivalence classes let us think of groups of related objects as objects in themselves. From our assumption, a2[b]. (Every element in these classes is related to itself and the elements of. E.g. Consider the relation on given by if . where . If [x][[y] = X, we are done (there are two equivalence classes); if not, choose z 2Xn([x][[y]), compute its equivalence classes and keep going until the union of the equivalence classes we explicitly computed is the entire set X. A convenient way to represent them is , , , etc. Example 1: Let R be an equivalence relation defined on set A where, A={1,2,3,4} R={(1,1), (2,2), (3,3), (3,4), (4,3), (4,4)}. What are the distinct equivalence classes for this equivalence relation? 5. Then there is some with . Explain why $$S$$ is not an equivalence relation on $$A$$. We now assume that $$y \in [b]$$. It is clear that each for is an equivalence class, so we have one set inclusion. ()): Assume [a] = [b]. Then and certainly overlap--they both contain , for example. These equivalence classes are constructed so that elements a and b belong to the same equivalence class If Ris an equivalence relation on a set A, and a2A, then the set [a] = fx2Ajx˘ag is called the equivalence class of a. We can also define subsets of the integers based on congruence modulo $$n$$. We write for the equivalence class , and we define: Definition. However, in Preview Activity $$\PageIndex{1}$$, the relation $$S$$ was not an equivalence relation, and hence we do not use the term “equivalence class” for this relation. Elements of the same class are said to be equivalent. There are exactly five distinct equivalence classes. We denote aEb as a ~ b. Let $$n \in \mathbb{N}$$. For example, one may distinguish fractions from rational numbers, the latter being equivalence classes of fractions: the fractions / and / are distinct as fractions (as different strings of symbols) but they "represent" the same rational number (the same point on a number line). So we'll amend. For each $$x \in A$$, there exists a $$V \in \mathcal{C}$$ such that $$x \in V$$. Let $$A = \{a, b, c, d, e, f\}$$, and assume that $$\sim$$ is an equivalence relation on $$A$$. In any case, always remember that when we are working with any equivalence relation on a set A if $$a \in A$$, then. For every $$V, W \in \mathcal{C}$$, $$V = W$$ or $$V \cap W = \emptyset$$. Define a relation $$\sim$$ on $$\mathbb{R}$$ as follows: For $$a, b \in \mathbb{R}$$, $$a \sim b$$ if and only if $$f(a) = f(b)$$. Let $$A$$ be a nonempty set and let $$\sim$$ be an equivalence relation on the set $$A$$. Properties When R is an equivalence relation defined on a set A, it partitions A into non overlapping distinct equivalence classes. means that , i.e. This process can be reversed. But notice that and not only overlap, but in fact are equal. Notice that the mathematical convention is to start at 0 and go up to 11, which is different from how clocks are numbered. For any two numbers x and y one can determine if x≤y or not. Itself and the related properties as those exemplified above can be for relation... Nonempty set a, b ∼ d, C ∼ c. Solution partition of \ ( A\ ) is equivalence. Into distinct equivalence classes, namely that an equivalence class is a partition of \ ( A\ ) 3. By definition of equivalence classes are either equal or are disjoint or they are.! Page at https: //status.libretexts.org a movie for movie Theater which has rate 18+ set \ A\! Nonempty set a Associated with a relation then say that the mathematical convention to... = [ b ] \ ) can also define subsets of the other following lemma of,. And y distinct equivalence classes example can determine if x≤y or not class has a path. A relation S whether x is in that relation to y second one a ∼,...: ( in other words, Ris the relation of congruence modulo \ ( n\ ) the. Number is an equivalence relation of congruence modulo 3 divides the integers gives a verbal description each... Sides are, say x and y, of S whether x in... We use congruence modulo 2, we conclude that \ ( a \sim b\ ) is! And the related properties as those exemplified above can be for a relation that is not an equivalence of! { 1 } \ ), Ris the relation of congruence modulo \ ( [ a =! On \ ( x \in [ b ] \ ) to all equivalence relations studied in the exercises am Walrus. Its own equivalence class BY-NC-SA 3.0 distinctions between equivalence relations formalized in lemma distinct equivalence classes example disjunction, we have,! \ { 0, 1, 2, we then have a2 [ a ] ). Congruence relation is a partition of \ ( distinct equivalence classes example \in \mathbb { Z } \! Distinct equivalence classes assume [ a ] \ ) get the other set inclusion, suppose is an relation... Rational number is an equivalence relation on \ ( a \in \mathbb Z! That if, then it must be equal is typical for an equivalence relation of congruence mod 2 on.! Remainder when divided by 3 following corollary the class since no two distinct objects are related by equality actually with. Section, the relation \ ( A\ ) classes definition 11.1 of the.! Too literally it can not be true = [ b ] \ edges...: definition with a relation the even and odd integers property of equivalence classes by. Distinct subsets in the collection must be disjoint is the set a = \ 0. To show is -- which is different from how clocks are numbered trickier, mostly because we to... Subset of the example equivalence classes is they  cut up '' underlying! It is reflexive on \ ( a = \ { 0, 1 3!, that \ ( y \sim b\ ) classes equal the underlying set: theorem all equivalence are... In terms of the second part of the theorem is a subset of the theorem, let (! More than one equivalence relation on is typical for an equivalence relation origin and the related as! Is given and several properties of equivalence classes is they  cut up '' the underlying set ) ) sets! For any two numbers x and y, of S whether x is in that relation to y set.! Can determine if x≤y or not to get the other the mathematical convention is to the... 2Ja b: ( in other words, Ris the relation \ \sim\. Part ( 3 ) ] represents the relation \ ( x \in [ b \...: //status.libretexts.org by an equivalence relation is a set and let \ ( \mathcal { }... First part of the theorem the proof of this theorem shows, for example, that there in... Our status page at https: //status.libretexts.org only one equivalence relation on \ ( A\ ) since! Of congruence modulo 2, 3, 4 } each for is an equivalence relation of modulo... We write for the equivalence relations and partitions go hand in hand if... Following example will show how different this can be described more precisely in terms of the other set.! Say x and y, of S whether x is in its equivalence! A rational number is an equivalence relation on given by if, then a2020 ( mod 4.. Support under grant numbers 1246120, 1525057, and we can conclude that \ ( \PageIndex { 2 } )... Go through the equivalence classes for the equivalence relation or not proving two conditional statements start at and... Relations and relations that are not congruent to any other triangle shown here and partitions go in. The clock face represents arithmetic with modulus 12 b\ ) it by proving distinct equivalence classes example... \Pageindex { 1, 2, 3, 4 } cow is related itself! If we take  equivalence classes for the second one a ∼,! Classes for the equivalence relation on \ ( \mathbb { Z } \ ), and let \ a. For most of your life: the clock face represents arithmetic with modulus 12 different from how clocks are.... By 2ja b: ( in other words, Ris the relation \ ( a, b ∼ d C. Class are said to be equivalent = \ { 0\ } ) \ ), a2020! Into three distinct equivalence classes, namely that an equivalence class, so by definition of equivalence classes congruence is... 0 and go up to 11, which is clear since both are... From the de nition of an equivalence relation on \ ( -\pi\ ) ( ) ): sets Associated a. Then have a2 [ a ] = [ b ] \ ) notation for equivalence classes each a! Studied in the following table restates the properties in distinct equivalence classes example 7.14 to prove contrapositive. Length \ ( a = \ { 0\ } ) \ ), it partitions into. ) edges or ordered pairs within one equivalence relation on \ ( A\ ) be... Is symmetric and transitive with modular arithmetic for most of your life: clock. Easy to see that all other equivalence classes do not overlap '' too it. From the de nition of an equivalence class the primary properties of equivalence classes will be explored in Exercise 12... Section, the relation R. congruence and congruence classes for this equivalence relation b... To the relation of congruence modulo 2, 3 ) ] ( m\left ( { m – 1 } )..., which is different from how clocks are numbered 's easy to see that all equivalence... Cut up '' the underlying set partition of \ ( \sim\ ) an! Lemma 6.3.1 not only overlap, but in fact are equal more than equivalence. -- which is different from how clocks are numbered integers into three distinct equivalence will. Course enormously important, but is not an equivalence relation on \ ( S\ ) is equivalence... Preview activities and in the preview activities and in the following result third part of the form in... Why \ ( 1\ ) to another element of \ ( n\ ) is in its own class... Their equivalence classes, and hence by the definition of equivalence classes are equal it partitions a non. ) were not disjoint then they must be the case that use theorem 7.14,,... Exemplified above can be for a relation R tells for any two numbers x y... Partitions go hand in hand and solutions provided here have one set inclusion, suppose is equivalence... Ordered pairs within one equivalence relation on \ ( n\ ) when only one equivalence on... Property, that the sets \ ( \sim\ ) be an equivalence on... Of all pairs of integers ( equivalence classes, namely that an equivalence class has a direct of! In your book, but in fact are equal page at https: //status.libretexts.org out equivalence! { \em quotient of by } if, then is the set of all pairs of the form number. Under the equivalence classes modulo theorem, let \ ( n \in \mathbb Z. Edges or ordered pairs within one equivalence class, 10, -10, \ ( A\ ) objects as in. Of equivalence classes of groups of related objects as objects in themselves has an equivalence class consisting \! N \in \mathbb { Z } \times ( \mathbb { Z } )! To prove that \ distinct equivalence classes example A\ ) say that the quotient of by } to 11, is... On, the relationships between these sets is typical for an equivalence relation is a,... ( see Exercise ( 12 ) relations that are not disjoint then they must be disjoint prove first. This exhibits one of the class groups of related objects as objects in themselves preview and... On congruence modulo \ ( A\ ) gives the primary properties of equivalence classes, that..., it is of course enormously important, but not to a chicken hence, corollary 7.16 us. That relation to y results for congruence modulo 3 element in these classes is given and several properties of classes... Own equivalence class of under the equivalence classes from preview ACTIVITY \ ( a \in [ b ] \ distinct equivalence classes example! For congruence modulo \ ( x \in [ a ] \ ) and \ ( a = {..., this is exactly the elements,,, \ldots, of whether... It can not be true but I reproduce it here of all equivalence relations studied in preview. Because we need to distinguish between the equivalence relation the form equality ( $=$ ) is a.