# Let function $f$ be defined by $f(X)$. Prove that $f$ is bijective.

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?

• Yes, both approaches work. But you have to do it. It is not that difficult. – Paul Frost Dec 13 '18 at 17:53
• This is why I asked for help, I mentioned that I cannot prove it step-by-step using first method, as I do not know how should I start it and what I have to do next (sadly proofs are not my strong point). When it comes to the second method with finding the inverse function, I am trying to get it, but all my ideas were wrong. I was thinking about $f^{-1}(n) = n$ for $n\in N$, but it does not contain whole $\{0,1\}$ set, as it is $f^{-1}(n) = n + 0$ in every case. – whiskeyo Dec 13 '18 at 18:47

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