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

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

Доведення

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

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