на такому спостереженні: для того щоб порівняти за кількістю елементів дві скінченні множини, зовсім необов'язково перелічувати елементи кожної з них. Можна діяти таким чином. Наприклад, необхідно порівняти за кількістю дві множини - множину S студентів та множину M всіх місць в аудиторіях факультету. Запропонуємо кожному студенту зайняти одне місце. Якщо кожен студент отримає місце і при цьому в аудиторіях не залишиться жодного вільного місця, то очевидно, що кількість елементів в обох множинах S і M однакова. У противному разі, множина S містить більше елементів ніж множина M, або навпаки. Очевидно, що запропонована процедура встановлює деяку функціональну відповідність між множинами S і M. У першому випадку ця відповідність виявляється взаємно однозначною, в той час як у другому і третьому випадках умови взаємної однозначності не виконуються: або порушується умова повної визначеності (принаймні один студент не дістав місця), або порушується умова сюр’єктивності (хоча б одне місце залишилося вільним).
Принагідно зауважимо, що багато хто з математиків вважає, що описаний простий спосіб порівняння кількостей елементів у двох скінченних множинах логічно передує виникненню поняття числа.
Кількість елементів скінченної множини 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) такий, що
0, якщо aiA',
bi =
1, якщо aiA'.
За цим правилом порожній множині 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)
3. Якщо A~B і B~C, то A~C (транзитивність).
Наведемо декілька прикладів рівнопотужних нескінченних множин.
Приклад 1.12. 1. Множина натуральних чисел N рівнопотужна множині S={1,4,9,16,...}, яка складається з квадратів натуральних чисел. Необхідна взаємно однозначна відповідність встановлюється за законом (n,n2), nN, n2S.
2. Множина Z всіх цілих чисел рівнопотужна множині P всіх парних чисел. Тут взаємно однозначна відповідність встановлюється таким чином: (n,2n), nZ, 2nP.
3. Множина точок інтервалу (-/2, /2) рівнопотужна множині точок дійсної прямої. Шукана взаємно однозначна відповідність встановлюється за допомогою тригонометричної функції tg: (x,tg x), x(-/2, /2), tg x(-,) (див. рис.1.3,а).
4. Множини точок двох довільних відрізків a і b рівнопотужні. Правило, за яким встановлюється взаємно однозначна відповідність між точками відрізків a і b різної довжини, зображено на рис.1.3,б. Кожний промінь з точки O, який перетинає відрізки a і b в точках v і w, утворює одну пару (v,w) необхідної взаємно однозначної відповідності.
5. Аналогічним чином може бути встановлена взаємно однозначна відповідність між множинами точок двох довільних квадратів K1 і K2 різних розмірів (див.рис.1.3,в).
Зауваження. З рівнопотужності довільних відрізків і транзитивності рівнопотужності можна зробити висновок, що будь-який відрізок рівнопотужний інтервалу (-/2, /2) і, значить, рівнопотужний всій прямій.
а) б) в)
Рис.1.3.
З усіх наведених прикладів випливає, що нескінченна множина може бути рівнопотужна своїй власній підмножині, що очевидно неможливо для скінченних множин. Саме незвичність і екзотичність висновків типу "множина парних чисел містить стільки ж елементів, як і множина всіх цілих чисел", "будь-який інтервал містить стільки