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?
Best Answer
The basic ideas are fine, but there are some assumptions that are not made explicit and make it a bit weak, and there are some issues with the presentation.
Comments:
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.
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.