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 ε B or not. If y ε B, then y ε f(y), but that implies, by definition of B, that y not ε B. On the other hand if it is y not ε B, then y not ε f(y) and therefore y not ε B. Either way, we get a contradiction.