МНОЖИНИ І ВІДНОШЕННЯ

Принагідно зауважимо, що багато хто з математиків вважає, що описаний простий спосіб порівняння кількостей елементів у двох скінченних множинах логічно передує виникненню поняття числа.

Кількість елементів скінченної множини A прийнято позначати через |A|.

Таким чином, неважко переконатись, що між двома скінченними множинами A і B існує взаємно однозначна відповідність тоді і тільки тоді, коли |A|=|B|.Сформульоване твердження дозволяє розв'язувати задачу обчислення кількості елементів множини A шляхом встановлення взаємно однозначної відповідності між множиною A і деякою множиною B, кількість елементів якої відома або легко може бути визначена. Для ілюстрації цього методу доведемо наступну важливу теорему про кількість підмножин заданої скінченної множини.

Теорема 1.1. Нехай A = {a1,a2,...,an} - скінченна множина з n елементів (|A|=n), тоді кількість усіх підмножин множини A дорівнює 2n, тобто 2|A|.

Доведення. Розглянемо множину всіх кортежів (b1,b2,...,bn) довжини n, які складаються з двійкових цифр 0 або 1 (тобто biB={0,1}, i=1,2,...,n). Очевидно, що множина цих кортежів є Bn.

Встановимо таку відповідність між підмножинами множини A і кортежами з Bn. Кожній підмножині A'A поставимо у відповідність двійковий кортеж (b1,b2,...,bn) такий, що

За цим правилом порожній множині A відповідає кортеж (0,0,...,0), самій множині A - кортеж (1,1,...,1), а підмножині A' = {a2, a4 } - кортеж (0,1,0,1,0,...,0). Встановлена відповідність є взаємно однозначною. Отже кількість усіх підмножин множини A дорівнює |Bn |.

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

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

Припустимо, що |Bk-1 | = 2k-1. З того, що кожному елементові (b1,b2,...,bk-1) множини Bk-1 відповідають два елементи (b1,b2,...,bk-1,0) і (b1,b2,...,bk-1,1) множини Bk випливає, що кількість елементів у множині Bk вдвічі більша від кількості елементів у множині Bk-1.

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

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

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

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

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

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

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

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