[Math] “Converting” equivalence relations to partitions

Question

There is a direct relationship between equivalence relations and partitions.

Is there a way to simply use an equivalence relation's definition to get the matching partition? And what about the other way around?

Answer 1

Most of the time, an equivalence relation is hiding an "equality" somewhere; that is, $x\sim y$ if and only if $x$ and $y$ have something that you are trying to isolate which is "equal". With integers, the equivalence $a\equiv b\pmod{m}$ means that $a$ and $b$ have equal remainder when divided by $m$. We usually start from a notion of the thing that we want to be "the same", and define the equivalence relation accordingly, which makes it easier to think about just what are the equivalence classes: they correspond to all objects with the same "thingie" that we are focusing on in the first place.

But suppose you were walking down the street and you found an equivalence relation lying on the ground. Just how easy is it to figure out what this "equality" that is hinding behind it? How easy is it to describe all elements of the equivalence class of a given $x$?

The answer is that it depends greatly on the equivalence relation you find, and sometimes on the $x$. For some equivalence reations, it is fairly easy to figure it out, and then to partition the objects into equivalence classes. But for others, it may be more mysterious.

For example, suppose you only know about positive integers, their order, and their addition and multiplication. You don't know about negative numbers (as most of humanity did not for most of its history). I can define an equivalence relation on pairs of positive integers by $$(a,b)\sim (r,s) \Longleftrightarrow a+s = b+r.$$ It is easy to verify that this is an equivalence relation. But what is the partition it induces? What is that "equality" that is hiding behind that equivalence relation?

It's perhaps not so obvious. In fact, it comes from thinking of an ordered pair $(a,b)$ as corresponding to the equation $a+x=b$, so that the pair $(a,b)$ represents what we want to be a solution to this equation, which may or may not exist in the positive integers. Then $(a,b)\sim(r,s)$ means that the solution of $a+x=b$ should be "the same" as the solution of $r+x=s$. It seems obvious, then, that since $x=b-a=s-r$, this gives the condition I give, but the point is that one makes this definition among positive integers, where $b-a$ may be undefined, e.g., if $a\geq b$. It corresponds to a way of trying to think about negative numbers without having to use subtraction. But if you've never even thought about negative numbers, it would be rather difficult to figure it out, thought it would be pretty easy to check, given two pairs, whether they are equivalent or not; and you may even be able to describe all the pairs that are equivalent to a given one, at least sometimes.

But you really have little hope of having some general method that will work easily and always. The reason is precisely because equivalence relations correspond to partitions. Pick any partition, and define an equivalence relation by "$a\sim b$ if and only if they are in the same piece of the partition." That will be an equivalence relation, but if you find it lying on the quad you would be hard pressed to figure out where it could have come from, precisely because it came from an arbitrary partition that happened to catch your fancy at the moment.

So, the moral is that most of the time equivalence relations come from a very specific idea we are trying to isolate, or a specific issue that is somewhat troublesome and we want to avoid (for instance, two functions being identical except for some negligible set of points where they differ, which may lead to some 'obvious' conclusions being technically false but true in 'spirit', so we define an equivalence relation that puts two such functions into the same class so that our "true in spirit" becomes "technically true" by now refering to equivalence classes of functions instead of functions themselves). In such cases, it is very often easy to figure out the equivalence classes, or at least the bulk of each equivalence class (with some outliers being a bit troublesome from time to time). Practice and experience will let you spot them as they show up.