proof of existence of partition

Question

Let be a partition of a set . Show that there exist a set and a surjection :→ such that ={{∈∶()=}∶∈}.

How can I attempt this question?

Answer 1

Sketch of proof:

Let $C=A_1 \cup A_2 \cup \dots \cup A_n$ be this partition (one doesn't need to have a finite partition, just to simplify)

Then you can construct $f$ such that $\forall x,y\in A, \exists i \in \{1,2,\dots,n\}, x,y \in A_i \iff f(x)=f(y)$

This means that if $x,y$ are from the same part (of the partition), you construct $f$ such that their images are equal.

Then $B$ is some set including these images... (here in the finite case $B=\{1,2,\dots,n\}$.

Answer 2

Define $B$ to be the image of the bijection $g\colon \mathcal{C} \to B$ that maps each separate subset of $A$ to a distinct element of $B$. This is clearly well-defined, if by simple enumeration. Then define the function $f\colon A \to B$ as follows: $$\forall x\in A, f(x)=y \iff x\in g^{-1}(y).$$ Note that the inverse of $g$ is well-defined too, since it is a bijection. The proof that $f$ is a surjection and the given condition is satisfied follows immediately.