2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is not hard either to show that $[0,1]$ is uncountable. There is a rather simple surjection on $\mathbb{R}$. $\endgroup$ – Listing Nov 29 '11 at 8:53
  • $\begingroup$ 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. $\endgroup$ – dfeuer Jun 24 '12 at 6:34

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.