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

Теорема Кантора — твердження у теорії множин, що потужність довільної множини є меншою, ніж потужність її булеану (множини всіх її підмножин). Названа на честь німецького математика Георга Кантора.

Доведення

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

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

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

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

Див. також

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

Література

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