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.

  • 0
    Apologies to Paul; our edits got crossed, it appears.2011-11-29
  • 6
    These should probably be two separate questions.2011-11-29
  • 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.2011-11-29
  • 0
    @Zev Chonoles: no problem! Your edit looks better!2011-11-29
  • 2
    The only true reason that the questions should be made separate is because each is a duplicate of a different question.2011-11-29
  • 1
    Question about P(N): http://math.stackexchange.com/questions/77656/is-the-power-set-of-the-natural-numbers-countable Both can also be found at proofwiki: http://www.proofwiki.org/wiki/Composite_of_Bijections and http://www.proofwiki.org/wiki/Powerset_of_Natural_Numbers_Not_Countable2011-11-29
  • 0
    Actually, for _any_ set $S$, $\mathcal{P}(S)$ is a larger set than $S$. I think Cantor first proved this, but I may be mistaken. The proof is by contradiction, and is very short. Assume the negation. Then there is a surjection $g:S\to\mathcal{P}(S)$. Define $A \subset S$ by $A=\{y \in S \mid y \not\in g(y)\}$. Then $A$ is not in the range of $g$: if you assume $g(x)=A$, it leads to a contradiction.2013-09-30

2 Answers 2

3

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.

3

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.

  • 0
    It is not hard either to show that $[0,1]$ is uncountable. There is a rather simple surjection on $\mathbb{R}$.2011-11-29
  • 0
    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.2012-06-24