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

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

Доведення

Припустимо, що існує множина $~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}$), тому $\exists 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.(рос.)

• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)