S is a possibly infinite set. Prove |S| < |P(S)|

Question

Suppose S is a set. Do not assume that S is finite. How can one prove that |S|<|P(S)|? (P(S) is the power set of S).

Would I say something how the power set is the subset of S so that it contains everything S has but more?

Answer 1

Assume $f:S \rightarrow \mathscr P(S)$ is $1-1$. Then it can’t be surjective because $\{x \in S~|~x \notin f(x)\}$ can’t be in the range of $f$. If that set were $f(y)$ for some $y$, then we find $y \in f(y) \iff y \notin f(y)$.