Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
On sets, this is the Fundamental Theorem of Equivalence Relations. See, e.g. Dummit and Foote, Abstract Algebra, somewhere in the very first few pages. –  Willie Wong Dec 10 '10 at 13:01
    
I know the theorem. But I'd like to know whether there's an easy way to do the conversion based on the implicit definition of the relation, because, technically, this doesn't seem to be that easy all the time. –  Franz Dec 10 '10 at 13:47
add comment

3 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
Thanks. Good post. –  Franz Dec 12 '10 at 16:19
add comment

Suppose you have an equivalence relation $\sim$ on $X$. For each $x\in X$, the set $S_x=\lbrace y\in X: y\sim x \rbrace$ is one of the sets in the partition, and every set in the partition arises this way. But you should know that $S_x$ and $S_y$ are identical (the same) if and only if $x\sim y$.

On the other hand, if you have a partition $\lbrace C_i: i\in I \rbrace$ of $X$. Then the relation $\sim$ defined by $$ x\sim y \mbox{ iff } x,y \in C_i \mbox { for some } i $$ is an equivalence relation on $X$.

share|improve this answer
add comment

In addition to my comment above, see also this post at the ProofWiki.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.