# Every equivalence relation on a set $S$ defines a corresponding partition, and vice versa

Could someone help me prove this? This is one of the opening exercises in my Algebra book that I just can't figure out how to solve. I don't understand how to show that the equivalence classes defined by the relation would be disjoint. The opposite direction also completely baffled me on how to start.

Seeing as how Wikipedia refers to this proof as the Fundamental Theorem of Equivalence Relations, and seeing how someone here or on MathOverflow commented that it was one the most important things they'd make sure an algebra student took away from their classes, I figured it's important enough for me to see it proved.

I'd really appreciate that any answers do everything with function notation, instead of using kind of slippery words like "choose" or "pick"; I'm always bad at knowing when to invoke them.

I'd also appreciate examples of what this result is useful for proving.

-
I've updated my answer with an example. Is that what you're looking for? – lhf Apr 8 '11 at 1:14
@lhf Yes, any examples are great. – Uticensis Apr 8 '11 at 2:00
For more examples, see en.wikipedia.org/wiki/Equivalence_class , especially the construction of rational numbers from integers. – lhf Apr 8 '11 at 2:45

Consider an equivalence relation $\sim$ on a set $S$. Consider the equivalence classes $[a]=\{ x \in S : x \sim a \}$. By definition these are subsets of $S$. Their union is $S$ because by reflexivity $a\in[a]$ for every $a\in S$. Finally, they are disjoint because if $x \in [a]$ and $x \in [b]$ then $x \sim a$ and so $a \sim x$, by symmetry. But then $a \sim b$ by transitivity and so $a\in [b]$. Every $y \in [a]$ is also in $[b]$ again by transitivity. This means that $[a]\subseteq [b]$. Swapping $a$ and $b$, we conclude $[a]=[b]$. All this means that the equivalence classes form a partition of $S$.

Conversely, given a partition of $S$ in subsets $C_\lambda$, define an equivalence relation in $S$ by $a\sim b$ iff there is a $\lambda$ such that $a$ and $b$ are both in $C_\lambda$. Since the $C_\lambda$ cover $S$, every $a\in S$ is in one of those and so $\sim$ is reflexive. By definition, $\sim$ is symmetric. Since the $C_\lambda$ are disjoint, $\sim$ is transitive.

A classical application of this is Lagrange's theorem on groups: the cosets of a subgroup are equivalence classes and so form a partition. On the other hand, they all have the same cardinality. Hence, the size (order) of the subgroup divides the size of the group.

-

Fix a set $S$.

An equivalence relation on $S$ is a subset $E$ of $S \times S$ that satisfies reflexivity, symmetry, and transitivity. (Instead of writing $x \sim y$, we say that $(x, y) \in E$.) Let $\mathcal E = \mathcal E(S)$ denote the set of all equivalence relations on $S$.

A partition of $S$ is a set of subsets $P = \{ S_i \}$ that span $S$ and are pairwise disjoint. Let $\mathcal P = \mathcal P(S)$ denote the set of all partitions on $S$.

Define a map $\alpha: \mathcal E \to \mathcal P$, taking an equivalence relation and producing a partition from it. How? Begin with an equivalence relation $E \in \mathcal E$. For any element $s \in S$, the other elements in the same part of the partition $\alpha(E)$ are precisely those that are equivalent to $s$ in $E$. You have to show that the two conditions that make a partition are satisfied.

In the other direction, define $\beta: \mathcal P \to \mathcal E$, taking a partition and producing an equivalence relation from it. How? Now, begin with a partition $P \in \mathcal P$. For any element $s \in S$, another element is equivalent to $s$ in $\beta(P)$ exactly when they belong to the same part of the partition. Here you have to show that the three conditions that make an equivalence relation are satisfied.

In fact, the maps $\alpha$ and $\beta$ are mutually inverse bijections, meaning that $\alpha(\beta(P)) = P$ for any partition $P$ and $\beta(\alpha(E)) = E$ for any equivalence relation $E$.

-