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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Доведення[ред.ред. код]

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

Див. також[ред.ред. код]

Література[ред.ред. код]