Cantor's theorem

In set theory, Cantor's theorem states that the set of all subsets of any set A has a strictly greater cardinality than that of A. In particular, the set of all subsets of a countably infinite set is uncountably infinite.

The proof is a quick diagonal argument. Let f be any one-to-one function from A into the set of all subsets of A. It must be shown that f is necessarily not surjective. To do that, it is enough to exhibit a subset of A that is not in the image of f. That subset is

$B=\left\{\,x\in A:x\not \in f(x)\,\right\}.$

To show that B is not in the image of f, suppose that B is in the image of f. Then for some y in A, we have f(y) = B. Now consider whether y is a member of B or not. If yεB, then yεf(y), but that implies, by definition of B, that y is notεB. On the other hand if it is not the case that yεB, then it is not true that yεf(y) and therefore it is true that yεB. Either way, we get a contradiction.