## You are here

Homeproof of Cantor's theorem

## Primary tabs

# proof of Cantorβs theorem

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 $X$ to its power set. Then we define the set $Z\subseteq X$ as follows:

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

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

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

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

Keywords:

diagonal argument

Major Section:

Reference

Type of Math Object:

Proof

Parent:

## Mathematics Subject Classification

03E17*no label found*03E10

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

Oct 19

new correction: examples and OEIS sequences by fizzie

Oct 13

new correction: Define Galois correspondence by porton

Oct 7

new correction: Closure properties on languages: DCFL not closed under reversal by babou

new correction: DCFLs are not closed under reversal by petey

new question: Lorenz system by David Bankom

Oct 2

new correction: Many corrections by Smarandache

Sep 28

new question: how to contest an entry? by zorba

new question: simple question by parag

Sep 26

new question: Latent variable by adam_reith

new correction: examples and OEIS sequences by fizzie

Oct 13

new correction: Define Galois correspondence by porton

Oct 7

new correction: Closure properties on languages: DCFL not closed under reversal by babou

new correction: DCFLs are not closed under reversal by petey

new question: Lorenz system by David Bankom

Oct 2

new correction: Many corrections by Smarandache

Sep 28

new question: how to contest an entry? by zorba

new question: simple question by parag

Sep 26

new question: Latent variable by adam_reith

## Comments

## infinite sets

You proved that |P(X)| is bigger than |X|, because you can't find any x so that F(x)=Z.

But what does it means for infinite sets |P(X)|=|X|+1 ?

It's like saying that natural numbers are more numerous than even numbers. You're right, but they have the same cardinal.