# Cantor’s Diagonal Argument

This argument is maybe less confusing than the one I gave in class today.

Suppose is a mapping from $latex A$ to its power set. We want to show that $latex f$ *cannot *be onto, i.e. there exists a subset $latex B$ of $latex A$ that is not in the range of $latex f$.

We define . Suppose now there exists in with . Since is a subset of , either is in or not.

If is in , then, by definition of , is not in .

If is not in $latex B$, then, since $latex B = f(b)$, $latex b$ is not in $latex f(b)$ and hence, since $latex f(b) = B$, $latex b$ is in $latex B$.

In both cases we obtain a contradiction, hence such $latex b$ cannot exist, and $latex f$ is not onto.

Advertisements

Leave a Comment