MaBloWriMo 28: Equivalence relations are partitions

Today we’ll take a brief break from group theory to prove a fact about equivalence relations, namely, that they are the same as partitions. A partition is a pretty intuitive concept: you take a big set, and cut it up into smaller sets so that every element of the big set belongs to exactly one of the small sets. That is, no elements are left out, and none of the small sets overlap with each other at all.

More formally, a partition of a set $S$ is a finite collection of nonempty sets $P_1, \dots, P_n$ such that

The union of all the $P_i$ is the original set: $\bigcup_i P_i = S$ .
The $P_i$ do not overlap, i.e. they are pairwise disjoint: if $i \neq j$ then $P_i \cap P_j = \varnothing$ .

So how does this relate to equivalence relations? Suppose we have a set $X$ and an equivalence relation $\sim$ on $X$ . Then the equivalence class of an element $x \in X$ is defined as the set of all elements which are equivalent to $x$ . We write

$[x] = \{ y \mid y \in X, x \sim y \}$

to denote the equivalence class of $x$ . It turns out that if $\sim$ is an equivalence relation, the equivalence classes form a partition of $X$ . Intuitively, each equivalence class consists of a bunch of things which are all equivalent to each other, and these necessarily include everything (since everything is at least equivalent to itself) and don’t overlap (because if two equivalence classes did overlap, they would collapse into one big class due to transitivity). Let’s prove it.

First we’ll prove a small lemma: if $y \sim z$ then $[y] = [z]$ . As is usual, to prove two sets are equal, we’ll prove that each is a subset of the other. First, suppose $y'$ is any element in $[y]$ . Then by definition $y \sim y'$ . By symmetry, $y' \sim y$ , and then by transitivity (since we assumed $y \sim z$ ), $y' \sim z$ . By symmetry again $z \sim y'$ , so by definition $y' \in [z]$ . So every element of $[y]$ is also an element of $[z]$ . An entirely analogous argument shows that $[z]$ is a subset of $[y]$ as well. Thus $[y] = [z]$ .
Now we can prove that the set of distinct equivalence classes forms a partition of $X$ . First, every $x \in X$ is at the very least included in its own equivalence class $[x]$ , which must contain $x$ since $x \sim x$ by reflexivity. So the equivalence classes don’t miss any elements, that is, the union of all the equivalence classes is the entire set $X$ .
We also have to prove that distinct equivalence classes don’t overlap. Let $P_i$ and $P_j$ be two different equivalence classes. We want to show they have no elements in common. Suppose, on the contrary, that there is some $x$ which is in both $[y]$ and $[z]$ . Then by definition $y \sim x$ and $z \sim x$ . So by symmetry $x \sim z$ , and then by transitivity $y \sim z$ . By our lemma above, this means $[y] = [z]$ , contradicting our assumption that they are different.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

2 Responses to MaBloWriMo 28: Equivalence relations are partitions

Tom says:

November 29, 2015 at 12:35 pm

Why the requirement for a partition to be a finite collection of subsets? If you use this restriction then you don’t get a 1-1 correspondence between partitions and equivalence relations like you want.
- Brent says:
  
  November 29, 2015 at 12:44 pm
  
  Good point. Since this is all in the service of proving things specifically about finite groups it doesn’t really matter; partitions with a finite number of parts and equivalence relations on finite sets are indeed in 1-1 correspondence. But you’re right that more generally the definition of a partition should be extended to include the possibility of breaking up infinite sets into infinitely many pieces.

Comments are closed.