[Math] Consider P a partition of set A. Given relation R on A and xRy if and only if x, y $\in$ X for some X $\in$ P. Show R is equivalence relation on A

elementary-set-theoryequivalence-relationsrelationsset-partition

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$.

Best Answer

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$.

Related Question