Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What exactly are equivalence relations and equivalence classes? The latter is giving me the most trouble; I've tried to read multiple sources online but it just keeps going over my head.

Example question: What are the equivalence classes of 0 and 1 for congruence modulo 4?

share|improve this question
    
This is an intuitive sort of argument that helped me: Friendship is a relation on people, right? Let's check what properties it has. Friendship is reflexive, because you're your own friend. Friendship is symmetric because if I'm your friend, then you're mine. What if friendship were also transitive? So you're friends with all your friends' friends. That sounds like a high school where everyone's in a clique. Instead of complicated friend-of-a-friend stuff, you'd just have The Goth Kids and they all know each other, and the Jocks all know each other. Each clique is an equivalence class. –  Logan Stokols Nov 13 '12 at 9:41

3 Answers 3

up vote 1 down vote accepted

Heuristically: Let us take a finite set $S= \{s_1,...,s_n\}$. Now we "glue" together some elements, for example we could glue together $s_1$ and $s_2$, if we consider them to be "same object" we obtain a new set $S^*= \{s_1=s_2, s_3,...,s_n\}$. How should we call this first object in $S^*$? We can call it by $s_1$ or $s_2$ because it is determined by one of the two, but it is clear that it is not the same object as $s_1$ or $s_2$ in $S$. What about calling it equivalence class of $s_1$ and $s_2$? Similarly we can call equivalence relation the glueing operation we perform on the set $S$.

Formally: This time the set $S$ is not finite anymore, simply because we don't need it. Let us cite the formal definition of equivalence relation from Wikipedia.

A given binary relation $\sim$ on a set $S$ is said to be an equivalence relation if and only if it is reflexive, symmetric and transitive. Equivalently, for all $a$, $b$ and $c$ in $A$: $$ a \sim a. \qquad \text{(Reflexivity)}$$ $$\text{if} \: a \sim b \:\text{then} \:b \sim a. \qquad \text{(Symmetry)}$$ $$\text{if}\: a \sim b\:\text{and}\: b \sim c \:\text{then}\: a \sim c. \qquad \text{(Transitivity)}$$

To translate what we said above now we glue the elements $s_1$ and $s_2$ of $S$ if and only if $s_1\sim s_2$. Why do we need this complicated definition? Because we can now make a partition of the set $S$, let us call $[s]=\{t\in S\; | \;t\sim s\}\subset S$ the set of all the elements in $S$ which are in relation with $s$, and make this construction for every element of the set.

It is clear that can happen $[s] \cap [t] \neq \emptyset$ for some elements $s,t \in S$, but using the definition of equivalence relation above you can easily verify that this is indeed a partition of the set $S$. Where this essentially means that if $[s]\cap [t] \neq \emptyset$ then $[s]=[t]$.

Now the last step is simply to give a name to the subset $[s]\subset S$, how do you like equivalence class of $s$?

Example: Let us examine your proposed example. Take $S=\mathbb{Z}$, the set of integers number. and the equivalence relation to be $a \sim b \Leftrightarrow a = 4k +b$ for some $k\in \mathbb{Z}$. Then you can use the machinery above for $s=0$: $$[0]= \{n \in \mathbb{Z} \:|\: n= 4k \text{ for some } k \in \mathbb{Z}\}= \{...,-12,-8,-4,0,4,8,12,...\}.$$ And for $s=1$: $$[1]= \{n \in \mathbb{Z} \:|\: n= 4k +1 \text{ for some } k \in \mathbb{Z}\}= \{...,-13,-9,-5,-1,3,7,11,...\}.$$

share|improve this answer

take any number $n$ and divide it by $4$ and consider the reminder the values of remainder range from $0$ to $3$
as a result there are 4 classes :-
equivalence class of $0$ is $\{4,8,12,........\}$ (multiples of 4).
equivalence class of $1$ is $\{5,9,13,........\}$ numbers of the form $4k+1$

share|improve this answer
    
Thanks for the response. Can you just explain the equivalence classes in greater depth? I realize how this makes sense for the example question I've given, but I'm having trouble applying it to other situations. –  Bob John Nov 13 '12 at 9:31
    
Also, how does the equivalence class relate to a partition of a set? –  Bob John Nov 13 '12 at 9:34

At the beginning you have a large set of "things" that differ in millions of ways, say the set of all people living on earth at the moment. But you are mainly interested in languages. Not knowing yet how many languages there are in the world you nevertheless are able to group all these people according to their native tongues: Call two people equivalent if their native tongues coincide. This simple device puts some structure onto the cloudy multitude of people: They now fall into groups having the same native tongue, and that exactly is the topic that interests you. Each of these groups is called an equivalence class with respect to the relation "are of same native tongue". Note that you were not required to have a list of all existing languages at the start; but now you can count the number of languages, and you can also form a "set of representatives" by selecting a member of each language group.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.