# Proof that the set of equivalence classes of a relation on a set form a partition of that set.

I was attempting to prove the following proposition.

Proposition: Let $$A$$ be a non-empty set. Let $$I$$ be an indexing set. Let $$R$$ be an equivalence relation on $$A$$. Prove that the set of all equivalence classes of $$R$$ form a partition of $$A$$. In other words, show that for any two equivalence classes $$A_j, A_k$$ with $$j, k\in I$$ and $$A_j\ne A_k$$ we have that $$A_j\cap A_k=\emptyset$$ and $$\bigcup_{i\in I}A_i=A$$.

The following is my attempt at a proof.

Proof: Suppose that $$A_j\cap A_k\ne \emptyset$$. Then there exist $$a_1,\dots,a_n\in A_k$$ such that $$a_1,\dots,a_n\in A_j$$. Because $$R$$ is an equivalence relation, from the transitive property of $$R$$ we have that $$a_1,\dots,a_n \sim y$$ for all $$y\in A_k$$. Because $$a_1,\dots,a_n\in A_j$$, we also see that every $$y\in A_k$$ is an element of $$A_j$$. This also follows from the transitive property of $$R$$. Thus, $$A_k \subset A_j$$. By similar argument we see that $$A_j\subset A_k$$. Showing that $$A_j=A_k$$ which contradicts the hypothesis that $$A_j\ne A_k$$. Hence, $$A_j\cap A_k=\emptyset$$.

To show that $$\bigcup_{i\in I}A_i=A$$. Note that for all $$x\in A$$ we have that $$x$$ is in some equivalence class $$A_j$$ with $$j\in I$$. We also see that $$x$$ cannot be in another equivalence class $$A_k$$ as that would lead to $$A_j$$ being equal to $$A_k$$. Thus, every element $$x\in A$$ is in a unique equivalence class $$A_m$$. Hence, $$\bigcup_{i\in I}A_i=A$$.

Is the proof correct?

1. There is no reason whatsoever to have a list of elements in the intersection $$A_j\cap A_k$$; if the intersection is nonempty, then there is an element $$x\in A_j\cap A_k$$. That's all you need. And you elide the rest of the argument, which I don't find very comforting. Show that if $$y\in A_j$$, then the nonemptyness of the intersection gives $$y\in A_k$$, don't just tell me so. You need to use the fact that $$A_j$$ and $$A_k$$ are equivalence classes. Also, you showed $$A_j\subset A_k$$, not equality, so some wrods about the symmetric argument establishing the other inclusion would be good.
2. You don't specify if your set of classes, $$A_i$$, $$i\in I$$, is non-superfluous. The definition of partition just requires that if $$A_i\neq A_j$$, then $$A_i\cap A_j=\varnothing$$. This is not the same as saying that $$i\neq j$$ implies $$A_i\cap A_j=\varnothing$$, though! It is asking that different sets be disjoint, not that different labels belong to disjoint sets. For example, a standard way of defining the partition of equivalence classes of $$A$$ under $$\sim$$ is to take all sets of the form $$A_x$$, with $$x$$ ranging over all elements of $$A$$, with $$A_x = \{a\in A\mid a\sim x\}.$$ Then each element of the partition has many "labels" (one for each of its elements), but it is still a partition and still satisfies that $$A_x\neq A_y$$ implies $$A_x\cap A_y=\varnothing$$. As such, I would say that your second part is close but not quite nails down the proof. There is no reason to assume that there is a "unique" $$A_i$$ that contains $$x$$, given the definition as you have stated it. Also, saying that $$x$$ must be "in some equivalence class" is essentially asserting that $$A=\cup A_j$$, so it looks like you are invoking what you are trying to prove. Rather, $$x$$ is in the equivalence class of $$x$$ itself.