Show that $S$ and $2^{S}$ are not equinumerous. (Not bijective?) I have tried to look for a problem the same as mine, but I have not been too lucky, or if I did I had trouble applying that solution to my problem. Any help would be appreciated. I know how to solve this problem, but I'm afraid it would someone "cheap" because it is just a fact I found. 
Let $S$ be any set.  Let $2^{S} =\{f\mid f\colon S\to\{0,1\}\}$. Then $S$ and $2^{S}$ are not equinumerous. 
Now, I believe the "cheap" way I found out how to do this is to use the fact that the there is a bijection between $2^{S}$ and $\mathcal{P}(S)$, but there is no bijection between a set and it's power set. 
I was given a hint to assume there is a bijection $f\colon S\to2^{S}$, and to copy the method used in Cantor's Theorem. I went through this theorem a few weeks ago. Also, I just looked at in my text and on Proofwiki, but I am still having trouble. 
Edit: I forgot to mention I am just taking an introductory logic class. The only thing we have done with Cantor's Theorem is prove that the powerset of integers is non enumerable. 
 A: In Cantor's theorem, as well as here, you don't need to assume towards contradiction that there is a bijection.
HINT: The proof of Cantor's theorem says that given a function $F\colon S\to\mathcal P(S)$, then the set $D_F=\{s\in S\mid s\notin F(s)\}$ is not in the image of $F$. Translate this $D_F$ into a binary string indexed by $S$.
(Conclude from this that there cannot be a surjective function, let alone a bijection function, between the two sets.)
A: $S$ a set of people, $F\colon S \to \mathcal{P}(S)$, $F(s) = \{\text{people shaved by } s \}$. Consider the barber $b$,  somebody who shaves exactly those people who do not shave themselves, i.e. $F(b) = \{ s \ | \ s \not \in F(s) \}$.  Does the barber shave himself? Or not? 
Obs: The barber's paradox should ask the yes/no question:" does the barber shave himself?" rather than : " who shaves the barber?" . There could be several people shaving the same person ( compare  with other actions). 
A: Equivalently, you can prove there is no surjective function $f: S\to 2^S$. See my formal proof of this at Cantor's Theorem in the DC Proof format.
A: *

*Combine Cantor's theorem with prop 1.17.19 to show $X\nsim 2^X$



