Skip to content

Cantor’s Diagonal Argument

September 12, 2011

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

Suppose f: A \to P(A) 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 B=\{a \in A : a \not\in f(a) \}. Suppose now there exists b in A with f(b) = B. Since B is a subset of A, either b is in B or not.

If b is in B, then, by definition of B, b is not in f(b) = B.

If b 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

From → Class Topics

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: