# Proof that the power set of $\mathbb{N}$ is uncountable, and that the composition of two bijections is a bijection

How do I prove the power set of natural numbers, $\mathcal{P}(\mathbb{N})$, the collection of subsets of $\mathbb{N}$ (natural number set) is uncountable? I am thinking the approach is to contradict an initial assumption that there is a function $f$ that maps $\mathbb{N} \to \mathcal{P}(\mathbb{N})$.

How do I prove that the composition of 2 bijections is a bijection? So, if $f: A \to B$ and $g: B \to C$ are bijections, then $(g \circ f): A \to C$ is also a bijection.

Help appreciated! Thank you.

-
Apologies to Paul; our edits got crossed, it appears. – Zev Chonoles Nov 29 '11 at 7:13
These should probably be two separate questions. – Austin Mohr Nov 29 '11 at 7:14
I agree with Austin. As even the mods don't have the ability to separate things like that, I ask the OP (original poster), LiveYourLife, to ask about the composition of two bijections in a separate question. – Zev Chonoles Nov 29 '11 at 7:16
The only true reason that the questions should be made separate is because each is a duplicate of a different question. – Asaf Karagila Nov 29 '11 at 7:37

This is a corollary of the classic Cantor's theorem. Not necessary, but it is not hard to show that, in fact, $\#(2^\mathbb{N})=\#(\mathbb{R})$.

For your second question merely note that $(f\circ g)^{-1}$ exists, namely because $g^{-1}\circ f^{-1}$ "works". Try it and you'll see what I mean.

-

If you know that $[0,1]$ is uncountable, this isn't to hard:

For your first question, consider the set $B$ of all numbers in $[0,1]$ written in binary notation. There is a natural way to define an onto map from $\cal P(\Bbb N)$ to $B$ (for $A$ in $\cal P(\Bbb N)$ set the $n$th digit of its image equal to 1 if $n\in A$ and 0 otherwise) . $B$ is uncountable. So $\cal P(\Bbb N)$ is uncountable.

A bijection from $\cal P(\Bbb N)$ to $B$ can be constructed with a bit more care.

Let $f:B\rightarrow D$ and $g:A\rightarrow B$ be bijections.

Let $d\in D$. There is a $b\in B$ with $f(b)=d$ and there is a $a\in A$ with $g(a)=b$. Then $(f\circ g)(a)=d$,. So, $f\circ g$ is onto.

Now $(f\circ g)(x)=(f\circ g)(y)\ \Rightarrow\ g(x)=g(y)\ \Rightarrow\ x=y$; which shows $f\circ g$ is 1-1.

-
It is not hard either to show that $[0,1]$ is uncountable. There is a rather simple surjection on $\mathbb{R}$. – Listing Nov 29 '11 at 8:53
I really don't think assuming [0,1] (or ℝ) is uncountable is terribly reasonable if you're trying to prove that P(ℕ) is uncountable. I think Alex Youcis has the right approach here. – dfeuer Jun 24 '12 at 6:34