Help me understand 'equivalence classes' and relations I'm reading up on binary relations and I understand them to be a mapping from one set into another.
However I'm having problems understand 'equivalence classes'. My book only gives a pretty dry explanation.
If you could give a good tangible explanation of equivalence relations and equivalence classes, that would be great!
 A: Let $X$ be a finite set and $R \subseteq X^2$ be some binary relation. Then $R$ is very similar to a directed graph that has elements of $X$ as vertices, or in other words, $R$ can be drawn as dots and arrows. The following example depicts a graph and corresponding relation.
$$
\begin{array}{ccc}
1 &\to& \stackrel{\curvearrowright} 2 \\
\downarrow & & \updownarrow\\
3 & \gets & 4
\end{array}
$$
$$
\{(1,2),(1,3),(2,2),(2,4),(4,2),(4,3)\}
$$
Now, to talk about equivalence classes we need an equivalence relation. How an appropriate graph looks like?


*

*It has to be reflexive, that is, each vertex $v$ has to have a loop $\stackrel{\curvearrowleft}v$ like $2$ in the previous example.

*It has to be symmetric, i.e. each edge of the graph has to be bidirectional, like $\{2,4\}$ in the above diagram. If all the edges are bidirectional, then such graph is called undirected.

*It has to be transitive. This means that the graphs includes all the possible "shortcuts", i.e. if you can get from vertex $u$ to $v$, then there is an edge $u \to v$, or in case of undirected graphs $u \leftrightarrow v$.


The above conditions together imply that if some two vertices are connected, then they belong to a clique (a graph that has all the possible edges, modulo loops), that is, each connected component forms a clique. These cliques are precisely the equivalence classes. In the following diagram we have two: $\{1,2,3,4\}$ and $\{5,6,7\}$ (loops omitted for clarity).
$$
\begin{array}{ccc}
1 &\leftrightarrow & 2 &  & 5 & \leftrightarrow & 6\\
\updownarrow & \swarrow\hspace{-10pt}\nearrow\hspace{-10pt}\nwarrow\hspace{-10pt}\searrow & \updownarrow & &\updownarrow & \swarrow\hspace{-10pt}\nearrow\\
3 & \leftrightarrow & 4 & & 7
\end{array}
$$
Observe, that if we would add edge $4 \to 5$ then symmetry would require also $5  \to 4$ and then transitivity would add all the other edges. The two clusters would merge into a single equivalence class, i.e. the graph would become the $K_7$ clique.
This intuition also holds for infinite sets, but it's hard to draw infinite graphs. 
I hope this helps $\ddot\smile$
A: An equivalence relation on a set $X$ is a binary relation $R\subset X\times X$ such that the following three properties hold:


*

*Reflextivity: $xRx$, or $(x,x)\in R$ for every $x$ in $X$.

*Symmetry: $xRy \leftrightarrow yRx$ or $(x,y)\in R$ if and only if $(y,x)\in R$.

*Transitivity: $xRy \wedge yRz \rightarrow xRz$, or that if $(x,y), (y,z)\in R$, then $(x,z)\in R$.


An equivalence class is a subset $E$ of $X$ such that the following holds: if $x,y\in E$, then $(x,y)\in R$ (i.e. $xRy$), and if $x$ is an element of $E$ and $y$ is an element of $X$ such that $xRy$, then $y$ is also an element of $E$.  That is, it is closed under the relation and only contains the elements that are 'equivalent'.  
The idea is that an equivalence relation gives us a new way of saying whether or not two objects should be viewed as essentially the same thing; the equivalence classes are then the sets after grouping all the equivalent things together, and they form a way of partitioning the set into these 'sets of equivalent things'.
This mention of partitions is actually an important thing; it ends up that a partition of a set uniquely determines an equivalence relation, and vice-a-versa.  It is not hard to show that the set of equivalence classes is a partition of $X$ and given a partition, we can define a relation $R$ where $(x,y)\in R$ if and only if $x$ and $y$ lie in the same part of the partition; it can be checked rather easily that this is an equivalence relation.
A: I will assume that you know the definition of an equivalence relation on a set $A$.
Here is an example which may help:  Consider the set of all integers, $\mathbb{Z}$, and define and equivalence relation on $\mathbb{Z}$ by $a$ ~ $b$ if $a = b + 3k$ for some integer $k$.  Then there are three equivalence classes, $A_0, A_1, A_2$ where $A_j$ represents all the integers that leave a remainder of $j$, $0 \leq j \leq 2$ when divided by the number $3$.  Note that we have decomposed $\mathbb{Z}$ as $A_0 \cup A_1 \cup A_2 = \mathbb{Z}$ and that the sets $A_j$ are disjoint.
A: Actually, binary relations are more like "loose" mappings: they do not need to be defined everywhere on their domain and any point can have more than one image.
Formally, an equivalence relation on a set $X$ is a binary relation $\rho$ defined on $X$, that is a subset $\rho$ of $X\times X$, such that for every $x,y,z\in X$:


*

*$x\rho x$ (reflexivity)

*$x\rho y$ implies $y\rho x$ (symmetry)

*$x\rho y$ and $y\rho z$ imply $x\rho z$ (transitivity)


where we (customarily) write $x\rho y$ for $(x,y)\in\rho$. Now, from these properties we can see that $\rho$ induces a partition on $X$, namely a collection $P$ of subsets of $X$ such that


*

*$\varnothing\notin P$

*the union of all elements of $P$ is the whole space $X$

*$S_1\cap S_2=\varnothing$ for any two distinct $S_1,S_2\in P$


Indeed, for every $x\in X$ define $[x]=\{y\in X : x\rho y\}$. Then:


*

*by reflexivity $x\in[x]\neq\varnothing$

*$X\supseteq \bigcup_{x\in X} [x] \supseteq \bigcup_{x\in X} \{x\} = X$

*$z\in[x]\cap[y]\neq\varnothing$ implies $x\rho y$ by transitivity and symmetry, which then implies that $[x]=[y]$


Therefore the set $P=\{[x]:x\in X\}$ is indeed a partition of $X$. The equivalence classes of $\rho$ are exactly the elements of this partition.
Vice-versa, a partition $Q$ of $X$ induces an equivalence relation $\sigma$ on $X$ simply by defining $x\sigma y$ iff $x,y\in S$ for some $S\subseteq X$ (prove it!).
Finally, it is a nice, not so difficult, exercise to show that those two operations are actually the inverse of each other: the partition $P$ induced by a relation $\rho$ induces again $\rho$ and the relation $\sigma$ induced by a partition $Q$ induces again $Q$.
A: Binary relations and equivalence classes are two basic notions that we all learn at the very beginning of school. By this I am saying that you actually very well know what they are and how they work. 
It is only due to the bad influence of Bourbaki, the formalism that was important to address some problem in logic (like consistency) that those dry expositions have permeated areas of mathematics in which they are absolutely not needed, and even become detrimental.
I will use pictures to explain what are these two notions. I will use pictures because it is with pictures we (I) learned (in the first year we entered school in our life) what this concepts are.
Binary relation
In kindergarten they used to gives us pictures of a row of bees and a row of flower pots. 
We were supposed to draw arrows indicating what flowers each bee likes. There were different requirements about the preferences depending on the exercise and the skill the teacher wanted to teach. But a totally freely chosen set of arrows going from the bees to the flowers is what a relation is. 
If we require, for example, that a bee has only one favorite flower then we get a a relation that is what we call a function from bees to flowers. 
If we add to this the requirement, for example, that each flower should have no more than one bee that likes it, they we get a relation that is what we call an injective function from the bees to the flowers. 
And so on. 
Equivalence class
We had this other type of exercise in kindergarten. We were given a figure with many objects: flowers, tools, people, ...
We were given a feature, and we were supposed to enclose in blobs figures that had that feature in common. 
For example, we could be told to group figures by color, or by use, or by kingdom, etc.
Something like this. 

This breaking into classes is what an equivalence relation is. 
