Let function $f: \mathcal{P}(\mathbb{N}\times\{0,1\}) \rightarrow \mathcal{P}(\mathbb{N})$ be defined by $f(X) = \{2x+y\:|\:\langle x,y\rangle \in X\}$.
Prove that $f$ is bijective.
$\mathcal{P}(X)$ is a power set over $X$.
In order for function to be bijective, it has to be:
- 1-1: $f(\langle x_1,y_1\rangle) = f(\langle x_2,y_2\rangle) \Rightarrow \langle x_1,y_1\rangle = \langle x_2,y_2\rangle$
- onto: $\forall z \in \mathcal{P}(\mathbb{N}) \:\exists x,y\in\mathcal{P}(\mathbb{N}\times\{0,1\}): f(x,y) = z$
To show that $f$ is 1-1, we take any $x_1, x_2\in \mathcal{P}(\mathbb{N})$; $y_1, y_2\in \{0,1\}$ and we need to show that the first condition is true. Similarly, we need to show that the second condition is true, then it would mean that $f$ is bijective, though I do not know how to prove it step-by-step.
I also thought about other possible way of solving it. Function $h:A\rightarrow B$ is bijective iff it has an inverse function $h^{-1}:B\rightarrow A$, so I could think of a function which would satisfy this condition, but would it be a sufficient proof?
Best Answer
Hint: Each $Y \in \mathcal{P}(\mathbb{N})$ has a unique decomposition $Y = Y_0 \cup Y_1$ where $Y_0$ contains all even numbers in $Y$ and $Y_1$ contains all odd numbers in $Y$. Define $$Y_0' = \{ n/2 \mid n \in Y_0 \} ,$$ $$Y_1' = \{ (n-1)/2 \mid n \in Y_1 \} ,$$ $$g : \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N} \times \{ 0,1 \}), g(Y) = Y_0' \times \{ 0 \} \cup Y_1' \times \{ 1 \} $$ and show that $g$ is an inverse for $f$.