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