Доклад: Множини і відношення

Методом математичної індукції доведемо, що |Bⁿ | =2ⁿ .

Для n =1 маємо B ¹ = B і |B | = 2 = 2¹ .

Припустимо, що |B^{k -1} | = 2^{k -1} . З того, що кожному елементові (b ₁ ,b ₂ ,...,b_{k -1} ) множини B^{k -1} відповідають два елементи (b ₁ ,b ₂ ,...,b_{k -1} ,0) і (b ₁ ,b ₂ ,...,b_{k -1} ,1) множини B^k випливає, що кількість елементів у множині B^k вдвічі більша від кількості елементів у множині B^{k -1} .

Тобто |B^k | =|B^{k -1} |*2 =2^{k -1} *2 = 2^k . Теорема 1.1 доведена.

Множину всіх підмножин деякої множини A (скінченної або нескінченної) часто позначають через b (A ) і називають булеаном множини A . З доведеної теореми випливає, що для скінченної множини A виконується | b (A )|= 2^{|A |} .

Множини A і B назвемо рівнопотужними або множинами, які мають рівні (однакові) потужності, якщо існує взаємно однозначна відповідність між множинами A і B .

Таким чином, дві скінченні множини A і B мають однакову потужність тоді та лише тоді, коли вони складаються з однакової кількості елементів. Отже, поняття потужності є узагальненням поняття кількості елементів множини.

Зверніть увагу на те, що ми не означили безпосередньо поняття "потужність множини", а лише дали означення рівнопотужності множин. Кантор пропонував розуміти під потужністю ту спільну властивість, яку мають всі рівнопотужні множини. Виходячи з того, що для рівнопотужних скінченних множин такою спільною властивістю є кількість їхніх елементів, за аналогією переносять цю властивість на нескінченні множини, що, взагалі кажучи, не зовсім коректно, в чому ми переконаємось нижче.

Якщо рівнопотужність множин A і B позначити через A ~B , то безпосередньо з означення випливають такі властивості рівнопотужності:

1. A ~A (рефлексивність);

2. Якщо A ~B , то B ~A (симетричність); (1.9)

3. Якщо A ~B і B ~C , то A ~C (транзитивність).

Наведемо декілька прикладів рівнопотужних нескінченних множин.

Приклад 1.12. 1. Множина натуральних чисел N рівнопотужна множині S ={1,4,9,16,...}, яка складається з квадратів натуральних чисел. Необхідна взаємно однозначна відповідність встановлюється за закон