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.

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?

share|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
add comment

1 Answer

up vote 5 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|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
1  
$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
add comment

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.