edited by
625 views
1 votes
1 votes
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.]$
edited by

2 Answers

0 votes
0 votes
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.
0 votes
0 votes
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

Related questions

0 votes
0 votes
0 answers
1
admin asked Apr 21, 2020
235 views
We say that a function is computable if there is a computer program that finds the values of this function. Use question $37$ and $38$ to show that there are functions th...
0 votes
0 votes
0 answers
3