Equivalence classes and their uses

Today I answered the following question on my FPM Piazza forum: What is the definition of an equivalence class and what is an example of it in use?

My response

We spent some time looking at relations on sets, and among these we identified some special relations called equivalence relations. These are relations which are reflexive, symmetric and transitive. Here I will assume that we are happy with those definitions, but I am happy to discuss relations and equivalence relations further if there are follow-up questions.

Before looking at the abstract setting, let's look again at some of the easiest examples, starting with the relation "congruence modulo \(2\)" defined on \(\mathbb{Z}\). This is the relation \(R\) on \(\mathbb{Z}\) defined as follows: for \(m\) and \(n\) in \(\mathbb{Z}\),

\(m \mathrel{R} n \Leftrightarrow m-n\) is even.

[Here "even" just means divisible by \(2\), which in turn means that the number must be of the form \(2 a\) for some integer \(a\). Note, in particular, that \(0\), \(6\) and \(-10\) are all even.]

This is a standard equivalence relation from the notes, and it has two "equivalence classes", namely the set \(E\) of all even integers, and the set \(O\) of all odd integers.

• All even integers are congruent to each other modulo \(2\), and they are not congruent to any odd integers modulo \(2\).
• All odd integers are congruent to each other modulo \(2\), and they are not congruent to any even integers modulo \(2\).
• Here \(\{E,O\}\) is an example of what we called a partition of \(\mathbb{Z}\).

We can do the same thing with congruence modulo \(10\), in which case we end up with \(10\) equivalence classes instead. More generally, for each positive integer \(k\), congruence modulo \(k\) is an equivalence relation, and gives a partition of \(\mathbb{Z}\) into \(k\) equivalence classes. This is the equivalence relation we met most often in lectures, and is closely related to modular arithmetic, which as we know is a very powerful tool when investigating problems relating to divisibility.

Now let's look at the abstract setting. Suppose that \(R\) is an equivalence relation on a non-empty set \(X\).

What we saw in lectures is that you can then use \(R\) to partition \(X\) into equivalence classes. Let's look at this in more detail, but (to start with) in a descriptive way rather than using the official definitions from lectures. (We'll come back to those later.)

Because \(R\) is symmetric, we can talk about two elements being "related to each other" or not, without having to specify which way round. Then, in addition, there is transitivity which causes elements that are related to each other to form "clumps" of elements all of which are related to each other (and also to themselves because of reflexivity). The equivalence classes are then "maximal clumps": non-empty sets of elements which are all related to each other (and themselves) and which cannot be expanded without losing this property. Each element then lives in its own maximal clump, and different maximal clumps cannot have elements in common (because otherwise transitivity would allow you to merge the two clumps together to make a bigger clump).

It may help to think about a collection of inhabited islands, and the elements of \(X\) as being people distributed among these inhabited islands (at a particular moment in time). Then the relation can be interpreted as "inhabiting the same island", and each maximal clump is just the set of inhabitants of one of these islands. This also shows how equivalence relations and equivalence classes fit with partitions. The partition you get is just this set of maximal clumps. (Exercise: draw a picture to illustrate this idea, or look back at some of the pictures we drew when discussing partitions of sets and see how the ideas fit together.)

How does this fit with the formal definitions from lectures?

Let \(x \in X\). Then (with respect to our equivalence relation \(R\)) the equivalence class of \(x\), \([x]\) is defined by

\([x]= \{y \in X: x \mathrel{R} y\}\,,\)

which is just the set of all those \(y\) in \(X\) which are related to \(x\) (either way round, because \(R\) is symmetric).

This is nothing other than the "maximal clump" with \(x\) in it. (Note that reflexivity ensures that \(x \in [x]\).) And we saw in lectures that \([x]=[y]\) if and only if \(x\) is related to \(y\) (either way round). In terms of our islands analogy, if you find an inhabitant \(x\) of an island, then \([x]\) is the set of all inhabitants of that island. This is the same as \([y]\) for any other inhabitant \(y\) of that island. All inhabitants of the same island are related (using \(R\)) to each other, and no inhabitants of different islands are related (using \(R\)) to each other.

Returning to the case of congruence modulo \(10\), with \(X=\mathbb{Z}\). We then have \(10\) different "inhabited islands", and \(10\) different maximal clumps/equivalence classes. If we were working with non-negative integers, we would just be interested in the last decimal digit, but negative integers bring in a minor complication. For example, one of our "maximal clumps" is the equivalence class

\(A=\{\dots,-17,-7,3,13,23,\dots\}\,,\)

Here \(A=[3]\), but we also have \(A=[-17]\) and \(A=[23]\), etc. These are all the same "clump".

There are only \(10\) different equivalence classes here, namely \([0],[1],[2],\dots,[9]\): all the rest are repeats (with period \(10\) as you run either way through the integers).

Modular arithmetic is often (but not always) helpful when we investigate Diophantine Equations (as we did at various points in classes).

Equivalence relations and equivalence classes are also important when you investigate the more abstract notion of quotients in mathematics, rather than the usual kind of quotients in division of integers. You will meet this in algebra/mathematical structures (where the equivalence classes using modular arithmetic will themselves become elements of a new mathematical structure). Quotients using equivalence relations are also used as "mathematical glue" to convert rectangles into Moebius strips etc. (See Lecture 14.)

So, why did the chicken cross the Moebius strip?

Best wishes,
Dr Feinstein