Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Apologies to Paul; our edits got crossed, it appears. –  Zev Chonoles Nov 29 '11 at 7:13
4  
These should probably be two separate questions. –  Austin Mohr Nov 29 '11 at 7:14
1  
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
2  
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
1  

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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