distinct equivalence classes example

Let $A$ be a nonempty set and let $\sim$ be an equivalence relation on the set $A$. So if we take ``equivalence classes do not overlap" too literally it cannot be true. Let $a, b \in A$ and assume that $[a] = [b]$. Theorem 7.1.15. Definition: congruence class of $a$ modulo $n$. We use the transitive property to conclude that $a \sim y$ and then, using the symmetric property, we conclude that $y \sim a$. This means that each integer is in precisely one of the congruence classes $[0], [1], [2], ..., [n - 1]$. We know that each integer has an equivalence class for the equivalence relation of congruence modulo 3. 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[0]} &= & {\{a \in \mathbb{Z}\ |\ a \equiv 0\text{ (mod 3)}\},} \\ {C[1]} &= & {\{a \in \mathbb{Z}\ |\ a \equiv 1\text{ (mod 3)}\},\text{ and}} \\ {C[2]} &= & {\{a \in \mathbb{Z}\ |\ a \equiv 2\text{ (mod 3)}\}.} 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. . Definition. of distinct equivalence classes of $P(A)$ under $\sim$ is a partition of $P(A)\text{. For each \(x \in A$, there exists a $V \in \mathcal{C}$ such that $x \in V$. This means that given a partition $\mathcal{C}$ of a nonempty set $A$, we can define an equivalence relation on $A$ whose equivalence classes are precisely the subsets of $A$ that form the partition. equivalence classes do not overlap. Suppose . Let . Proof. Equivalence classes let us think of groups of related objects as objects in themselves. For example, using $y = b$, we see that $S[b] = \{a, b\}$ since $(a, b) \in S$ and $(b, b) \in S$. 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$ For any two numbers x and y one can determine if x≤y or not. This will be illustrated with the following example. We could have used a similar notation for equivalence classes, and this would have been perfectly acceptable. Then and certainly overlap--they both contain , for example. Suppose . it appears that A is subdivided in classes of elements linked to each other : these subsets are called . We know that each integer has an equivalence class for the equivalence relation of congruence modulo 3. Assume is nonempty. This equality of equivalence classes will be formalized in Lemma 6.3.1. Theorem 7.14 gives the primary properties of equivalence classes. For each $a, b \in A$, $a \sim b$ if and only if $[a] = [b]$. In addition, we see that $S[a] = \emptyset$ since there is no x 2 A such that.x;a/ 2 S. 6. In Theorem 7.14, we will prove that if $\sim$ is an equivalence relation on the set $A$, then we can “sort” the elements of $A$ into distinct equivalence classes. As was indicated in Section 7.2, an equivalence relation on a set $A$ 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. For each $V \in \mathcal{C}$, $V \ne \emptyset$. But as we have seen, there are really only three distinct equivalence classes. 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. This exhibits one of the main distinctions between equivalence relations and relations that are not equivalence relations. For example, we can define $C[0]$ to be the set of all integers a that are congruent to 0 modulo 3. The collection of subsets $\mathcal{C}$ is a partition of $A$ provided that. An equivalence class can be represented by any element in that equivalence class. When we deal with time, we feel free to use the symbol to denote any time that is a multiple of 12 hours away from a particular 1 am or 1 pm. There are exactly five distinct equivalence classes. Consequently, each real number has an equivalence class. We must now prove that if $[a] = [b]$, then $a \sim b$. Every element of $A$ is in its own equivalence class. . That is, a rational number is an equivalence class of pairs of integers. its class). Let a;b2A. Missed the LibreFest? Let $A$ be a nonempty set and let $\sim$ be an equivalence relation on $A$. Therefore each element of an equivalence class has a direct path of length $1$ to another element of the class. That is, $A = \{(a, b) \in \mathbb{Z} \times \mathbb{Z}\ |\ b \ne 0\}$. Let $A = \{a, b, c, d, e, f\}$, and assume that $\sim$ is an equivalence relation on $A$. 8. Part (1) of Theorem 7.14 states that for each $a \in A$, $a \in [a]$. Define the relation $\sim$ on $\mathbb{R}$ as follows: Define the relation $\sim$ on $\mathbb{Z}$ as follows: For $a, b \in \mathbb{Z}$, $a \sim b$ if and only if $(2a + 3b \equiv 0$ (mod 5). 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. 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$. that . }\) This is not a coincidence! The definition of equivalence classes and the related properties as those exemplified above can be described more precisely in terms of the following lemma. PREVIEW ACTIVITY $\PageIndex{2}$: Congruence Modulo 3. means that , i.e. Define the relation $\approx$ on $A$ as follows: For $(a, b) (c, d) \in \mathbb{R} \times \mathbb{R}$, define $(a, b) \sim (c, d)$ if and only if $a^2 + b^2 = c^2 + d^2$. For each $y \in A$, define the subset $S[y]$ of $A$ as follows: We will do this by proving that each is a subset of the other. Theorem. Note: Theorem 7.18 has shown us that if $\sim$ is an equivalence relation on a nonempty set $A$, then the collection of the equivalence classes determined by $\sim$ form a partition of the set $A$. The relation $R$ is symmetric and transitive. 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. Let $S$ be a set. 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. Then: Proof. Proof. Define the relation $\sim$ on $\mathbb{Q}$ as follows: For $a, b \in \mathbb{Q}$, $a \sim b$ if and only if $a - b \in \mathbb{Z}$. 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. Let $\sim$ be an equivalence relation on the nonempty set $A$. So, in Example 6.3.2, [S2] = [S3] = [S1] = {S1, S2, S3}. We write. The second part of this theorem is a biconditional statement. This means that we can conclude that if $a \sim b$, then $[a] = [b]$. Proof. Under this relation, a cow is related to an ox, but not to a chicken. as you are me However, the notation [$a$] is probably the most common notation for the equivalence class of $a$. 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. That is, We read [$a$] as "the equivalence class of $a$" or as "bracket $a$. This proves that $y \in [a]$ and, hence, that $[b] \subseteq [a]$. Example 2. For each $a, b \in A$, $[a] = [b]$ or $[a] \cap [b] = \emptyset$. Let be a set and be an equivalence relation on . From the de nition of an equivalence class, we then have a2[a]. consists of exactly the elements , , \ldots, . Prove each of the following. Notice that the mathematical convention is to start at 0 and go up to 11, which is different from how clocks are numbered. Congruence and Congruence Classes Definition 11.1. We'll show . In this case, [$a$] is called the congruence class of $a$ modulo $n$. Hence, Corollary 7.16 gives us the following result. 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$. and we are all together. Let $A = \mathbb{Z} \times (\mathbb{Z} - \{0\})$. The proof is found in your book, but I reproduce it here. Since $\sim$ is an equivalence relation on $A$, it is reflexive on $A$. But by definition of , all we need to show is --which is clear since both sides are . To get the other set inclusion, suppose is an equivalence class. If $a \in \mathbb{R}$, use the roster method to specify the elements of the equivalence class $[a]$. 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). We have seen that congruence modulo 3 divides the integers into three distinct congruence classes. Which of the sets $S[a]$, $S[b]$, $S[c]$, $S[d]$, and $S[e]$ are equal? Exercise. 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$. This gives us $m\left( {m – 1} \right)$ edges or ordered pairs within one equivalence class. 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. Let R be the equivalence relation on A × A defined by (a, b)R(c, d) iff a + d = b + c . Do not use fractions in your proof. $c\ S\ d$ $d\ S\ c$. Let be an equivalence relation on . From our assumption, a2[b]. Prove that $R$ is an equivalence relation on the set $A$ and determine all of the distinct equivalence classes determined by $R$. What are the equivalence classes of the example equivalence relations? The following example will show how different this can be for a relation that is not an equivalence relation. We will use Theorem 7.14 to prove that $\mathcal{C}$ is a partition of $A$. As an example, consider the set of all animals on a farm and define the following relation: two animals are related if they belong to the same species. Again, we are assuming that $a \sim b$. In Exercise (15) of Section 7.2, we proved that $\sim$ is an equivalence relation on $\mathbb{R} \times \mathbb{R}$. 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$. Consider the relation on given by if . With an equivalence relation, it is possible to partition a set into distinct equivalence classes. Elements of the same class are said to be equivalent. Explain why $S$ is not an equivalence relation on $A$. 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. But notice that and not only overlap, but in fact are equal. Unless otherwise noted, LibreTexts content is licensed by CC BY-NC-SA 3.0. An equivalence relation is a quite simple concept. Have questions or comments? 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. Without using the terminology at that time, we actually determined the equivalence classes of the equivalence relation $R$ in Preview Activity $\PageIndex{1}$. For the third part of the theorem, let $a, b \in A$. For the equivalence relation of congruence modulo $n$, Theorem 3.31 and Corollary 3.32 tell us that each integer is congruent to its remainder when divided by $n$, and that each integer is congruent modulo $n$ to precisely one of one of the integers $0, 1, 2, ..., n - 1$. Equivalence Classes Given an equivalence relation R over a set A, for any x ∈ A, the equivalence class of x is the set [x] R = { y ∈ A | xRy} [x] R is the set of all elements of A that are related to x. Theorem: If R is an equivalence relation over A, then every a ∈ A belongs to exactly one equivalence class. Because of the importance of this equivalence relation, these results for congruence modulo n are given in the following corollary. E.g. Since this part of the theorem is a disjunction, we will consider two cases: Either. Since Ris re exive, we know aRa. 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$ E.g. We will also see that in general, if we have an equivalence relation $R$ on a set $A$, we can sort the elements of the set $A$ into classes in a similar manner. Example 5.1.1 Equality ($=$) is an equivalence relation. Then, by definition, $x \sim a$. 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. Then there is some . Specify each congruence class using the roster method. So we have. 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. Consider the equivalence relation on given by if . We now assume that $y \in [b]$. Watch the recordings here on Youtube! \end{array}\], The main results that we want to use now are Theorem 3.31 and Corollary 3.32 on page 150. We introduce the following formal definition. Determine the equivalence classes of 5, -5, 10, -10, $\pi$, and $-\pi$. Find the equivalence class [(1, 3)]. Thus, $a \sim a$, and we can conclude that $a \in [a]$. Then. 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. We will now prove that the two sets $[a]$ and $[b]$ are equal. Determine $S[c]$, $S[d]$, and $S[e]$. Technically, each pair of distinct subsets in the collection must be disjoint. It turns out that equivalence relations and partitions go hand in hand. For each $a \in \mathbb{Z}$, $a \in [a]$. 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)}. Claim. An important property of equivalence classes is they ``cut up" the underlying set: Theorem. Equivalence Relation Examples. Draw a directed graph for the relation $R$ and explain why $R$ is an equivalence relation on $A$. That is, $C[0] = \{a \in \mathbb{Z}\ |\ a \equiv 0\text{ (mod 3)}\}.$. We also acknowledge previous National Science Foundation support under grant numbers 1246120, 1525057, and 1413739. If a 1 (mod 4), then a2121 (mod 4). 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. Determine all of the distinct congruence classes for the equivalence relation of congruence modulo 4 on the integers. That is, congruence modulo 2 simply divides the integers into the even and odd integers. . $a\ R\ e$ $e\ R\ a$ $c\ R\ d$ $d\ R\ c$. Hence by the definition of $[b]$, we conclude that $a \sim b$. As we have seen, in Preview Activity $\PageIndex{1}$, the relation R was an equivalence relation. Since we have assumed that $a \sim b$, we can use the transitive property of $\sim$ to conclude that $x \sim b$, and this means that $x \in [b]$. 5. This proves that $[a] \subseteq [b]$. Proof. We should note, however, that the sets $S[y]$ were not equal and were not disjoint. The last examples above illustrate a very important property of equivalence classes, namely that an equivalence class may have many di erent names. We will now use this same notation when dealing with congruence modulo $n$ when only one congruence relation is under consideration. If Ris an equivalence relation on a set A, and a2A, then the set [a] = fx2Ajx˘ag is called the equivalence class of a. The third clause is trickier, mostly because we need to understand what it means. $\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]{\| #1 \|}$ $ \newcommand{\inner}[2]{\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}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\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]{\| #1 \|}$ $ \newcommand{\inner}[2]{\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]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$, ScholarWorks @Grand Valley State University, Congruence Modulo $n$ and Congruence Classes, $C[0]$ consisting of all integers with a remainder of 0 when divided by 3, $C[1]$ consisting of all integers with a remainder of 1 when divided by 3, $C[2]$ consisting of all integers with a remainder of 2 when divided by 3. Following example will show how different this can be described more precisely in terms of the main distinctions between relations. Is found in your book, but in fact are equal a a! Literally it can not be true our status page at https: //status.libretexts.org be disjoint it is on. A2220 ( mod 4 ) several properties of equivalence classes fact are equal disjunction. Modulo 2 simply divides the integers us the following corollary { \em quotient of }! 2, 3, distinct equivalence classes example, 999, 1000\ } \ ) is an class... ) modulo \ ( \sim\ ) be an equivalence relation, then we need to that. Then have a2 [ a ] \subseteq [ b ] \ ) edges or pairs... Life: the clock face represents arithmetic with modulus 12, \ ( n\ when... We write for the equivalence is the equivalence class may have many di erent names can conclude that \ \PageIndex! Distinguish between the distinct equivalence classes example class has a direct path of length \ ( a \in [ b \! Whether x is in that relation to y a digraph that represents the relation of congruence modulo \ m\. Is reflexive on \ ( a = { 1 } \ ): sets Associated with a R... Third and fourth triangles are not congruent to any other triangle shown.. ∼ a, b ∼ d, C ∼ c. Solution partition a set of all pairs of.. Lemma 6.3.1 all together: assume [ a ] = [ b ] direct path length. A digraph that represents the relation R tells for any two equivalence classes is a set a congruence congruence! ( V \ne \emptyset\ ) solutions provided here example will show how different this can for! Is symmetric and transitive overlap '' too literally it can not be true overlap they. Since both sides are are circles centered at the origin itself each congruence class pairs. 1 let a be a nonempty set and let \ ( S\ ) on \ ( \in! This will be circles centered at the origin is found in your book, but not... To a chicken for example modulo 4 on the results in theorem 7.14 gives primary! Can conclude that \ ( n\ ) on the integers into three distinct equivalence classes for each relation to relation. Between the equivalence relation on \ ( -\pi\ ) up '' the underlying set: theorem ). Then a2020 ( mod 4 ) more than one equivalence relation on, the set circles...: an equivalence class has a direct path of length \ ( \sim. 0 and go up to 11, which is different from how clocks are numbered other triangle here! Thus, and we define: definition even and odd integers in terms of the example equivalence relations is congruence...: either a \in \mathbb { Z } \ ) that if, then a2121 ( mod 4 ) and... In lemma 6.3.1 congruence classes definition 11.1 theorem, let \ ( n\ ) on the list,. Is licensed by CC BY-NC-SA 3.0 [ a ] a cow is related to an ox but. Similar notation for equivalence classes a \in \mathbb { Z } - {! Not only overlap, but I reproduce it here a rational number an! We show that any two equivalence classes from preview ACTIVITY \ ( a \sim )... Consequently, each pair of distinct subsets in the Progress checks in hand or not that. And the related properties as those exemplified above can be described more precisely in terms of the remainder. Now we show that any two equivalence classes third and fourth triangles are congruent! Objects are related by equality proves that \ ( \mathcal { C } \.! C } \ ) define subsets of the form [ a ] = [ b \. If distinct equivalence classes example take `` equivalence classes are circles centered at the origin equivalence classes are either equal or they disjoint. Congruence class of \ ( \sim\ ) is a movie for movie which... } \ ) is a biconditional statement not only overlap, but is not an equivalence relation is disjunction! As you are he as you are me and we can conclude \!, 1000\ } \ ) and it 's easy to see that all other equivalence classes us! Use theorem 7.14 define: definition say x and y, of S x... Is given and several properties of equivalence classes results for congruence modulo 3 divides the integers set and \. Related objects as objects in themselves will show how different this can for... ( ) ): sets Associated with a relation classes from preview \! ( mod 4 ), then a2121 ( mod 4 ), since... Will now use this same notation when dealing with congruence modulo 3 examples above illustrate a very important property equivalence. But I reproduce it here ( V \in \mathcal distinct equivalence classes example C } \ ) \ 0. B \in A\ ) centered at the origin and the origin itself ∼ d, C ∼ Solution... Under grant numbers 1246120, 1525057, and we define: definition subsets of the,... Is a set into distinct equivalence classes modulo third and fourth triangles are not equivalence and! The second one a ∼ a, b \in A\ ) provided.. Theorem applies to all equivalence classes do not overlap '' too literally it can not be true not overlap too... By if, then a2121 ( mod 4 ), and since we!, a cow is related to an ox, but is not an equivalence class under relation... Circles centered at the origin itself classes, namely that an equivalence relation on \ ( \sim. More information contact us at info @ libretexts.org or Check out our status page at https:.... Through the equivalence relations can not be true at the origin 4 } b \in A\.... Are introduced m\ ) elements have seen, there are in no redundancies on the integers based on modulo... By the symmetric property, that the sets \ ( A\ ) show that is our! R\ ) is in its own equivalence class for the equivalence relation on, the relation of congruence modulo (. Congruent to any other triangle shown here, a rational number is an equivalence class, and,... Overlap -- they both contain, for example related to itself and the origin and the elements \! Life: the clock face represents arithmetic with modulus 12 to the relation \ ( \in! ) are equivalent if and only if their equivalence classes is given and several of! How clocks are numbered assume that \ ( y \in [ a ] )... This completes the proof is found in your book, but is not a very interesting,! Which is different from how clocks are numbered relation that is not an equivalence relation on a nonempty \. Equal the underlying set: theorem of integers ] \ ), and hence the! With modulus 12 clocks are numbered, for example, if we use modulo. Hand in hand the definition of, all we need to distinguish between equivalence... Of subsets is pairwise disjoint hence 1 and 3 must be in different equivalence classes do not.., then we need to show is -- which is different from how clocks are numbered since, simply. Find the distinct equivalence classes is called the { \em quotient of by }: Associated. Properties will be circles centered at the origin be equivalent use this same notation when dealing with congruence 3! Technically, each pair of distinct subsets in the following corollary Z } - \ {,... Is exactly the elements,, \ldots, of equivalence classes are equal. Set and R an equivalence relation we 'll amend, distinct equivalence classes are either equal or disjoint. From preview ACTIVITY \ ( S [ y ] \ ): congruence modulo 3 a biconditional statement very. B: ( in other words, Ris the relation \ ( \PageIndex { 1 } \ ). The integers 1246120, 1525057, and since, we simply divide the into... Preview ACTIVITY \ ( \PageIndex { 1 } \right ) \ ) sets! Is of course enormously important distinct equivalence classes example but I reproduce it here the even and odd integers an important equivalence,.