Cantor's Theorem for $\Bbb N$. Hi I would like to prove this statement.
Show that there is no one-to-one correspondence from
the set of positive integers to the power set of the set of
positive integers.
[Hint: Assume that there is such a one-
to-one correspondence. Represent a subset of the set of
positive integers as an infinite bit string with ith bit 1 if i
belongs to the subset and 0 otherwise. Suppose that you
can list these infinite strings in a sequence indexed by the
positive integers. Construct a new bit string with its ith
bit equal to the complement of the ith bit of the ith string
in the list. Show that this new bit string cannot appear in
the list.]
 A: Let $S$ be the set of positive integers. Suppose there is a bijection $f : S \to P(S)$. Then every subset of $S$ is equal to $f(s)$ for some $s \in S$. For any $s\in S$, $f(s)$ is a subset of $S$, and it is certainly the case that either $s\in f(s)$ or $s\notin f(s)$. [For example, there exists $s_1$ such that $f(s_1)=
S$, and then $s_1 \in f(s_1)$; likewise, there exists $s_2$ such that $f(s_2) = \emptyset$, and then $s_2 \notin f(s_2)$.] Define $A$ to be the set of all elements $s$ of $S$ such that $s \notin f(s)$; symbolically, $$A = \{s\in S\,|\,s \notin f(s)\}.$$
(In the above notation, $s_1 \notin A$ but $s_2 \in A$.)
Certainly $A$ is a subset of $S$; that is, $A\in P(S)$. Therefore, as $f$ is a bijection, $A = f(a)$ for some $a \in S$. We now ask the question: does $a$ belong to $A$? If $a \notin A$, then $a \notin f(a)$, so by definition of $A$, we have $a \in A$. This is a contradiction. And if $a \in A$ then $a \in f(a)$, so by definition of $A$ we have $a \notin A$, again a contradiction.Thus we have reached a contradiction in any case. So we conclude that there cannot be a bijection from $S$ to $P(S)$.
A: Hint: Let $(b_1,b_2,...,b_i,...)$ denotes a new bit string. And let $(a_{i1},a_{i2},...,a_{ii},...)$ denotes the $i$th string that corresponds to the $i$th integer. Take $b_1 \neq a_{11}$, $b_2 \neq a_{22}$, ..., $b_i \neq a_{ii}$, and so on. It's called Cantor's diagonal argument.
