Consider $P$, a partition of a set $A$. Define a relation $R$ on $A$ such that $x\mathrel{R}y$ if and only if $x, y \in X$ for some $X \in P$. Show that $R$ is an equivalence relation on $A$. Next show that $P$ is the set of equivalence classes of $R$.

For the first part, proving $R$ is an equivalence relation on $A$: I think I understand how $R$ is reflexive and symmetric. Since $X$ is a set with a partition, every element in that set is related to itself and related to each other so $R$ is by definition reflexive and symmetric. Can I use the same rationale for transitivity?

If this is right, I'm having trouble formalizing these relationships in the form of a proof.

I'm also completely lost on the second part. I don't see how I can prove that $P$ is the set of equivalence classes of $R$.


Each element $a \in A$ is in a unique part in $P$; let's call it $X_a$. So, if $x$ and $y$ are both in a part $X$, and $y$ and $z$ are both in a part $Z$, then $X$ and $Z$ are both equal to $X_y$. So, $x$ and $z$ are both in $X_y$, so $x \mathrel{R} z$.

As far as $P$ being the set of equivalence classes: it's pretty much the definition. The equivalence class for $a \in A$ is the set of elements equivalent to $a$, i.e. the set $\{ y \in A \mid \exists X \in P : a, y \in X\} = \{y \in A \mid y \in X_a\}$. Since $a$ is contained in a unique part $X_a$, the elements equivalent to $a$ are exactly those in the set $X_a$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.