All quotations are from Moschovakis' "Notes on Set Theory," 1st edition, slightly rephrased on my own.
Before my question, here I restate a proof that $|A| < |\mathcal P(A)|$ for an infinite set $A$ (the proof actually works perfectly fine for a finite set, but I just emphasize $A$ to be infinite):
"Suppose in the contrary that there is a surjection $f : A \to \mathcal P(A)$. Let $B := \{ x \in A | x∉ f(x) \}$. As $B \subset A$ and $f$ is surjective there is some $b \in A$ such that $f(b) = B$. If $b \in B$ then (just playing around with definitions) $b ∉ B$ a contradiction. Similarly, $b ∉ B$ implies $b \in B$, again a contradiction."
I skipped some details as they are quite elementary.
I completely get the proof, but I am having trouble understanding the remark following this proof:
"A careful examination will reveal that this proof is a fairly straightforward generalization of the diagonal method of proof by which Cantor showed thay the set of infinite binary sequences is uncountable."
Here is my question:
How is the above proof a generalization of Cantor's diagonal method?
You can imagine infinite binary sequences are just representing whether element $i$ is in a set: (So for the sequence starting with 00100..., 0 and 1 are not in the set, 2 is in the set 3 is not and so on.)
Now, Cantor's argument is that you start from $i=0$, flip the $i$th bit, increment $i$, repeat, and now concatenate those bits. This element is not mapped by any $i$ (since it disagrees on some bit), so contradiction.
Now, look at what the concatenated string represents: it has 1 in locations where $i$ mapped to a string with 0 at index $i$ and 0 otherwise. But what does mapping to a string with 0 at index $i$ mean in set notation? That $f(i)$ did not contain $i$. So, you essentially constructed the set $B$ in your question. The contradiction follows similarly (replace 0 and 1 by "if it didnt belong, it now belongs; if it did, then it now doesn't).
Let me try to simplify the argument in a more step-by-step approach:
1) Every infinite binary string can be viewed as a member of the power set of the integers, with 1 representing belonging in the set.
2) Cantor's diagonal argument goes through each string $i$ and flips the $i$th bit: in set notation this corresponds to changing the membership of the $i$th bit on the domain.
3) In the diagonal argument, then you concatenate these new bits; if you check the new string in set notation, you just created the set $B$ in your question since if in the $i$th spot this new string has a $1$, that means originally it mapped to a string that had a $0$ on that spot, i.e. it was an element that didn't map to a set that contained itself (and converse is the same).
4) You know that noone maps to this string because this string is different from all the other strings. This is now similar to why $B$ is not mapped as well by the step (3) argument; if it mapped to itself, it would have had a 1 on spot $i$ but now it has a 0 on that spot (and the converse).