PlanetMath: proof of Cantor's theorem

(more info)

Math for the people, by the people.

Main Menu

proof of Cantor's theorem

(Proof)

The proof of this theorem is fairly simple using the following construction, which is central to Cantor's diagonal argument.

Consider a function $F\colon X\to {\mathcal P}(X)$ from a set to its power set. Then we define the set $Z\subseteq X$ as follows:

$\displaystyle Z = \{x\in X \mid x\not\in F(x)\}$

Suppose that is a bijection. Then there must exist an $x\in X$ such that . Then we have the following contradiction:

$\displaystyle x\in Z \Leftrightarrow x\not\in F(x) \Leftrightarrow x\not\in Z$

Hence, cannot be a bijection between and ${\mathcal P}(X)$ .

"proof of Cantor's theorem" is owned by Wkbj79. [ full author list (2) | owner history (1) ]

(view preamble)

Keywords:

diagonal argument

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: contradiction, bijection, power set, function, Cantor's diagonal argument
There are 3 references to this entry.

This is version 4 of proof of Cantor's theorem, born on 2002-06-05, modified 2007-08-08.
Object id is 3053, canonical name is ProofOfCantorsTheorem.
Accessed 11653 times total.

Classification:

AMS MSC:	03E17 (Mathematical logic and foundations :: Set theory :: Cardinal characteristics of the continuum)
	03E10 (Mathematical logic and foundations :: Set theory :: Ordinal and cardinal numbers)

Pending Errata and Addenda

None.[ View all 1 ]

Discussion

forum policy

No messages.

Interact