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?

  • $\begingroup$ Yes, both approaches work. But you have to do it. It is not that difficult. $\endgroup$ – Paul Frost Dec 13 '18 at 17:53
  • $\begingroup$ 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. $\endgroup$ – whiskeyo Dec 13 '18 at 18:47

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.