0

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?

Andrés E. Caicedo
  • 79,201
Kevin Wang
  • 21
  • Where does $T$ appear in the question? – Mark Fischler Mar 13 '19 at 20:19
  • The classic way to show this is known as Cantor's diagonalisation argument – Zubin Mukerjee Mar 13 '19 at 20:21
  • It waws a 3 part question, this was part 3 (unrelated to the rohter 2 parts). – Kevin Wang Mar 13 '19 at 20:31
  • I removed the obvious noise of mentioning T, but what remains is still very poorly worded. The power set (of S) is not "the subset of S". Actually writing what things are goes a long way. In any case, no, saying that the power set of S is the collection of all subsets of S does not mean that it contains everything S has. This can be fixed by nothing that for each s in S, the singleton {s} is in P(S). But it does not matter. The fact that P(S) contains all singletons (so, in essence, a copy of S) "and more" does not mean that in fact it has larger cardinality. – Andrés E. Caicedo Mar 13 '19 at 20:52
  • @ZubinMukerjee You're confusing Cantor's diag argument with Cantor's theorem. – user4894 Mar 13 '19 at 20:58
  • Yes: "A generalized form of the diagonal argument was used by Cantor to prove Cantor's theorem" – Zubin Mukerjee Mar 13 '19 at 21:06

1 Answers1

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)$.

Robert Shore
  • 23,332