Grasping the concept of equivalence classes more concretely

Question

I have read about equivalence classes a lot but unable to understand exactly what they are. I know about equivalence relations, but I am having a hard time understanding what equivalence classes are exactly.

Can anyone explain the concept of equivalence classes clearly?

Answer 1

Just in case you wanted a nice example: Consider the following shopping list made into a mathematical set $S$ \begin{equation} S = \{a=\text{apple}, b=\text{banana}, c=\text{chicken}, d=\text{date}, e=\text{elk}\}. \end{equation}

Define the equivalence relation to be \begin{equation} aRb\text{ if and only if a is the same food "type" as b}. \end{equation}

For example $a=$ apple is related to $b=$ banana as they are both fruit or $c=$ chicken is related to $e=$ elk as they are both meats. Now I would like to organise these items into "bags" (equivalence classes) of equivalent "items" (elements of set $S$). To start I'll pick all the items equivalent to $a=$ apple

\begin{equation} \{x\in S\text{ such that }xRa\}=\{a=\text{apple},b=\text{banana}, d=\text{date}\} \end{equation} and now I'll pick all the items equivalent to $c=$ chicken \begin{equation} \{x\in S\text{ such that }xRc\}=\{c=\text{chicken}, e=\text{elk}\}. \end{equation} Now I could pick any other element to create an equivalence class but the result would be a set equal to one of the ones we already have and thus we won't bother, but technically each element creates an individual equivalence class. Note that the equivalence classes above partition the original set and are disjoint (in general the equivalence classes will be either equal or disjoint), and that I could pick any element from each set as a representative of what is inside the "bag" (imagine a picture of a banana on the outside of the bag representing the bag that has fruit in it).

Answer 2

If you collect money, which contains different types of coins, notes,.. then while keeping them in better form, you will naturally keep coins of same value together, which exactly means you are putting them in an equivalence class.

Here two coins are equivalent if, and only if they have same value. This is an equivalence relation, and the collection of all those coins with same value is an equivalence class.

Answer 3

The main thing to understand is that when you have an equivalence relation $R$ given on a set $S$, you're able to create a partition on the set $S$.

Having a detailed look at the demonstration of this fact is a great move to understand the link between an equivalence relation and its classes.

Answer 4

An equivalence relation $R$ partitions a set $S$ into two or more subsets such that:

1. if $i\ne j,\;\;S_i\cap S_j=\emptyset$
2. $\bigcup_i S_i=S$

Each $S_i$ is an equivalence class.

From the definition of an equivalence relation, we have $R$ must be reflexive, symmetric and transitive.

The page from your image considers the sets $\subset\mathbb{Z}$ satified by:

$R=\{(a,b)|a,b\in\mathbb{Z}, a-b$ is even$\}$

It then proves $R$ is reflexive, symmetric and transitive, and hence $R$ is an equivalence relation.

Then it finds the equivalence classes, namely:

$E_0=\{\dots,-6,-4,-2,0,2,4,6,\dots\}$

$E_1=\{\dots,-5,-3,-1,1,3,5,\dots\}$

We have $E_0\cap E_1=\emptyset$ and $E_0\cup E_1=\mathbb{Z}$.

The mod operator is an equivalence relation, defined by:

$M_k=\{(a,b)|a,b\in\mathbb{Z},(a-b)|k\}$

and $R$ from your image is $M_2$.

Answer 5

Given a set $S$ and an equivalent relation $R$ then the equivalenz class of $a\in S$ is defined as

$$[a] := \{b\in S\ |\ (a,b) \in R\}$$

So the for an particular element $a$ the equivalenz class is the set of all elements $b$ that are equivalent to $a$.

Observe that $\forall b \in [a]: [b] = [a]$

proof: $"\subset"$ let $c \in [b]$ then $(b,c)\in R$. Because $(a,b) \in R$ by transitivity $(a,c)\in R$ so $c\in [a]$.

$"\supset "$ since $b\in [a]$ then $(a,b)\in R$. By symmetry $(b,a)\in R$ so $a\in [b]$ and by reflexivity $a\in [a]$

this means that the equivalenz relation splits up the set $S$ into subsets (the equivalenz classes) which are disjunct. As in the example in your link the defined equivalenz relation $R$ splits up $Z$ into the set of even and uneven numbers.

It might be confusing that we write $[a_1]$ because it looks like an element. But always remember that this is a set $[a_1] = \{a_1, a_2, \dots, a_n\}$ and with what we have just proven it doesn't matter what "representative" we choose to write in the bracket: $[a_1]= [a_2]= \dots =[a_n]$.

This is all rather abstract and in order to really understand concepts like this it is always good to look at lots of examples, at least that is what I always found.

Answer 6

I think of this in terms of what an equivalence relation is actually for. I'm aiming for an intuitive "proof" of the theorem that an equivalence relation partitions its domain. By which I mean, a hand-wave that corresponds loosely to a proper proof. I assume you've seen a proper proof, but that the details distracted your intuition.

You know that an equivalence relation $R$ by definition is true or false for each pair of elements taken from the domain, and that it is reflexive, symmetric and transitive. So for each element of the domain, consider the set of elements that can be "reached" from that element by 0 or more steps from $a$ to $b$ where $aRb$ is true (a "transitive closure"). We can see that:

• every element in the domain belongs to at least one such set (the one starting from itself)
• if element $b$ belongs to the set starting from $a$, then thanks to symmetry $a$ belongs to the set starting from $b$, we can retrace our steps in the opposite direction. Therefore, the "starting point" doesn't matter, all elements of the set are (dare I say it) equivalent. This means the sets are disjoint (the set starting from $x$ and the set starting from $y$ are either the same set, or else they have no elements in common), which together with the point above means they're a partition.
• if $a$ and $b$ belong to each other's sets, then either we took some steps to get from one to the other, in which case by transitivity $aRb$. Or we took no steps at all (they're the same point), in which case by reflexivity $aRa$. So the "set starting from $a$" is just the set of points related to $a$ by $R$, the sets form a partition, and this is what we mean when we say that the relation "partitions" the domain into "equivalence classes".

So "equivalence class" just means, "one of the sets that form the partition", and this is the same thing as "a set of points that are all related to each other and no other points". "Equivalence class of $x$" just means, "the part of the partition $x$ is in" or "everything in the domain that is equivalent to $x$".

Also, the reason that such relations are called "equivalence relation" is not because the word "equivalence" means anything to do with reflexivity, symmetry or transitivity. They're called "equivalence relations" because they partition their domain into sets of items, and for each of those sets we can consider all of the elements of that set "equivalent" as far as using the relation is concerned. In effect, the definition is for convenience, and the proof of the existence and properties of equivalence classes is of fundamental importance to the concept of equivalence relations.

Answer 7

I was once asked to "Give a complete set of equivalence class representatives," and I knew it was time to actually try to understand what equivalence relations/classes were all about. My reason for answering is because I remember coming across a lucid explanation of these concepts in the Princeton Companion to Mathematics (p. 12). Hopefully you'll find the following as helpful as I did.

---

Equivalence relations: There are many situations in mathematics where one wishes to regard different objects as "essentially the same," and to help us make this idea precise there is a very important class of relations known as equivalence relations. Here are two examples. First, in elementary geometry one sometimes cares about shapes but not about sizes. Two shapes are said to be similar if one can be transformed into the other by a combination of reflections, rotations, translations, and enlargements; the relation "is similar to" is an equivalence relation. Second, when doing arithmetic module $m$, one does not wish to distinguish between two whole numbers that differ by a multiple of $m$: in this case one says that the numbers are congruent $\pmod m$; the relation "is congruent $\pmod m$ to" is another equivalence relation.

Equivalence classes: What exactly is it that these two relations ("similarity" and "congruence") have in common? The answer is that they both take a set (in the first case the set of all geometrical shapes, and in the second the set of all whole numbers), and split it into parts, called equivalence classes, where each part consists of objects that one wishes to regard as essentially the same. In the first example, a typical equivalence class is the set of all shapes that are similar to some given shape; in the second, it is the set of all integers that leave a given remainder when you divide by $m$ (for example, if $m=7$ then one of the equivalence classes is the set $\{\ldots,-9,-2,5,12,19,\ldots\}$).