Proving the equivalence relation

Question

Let ∼ be a relation on set $A$. The followings are claimed to be equivalent:

1. ∼ is reflexive, symmetric, and transitive

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

3. $∃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)

Answer 1

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

Answer 2

For the function from $A$ to a set of subsets that partitions $A$, try assigning each $a \in A$ to the set it's in.

Answer 3

A good choice for $B$ is indeed the disjoint equivalence classes given by (2). Consider the function $f$ that maps elements of $A$ to the equivalence class it belongs to (a member of $B$). We are guaranteed that $a \in A$ belongs to some equivalence class; this is from the definition of “partition” of the set $A.$ Furthermore, $a$ cannot belong to more than one equivalence class, because of the fact that the classes are disjoint. Thus $f$ is well-defined.

To show that this function satisfies $x \sim y \iff f(x) = f(y)$ is simple; just show both directions. If $x \sim y,$ then by (2) there exists an equivalence class $A_i$ such that $x \in A_i$ and $y \in A_i.$ It follows that $f(x) = f(y) = A_i.$ In the other direction, $f(x) = f(y)$ implies that $x$ and $y$ belong to the same equivalence class. Then, clearly, there exists an equivalence class to which $x$ and $y$ both belong, and by (2) we know that $x \sim y.$ And the implication (2) -> (3) is proved.