# proof of Cantor’s theorem

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

Consider a function $F: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\notin 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\iff x\notin F(x)\iff x\notin Z$$ |

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

Title | proof of Cantor’s theorem |
---|---|

Canonical name | ProofOfCantorsTheorem |

Date of creation | 2013-03-22 12:44:55 |

Last modified on | 2013-03-22 12:44:55 |

Owner | Wkbj79 (1863) |

Last modified by | Wkbj79 (1863) |

Numerical id | 7 |

Author | Wkbj79 (1863) |

Entry type | Proof |

Classification | msc 03E17 |

Classification | msc 03E10 |