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

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

Доведення

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

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

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

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

Див. також

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

Література

• Шаблон:Хаусдорф.Теория множеств
• Шаблон:Куратовский.Мостовский.Теория множеств