Let $A$ be a set and suppose that $R$ and $R'$ are two equivalence relations in $A$ that induce the same partition $\mathcal{P}$. Prove that $R=R'$.
I am not sure how to start but I want to believe that I need the fundamental theorem of equivalence relations. Any help will be aprecciated.
Best Answer
If $Q$ is a partion of $A$ then each $x\in A$ is is precisely one block of the partition $Q$.
Now every equivalence relationship on $A$ induces a partition of $A$ so that for any two $x,y \in A$ then $x,y$ are in the same block of $Q$ if and only if $x R y$.
If $R$ and $R'$ both induce the same partition $Q$, then for any $x,y\in A$ then $x R y$ if and only if $x,y$ are in the same block. ANd $x R' y$ if an only if $x,y$ are in the same block. So $x R y$ if and only if $x R'y$.
So $R = R'$.
This was not meant to be a difficult problem. Once you accept that equivalence relations partition a set, and that a partition induces an equivalence relationship this result is basically inevetible.
=====
It's almost a definition.
Remember that $R \subset A\times A$ so that certain things can be said.
If $(x,y) \in R$ then $x R y$ which means $x,y$ are in the same set of the partition that $R$ induces. But as $R'$ induces the same partition as $R$ so $x,y$ are in the same set of the partition that $R'$ induces, and $x R' y$ and $(x,y) \in R'$. So $R \subset R'$.
Likewise if $(x,y) \in R'$ then $x R' y$ and $x, y$ are in the same set of the partitions. So $x Ry$ and $(x,y) \in R$ and $R'\subset R$.
So $R = R'$.
=====
To be a little more formal:
A partition of $A$ is set of sets, $\mathscr P= \{P_i\}$ were $A = \cup_{P_i\in \mathscr P} P_i$ and the $P_i$ are mutually disjoint.
An equivalence relationship, $R$, on $A$ is a subset of $A\times A$, with the following properties i) Reflexive: for all $x \in A$, $(x,x)\in \mathbb R$. ii) symmetric: $(x,y) \in R\iff (y,x) \in R$. iii) Transitive if $(x,y) \in R$ and $(y,z) \in R$ then $(x,z)\in R$. (We use the notation $x R y$ if $(x,y) \in R$.
It's basic property that: If we define $[x]=\{y\in A| (x,y) \in R\}$ then $\mathscr R = \{[x]|x\in A\}$ is a partition of $A \iff R$ is an equivalence relationship on $A$.
Pf: If $R$ is an equivalence relationship then for any $x$ we have $(x,x) \in R$ so $x \in [x]$ and so $x\in \cup_{[x]\in \mathscr R}[x]$ so $A\subset \cup_{[x]\in \mathscr R}[x]$. And obviously as $[x]\subset A$, $\cup_{[x]\in \mathscr R}[x]=A$ so $A = \cup_{[x]\in \mathscr R}[x]$.
And if $[x]\cap [y]\ne \emptyset$ then there is a $w\in [x]$ and $w\in [y]$. But then $(x,w)\in R, (y,w)\in R$ and reflexivity, symmetry, transitivity assures $(x,x),(y,y),(w,w), (w,x),(w,y), (x,y), (y,w) \in R$. And $[x]=\{z\in A|(x,z)\in R\}$ but if $(x,z)\in R$ then $(y,x)\in R$ so $(y,z)\in R$ so $[x]\subset [y]$ and vice versa. So $[x]=[y]$. So the $[x]\in \mathscr R$ are disjoint.
So $\mathscr R$ is a partition.
The reverse direction is just as easy to show.
......
So to the question.
If $R$ and $R'$ are equivalence relations that evoke the same partition, $\mathscr Q$.
Then if $W\in \mathscr Q$ then there is an $x\in A$ where $W= \{y\in A|(x,y)\in R\}= \{y\in A|(x,y)\in R'\}$ and we can denote this partition $[x]$.
So $(x,y) \in R\implies y\in [x] \implies (x,y) \in R' \implies y\in [x]\implies (x,y)\in R$.
So $(x,y)\in R\iff (x,y)\in R'$ so $R=R'$.