# 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!

• Can you explain in what sense a binary relation is a mapping from one set into another? – anon Apr 4 '14 at 21:11
• @anon In the sense that binary relations can be seen as sort of "loose" functions (may not be defined everywhere and may have more than one image). To be able to define the properties of equivalence relations you need that the "domain" and the "codomain" are one and the same, though. – A.P. Apr 5 '14 at 10:55

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$

• I never thought of equivalence relations as groupoids, thanks! – A.P. Apr 4 '14 at 22:22
• @A.P. See here. Also, MathWorld suggests an inverse intuition: <<A useful way to think of a groupoid is as a parametrized equivalence relation on $B$, as follows. Given a groupoid over $B$, define an equivalence relation on $B$ by $\alpha(g)∼\beta(g)$ for each $g$ in $G$. This equivalence relation is "parameterized" because there may be more than one element in $G$ which give rise to the same equivalence, that is, $g$ and $g'$ such that $\alpha(g)=\alpha(g')$ and $\beta(g)=\beta(g')$.>> – dtldarek Apr 4 '14 at 22:36
• @A.P. On the other hand, I prefer the graph-theory-based intuition. In fact, this was my primary intention and I was quite surprised by your comment. Anyway, I'm glad I could help $\ddot\smile$ – dtldarek Apr 4 '14 at 22:44
• Thanks for the pointers. I just happen to be biased towards recognising category-like graphs as such. ;) – A.P. Apr 4 '14 at 22:44
• very nice!..... – Chinnapparaj R Jun 23 at 13:38

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.

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.

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

1. $\varnothing\notin P$
2. the union of all elements of $P$ is the whole space $X$
3. $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:

1. by reflexivity $x\in[x]\neq\varnothing$
2. $X\supseteq \bigcup_{x\in X} [x] \supseteq \bigcup_{x\in X} \{x\} = X$
3. $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$.

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.

• Your example deals with a very specific equivalence relation, namely one where there are two objects in each equivalence class. You picked a nice approach, but that's a bad example. – dtldarek Apr 4 '14 at 22:03
• I suggested an improvement, because I think your post is a bit misleading (notice that I did not downvote). However, nobody forces you to take good advice (I won't edit your answer against your will). On the other hand, I would say that your last comment is dangerously close to name-calling and there are users that might take offence. Perhaps you have a bad day, it happens to all of us. Nevertheless, people in this community have generally good intentions, please consider this the next time you will be writing a reply. – dtldarek Apr 4 '14 at 22:25
• Indeed, in elementary school we are given some basics about set theory and binary relations. I would like to point out, though, that you only described binary relations in general (without a word about equivalence relations). Moreover, what you describe as equivalence classes are just subsets. For example suppose we are asked to group the figures in the picture by colour: then the paint bucket would go in the same set as the brush, which would go in the same set as the baseball glove. Thus by transitivity the bucket and the glove are in the same subset, although they don't share any colour. – A.P. Apr 4 '14 at 22:40