Kenneth Rosen Edition 7 Exercise 2.5 Question 40 (Page No. 177)

Question

Show that if $S$ is a set, then there does not exist an onto function $f$ from $S$ to $P(S),$ the power set of $S$. Conclude that $\mid S\mid  < \mid P(S)\mid .$ This result is known as Cantor’s theorem. [Hint: Suppose such a function $f$ existed. Let $T = \{s \in S \mid s \notin f (s)\}$ and show that no element $s$ can exist for which $f (s) = T.]$

Answer 1

S to P(S) no onto function is possible. because if |S|=n then |P(S)|=2^n. and these two can never be equal. always |S| <|P(S)|. but onto function condition is if there is an onto function from A to B then |A|>=|B|. but here the case is just reverse. hence S to P(S) no onto function is possible.

Answer 2

see in simple words

lets take an example

s{1,2,}

p(s)={phai,{1},{2},{1,2}}

now in onto  BASE CONDITION IS IF THERE EXIST A ONTO FXN BETWEEN A TO B THEN  |A|>=|B|

but s to p(s)  condn gets fails so

 

ONTO (SURJECTION) NOT POSSIBLE HERE