Show that the set of all subsets of an infinite enumerable set is not enumerable

Question

I know this problem involves using Cantor's theorem, but I'm not sure how to show that there are more subsets of an infinite enumerable set than there are positive integers. It seems like a lot of these problems are really the same problem, but they require some unique and creative thought to get them just right. Any idea how I can solve these more quickly? What train of thought do you go though when working with this specific example?

Answer 1

Given an enumerable set $S=\{x_1,x_2,\ldots\}$, and an infinite sequence of 0's and 1's, $\{b_1,b_2,\ldots\}$, we can associate a subset of $S$ consisting of those $x_i$ for which $b_i=1$. This is a bijection between colection of subsets of $S$ and infinite binary sequences. These binary sequences can be through of as base 2 representation of all real numbers between 0 and 1, hence it is uncountable.

Answer 2

Another way to clear it more is to considerer an enumerable set $ S = \{s_1, s_2, ..., s_n \}$; now, it's evident that we can take the first digit from $s1$, the second digit from $s_2$, and so on, such that we'll have a new $s$ that isn't in the set, and more, even if we wanted to include it in the set, we would have a new possibility to do it all again; hence the set of all subsets is uncountable; another way to see it, is considering these $s$'s as the representation of the numbers in the interval $(0,1 )$ as binary representations, which is a non-enumerable set clear

$ s1 = (+0, 0, 0, 0, 0, 0, 0, ...)\\ s2 = (1, +1, 1, 1, 1, 1, 1, ...)\\ s3 = (0, 1, +0, 1, 0, 1, 0, ...)\\ s4 = (1, 0, 1, +0, 1, 0, 1, ...)\\ s5 = (1, 1, 0, 1, +0, 1, 1, ...)\\ s6 = (0, 0, 1, 1, 0, +1, 1, ...)\\ s7 = (1, 0, 0, 0, 1, 0, +0, ...)\\ ... \\ s = (1, 0, 1, 1, 1, 0, 1, ...)$

obs.: we are using the $+$ sign as a form to highlight the fact we are forming a new number according to the rule we've mentioned above.

The proof was given by Cantor, and the method is known as Cantor's diagonal method. The link for it is in:

https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument