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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)}$


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

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

share|cite|improve this question
For the final point, see Cantor's diagonal argument; it's very classical. – Marc van Leeuwen Jan 25 '13 at 8:12
up vote 6 down vote accepted

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.

share|cite|improve this answer
Could you help me with the "prove by contradiction" in the link? The 3rd line from the end of the proof, what is "A=f(a)"? I thought A is the domain and f(a) is an element of the range. – Sean Jan 25 '13 at 6:14
$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

Your Answer


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.