Why are partitions and equivalence relations the same thing?

Question

My lecturer omitted the proof in the lecture notes. From what I can gather, it's because equivalence classes partition always partition a set (the class can contain only that element or more and the elements in that class can only be in that one class so it acts as a partition). However, this, firstly, doesn't tell me why equivalence relations are the same thing as partitions and not equivalence classes, and to me it sounds like partitions cannot be arbitrary. From what I understood all they have to be are a collection of subsets $A_i$ forming some set $A$ such that:

1. $A_i \ne \emptyset$
2. $A_i \ \cap A_j = \emptyset , \ \ \ \text{if $j \ne i$}$
3. $\bigcup _i A_i = A$

I don't see any of these rules demanding subtly there be an equivalence relation, and doing so sounds like it puts restrictions on the creation of a partition that I don't see in its definition. How are they equivalent?

Answer 1

A partition and an equivalence relation are not the same thing; however, they can induce each other (as explained at the end of this answer). An equivalence relation $R$ on a set $A$ is a subset of $A\times A$ satisfying the following properties: $$(a,a)\in R\space\forall a\in A$$ $$(a,b)\in R\implies (b,a)\in R\space\forall a,b\in A$$ $$(a,b)\in R\space\text{and}\space (b,c)\in R\implies (a,c)\in R \space\forall a,b,c\in A$$ However, a partition $P$ of $A$ is a subset of $2^A$ satisfying the following two properties: $$p_i\cap p_j=\varnothing\space\forall p_i,p_j\in 2^A\space\text{with}\space p_i\ne p_j$$ $$\bigcup_{i=1}^{|P|}p_i=A$$ We have that $R\subset A\times A$ and $P\subset 2^A$, so they're not even the same type of object. However, your professor probably meant that every equivalence relation on a set $A$ induces a partition of $A$, and vice versa.

More specifically, if $R$ is an equivalence relation on $A$, then the induced partition $P$ is $$P=\{\{b:(a,b)\in R\}:a\in A\}$$ and if $P$ is a partition of $A$, then the induced equivalence relation $R$ is defined by $$R=\{(a,b):\exists p_i\in P\space\text{s.t.}\space a,b\in p_i\}$$ In plain words: If $R$ is a given equivalence relation, then the induced partition $P$ partitions $A$ into all sets of elements which are equivalent to each other under $R$. If $P$ is a given partition, then the induced equivalence relation $R$ is the relation for which $x\sim y$ if and only if $x,y$ are in the same set of the partition P.

Answer 2

They are "the same thing" in the sense that given an equivalence relation there is a natural way to construct a partition, and given a partition there is a natural way to construct an equivalence relation, and these two natural ways invert one another. That's useful because whenever you encounter one of these objects you are free to reason about the other if that makes your argument easier.

You are right when you say that it is the equivalence classes of an equivalence relation that form a partition (that is in fact the natural thing to look at), not the equivalence relation itself.

The natural way to construct an equivalence relation from a partition is to define two elements to be equivalent just when they are in the same block of the partition.

Answer 3

Here's a visual explanation.

Note that the nodes in the first three panels should have had edges to themselves as well (from reflexivity of equivalence relations).