# Validity of proving “No surjection from any set to the its powerset” using induction on the cardinality of powerset

I wrote a proof for "There exists NO surjection from any set to the its powerset" by induction on the cardinality. It works like this:

The cardinality of any set $N$ for $|N|=n$, $|P(N)|=2^n$

Base case: for a set with $n=1$, $1 < 2^1$

Inductive step:

-Suppose it is true that for $1\le k\le n$, $k<2^k$. Intend to prove $n+1<2^{(n+1)}$

-Then $n < 2^n$

-Then $n+1 < (2^n)+1 < (2^{n})+(2^n) = 2^{(n+1)}$

QED

My concern is that the set may be countable, so can I really assume that n<2^n without invoking any theorem relates to countability? (If so, I do not want to prove this way)

On the other hand, I saw someone prove it by contradiction from http://problemhere.wordpress.com/2011/11/02/no-surjection-to-the-power-set/

But I don't really get it. Can someone explain it to me?

-
For the final point, see Cantor's diagonal argument; it's very classical. – Marc van Leeuwen Jan 25 '13 at 8:12

Induction works for finite $n$, but you can't use it to prove that $\lvert\mathbb N\rvert\ne\lvert\mathcal P(\mathbb N)\rvert$, or that $\lvert\mathbb R\rvert\ne\lvert\mathcal P(\mathbb R)\rvert$, for example. Note that $\mathbb R$ is not even countable, so any theorem related to countably infinite sets will be of no help to you there.
$f$ is a hypothetical function that maps elements of $S$ to subsets of $S$. $A$ is one such subset. Therefore, while $A$ is a subset of the domain of $f$, it is also an element of the range of $f$. That's the key thing in the proof. – Rahul Jan 25 '13 at 6:35