Let ∼ be a relation on set $A$. The followings are claimed to be equivalent:
-
∼ is reflexive, symmetric, and transitive
-
there exists a partition of $A$ into disjoint equivalence classes $A$, such that $x ∼ y$ if and only if $∃i : x ∈ A_i ∧ y ∈ A_i$
-
$∃B∃f : A → B$ such that $x ∼ y$ if and only if $f(x) = f(y)$
I want to prove that each statement follows from the preceding statement. For example, 1 -> 2, 2-> 3, 3->1.
I can't figure out ways to prove 2->3 directly.
(I think it is right to start with set $B$ as the set of all equivalence classes of $A$. But setting a function between A and B doesn't come to my intuition well)
Best Answer
Outline hints:
$2 \implies 3$.
Let $B = \{A_i\}$ be the disjoint partition described in $2$.
Let $f(x) = A_i$ where $x \in A_i$.
You must show this well defined function by showing that for $x\in A$ that i) $x \in$ some $A_i$ (that's what partition means) and ii) the each $x \in $ one specific $A_i$ only (that's what disjoint means).
Then you must show $f(x) = f(y)\iff x\sim y$. But $f(x) = f(y)$ is defined to meant $x,y\in A_i$ for the same specific $A_i$ and the condition of 2) so $x,y\in $ the same $A_i$ if and only if $x \sim y$.
$3 \implies 1$.
If $f(x) =f(y) \iff x\sim y$ the to prove the relation $\sim$ is reflexive, symmetric and transitive you must for that the relation of $f(x) = f(y)$ is refelxive, symmetric and transitive. That is $f(x) =f(x)$ for all $x$; that if $f(x)=f(y)$ then $f(y)=f(x)$ and that if $f(x)=f(y)$ and $f(y)=f(z)$ then $f(x)=f(z)$; which are so trivial you don't need to do anything.
$1 \implies 2$.
For each $x$ define $A_x=\{y\in A| x\sim y\}$.
We can prove that if $x\sim y$ then $A_x =A_y$.
If $z\in A_x$ then $x\sim z$ and $z\sim x$ and $x \sim y$ so $z\sim y$ and $y\sim z$ so $z \in A_y$. And if $w \in A_y$ then by the same argument $w \in A_y$ so $A_x =A_y$.
This shows the classes are disjoint ($z\in A_x\cap A_y\implies A_x=A_y$) and that $x\sim y\iff x,y \in A_x=A_y$.