## 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

Sep 17

new question: numerical method (implicit) for nonlinear pde by roozbe

new question: Harshad Number by pspss

Sep 14

new problem: Geometry by parag

Aug 24

new question: Scheduling Algorithm by ncovella

new question: Scheduling Algorithm by ncovella

new question: numerical method (implicit) for nonlinear pde by roozbe

new question: Harshad Number by pspss

Sep 14

new problem: Geometry by parag

Aug 24

new question: Scheduling Algorithm by ncovella

new question: Scheduling Algorithm by ncovella

## 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.