Теорема Кантора

Припустимо, що існує множина ${\displaystyle ~A}$, потужність якої є рівною потужності множини ${\displaystyle ~2^{A}}$, тобто існує бієкція ${\displaystyle ~f(x):A\to 2^{A}.}$

Розглянемо множину ${\displaystyle B=\left\{x\in A:\;x\not \in f(x)\right\}.}$ Оскільки ${\displaystyle ~f}$ бієкція та ${\displaystyle B\subseteq A}$ (тобто ${\displaystyle B\in 2^{A}}$), тому ${\displaystyle \exists y\in A:\;f(y)=B}$.

Подивимось, чи може ${\displaystyle ~y}$ належати ${\displaystyle B}$. Якщо ${\displaystyle y\in B}$, то ${\displaystyle y\in f(y)}$, а тоді, за визначенням ${\displaystyle B}$ ${\displaystyle y\not \in B}$. І навпаки, якщо ${\displaystyle y\not \in B}$, то ${\displaystyle y\not \in f(y)}$, а отже ${\displaystyle y\in B}$.

У будь-якому випадку, одержуємо суперечність. Отже, початкове припущення помилкове і потужність ${\displaystyle ~A}$ менша потужності ${\displaystyle ~2^{A}}$.

• Парадокс Кантора

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ, 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)
• Куратовский К., Мостовский А. Теория множеств. — Москва : Мир, 1970. — 416 с.(рос.)