I just came across the fact that if a non-empty set $A$ has a partition $\{A_i|i\in I\}$(where $I$ is some indexing set) then there is an equivalence relation on $A$ whose equivalence classes are precisely the sets in the partition. I was attempting to prove this and would appreciate if someone could confirm if the proof is correct.
Proof: Define a relation $R$ on $A$ by $(x, a)\in R$ if and only if $x, a\in A_m$ where $A_m$ is a set in the partition of $A$. It follows that these elements can't be in any other set as all the sets are disjoint.
This relation is reflexive as $(x, x)\in R$.
This relation is also symmetric as $(x, a)\in R$ and $(a, x)\in R$.
This relation is also transitive as if $(x, a)\in R$ and $(a, y)\in R$. That implies that $y$ is in the same set as $x$ and $a$. Thus, $(x, y)\in R$.
Hence, $R$ is an equivalence relation.
Is this the correct way to prove this?
Best Answer
You have the right idea, but I feel some explanation is lacking.
I would rewrite the definition of $R$ a bit more formally, for the sake of making it perfectly clear. I would say $$(x,a) \in R \iff (\exists !\,m \in I)(x \in A_m \text{ and } a \in A_m)$$ This makes it clearer to me that $x,a$ must lie in the same partite set. While clarity is certainly a subjective issue, I think it would also make proof-writing for this easier.
You claim the result for reflexivity without proving or explaining anything. Let's focus in a little. Reflexivity would mean that, $\forall x$, we have $(x,x) \in R$. We have an underlying partition, so given $x \in A$, for a unique $i \in I$, $x \in A_i$. Well, $x \in A_i$ and $x \in A_i$ (for that $i$), however redundant-sounding on the tongue, is a true statement, so $(x,x) \in R$.
You claim the result of symmetry likewise: you state it, but argue nothing for it. So, symmetry requires that $$ (x,a) \in R \implies (a,x) \in R $$ We begin by assuming, then $(x,a) \in R$ as a given. Well, $x \in A_m$ and $a \in A_m$ (for the relevant $m$) is given by definition, and logically equivalent to $a \in A_m$ and $x \in A_m$, which means $(a,x) \in R$, giving the symmetry.
You do at least explain the argument a bit with the transitive case, and have the right idea. $(x,a),(a,y) \in R$ means that, for some $m,n$, $x \in A_m, a \in A_m, a \in A_n, y \in A_n$. But since $\{A_i\}_{i \in I}$ partitions $A$, then $A_m = A_n$, i.e. $m=n$. Thus, $x \in A_m, a \in A_m, y \in A_m$, and by the first and last, $(x,y) \in A_m$, as desired.