Зліченні множини

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

Потужність нескінченної множини

Визначити кількість елементів скінченної множини просто: підрахуємо їх. Отже, множина M = {a, b, c, d, e} має 5 елементів, записуємо |M| = 5.

З нескінченними множинами ситуація значно складніша. Як порівняти потужності нескінченних множин? Чи можливо це взагалі, чи всі нескінченні множини «однаково великі»?

Для прикладу візьмімо множину натуральних чисел і множину парних натуральних чисел. Маємо множини ℕ = {1, 2, 3, 4, 5, 6, …} і S = {2, 4, 6, …}. Хочеться сказати, що множина натуральних чисел більша за множину парних чисел, бо натуральні числа містять усі парні числа і ще якісь елементи додатково — непарні числа.

Тож ми могли б записати, що S ⊂ ℕ, тобто множина S є власною підмножиною множини ℕ. І могли б сказати, що якщо S ⊂ ℕ, то множина ℕ більша — адже вона містить більше елементів, ніж множина S.

Одна з причин, чому не можна вимірювати множини за відношенням підмножини, полягає в тому, що множини можуть мати різну кількість елементів, хоча жодна з них не є підмножиною іншої. Це можна показати вже на скінченних множинах: A = {1, 3, 4, 9} і B = {b, u, r, z, m}. Маємо: |A| = 4 і |B| = 5. Множина B більша за множину A, але A ⊂ B не виконується. У випадку нескінченних множин це видно на парних і непарних числах. Жодна з цих множин не є підмножиною іншої.

Отже, відношення підмножини не підходить для того, щоб вирішувати, чи одна множина більша за іншу.

Бієкція

Спробуймо інший підхід. Маємо дві множини, A і B. Можемо сказати, що вони мають однакову потужність, якщо між ними існує бієктивне відображення. Що це означає? Беремо елемент множини A, елемент множини B і утворюємо пару (a; b). Ці елементи з множин вилучаємо і продовжуємо. Якщо вдається «спорожнити» обидві множини, то ми знайшли бієктивне відображення.

Приклад на скінченних множинах: A = {a, b, c} і B = {1, 2, 3}. Перша пара могла б бути (a; 1), наступна (b; 2) і нарешті (c; 3). Ми вичерпали всі елементи обох множин, тож знайшли бієктивне відображення. Важливо, що це не єдине бієктивне відображення. Ось ще один правильний варіант: (a; 3), (b; 1), (c; 2).

З нескінченними множинами все вже трохи цікавіше. Спробуймо непарні й парні натуральні числа. Інтуїтивно відчуваємо, що їх має бути порівну. Спробуємо. Беремо перше непарне число і відображаємо його на перше парне: (1; 2). Далі друге непарне й друге парне: (3; 4). І так далі. Отримуємо пари: (1; 2), (3; 4), (5; 6), (7; 8), … Можна записати, що кожне непарне число l відображається на парне число l + 1, а кожне парне число s є образом непарного числа s − 1. Для кожного непарного і для кожного парного числа маємо пару, яка містить це число. Отже, множини непарних і парних чисел мають однакову потужність.

Парні й натуральні числа

Тепер спробуємо той самий підхід і порівняємо множину натуральних і парних чисел. Маємо множини ℕ = {1, 2, 3, 4, 5, 6, …} і S = {2, 4, 6, …}. Інтуїтивно очікуємо, що множина натуральних чисел буде більшою.

Однак спробуймо знайти бієктивне відображення. Можемо сказати, що кожне натуральне число n відображається на своє подвоєне, на 2n. Так отримуємо пари (1; 2), (2; 4), (3; 6), (4; 8), (5; 10), … Для кожного натурального числа n маємо пару (n; 2n), а для кожного парного числа s маємо пару (s/2; s). Ми знайшли бієктивне відображення, тож множина парних чисел і множина натуральних чисел рівнопотужні, тобто мають однакову потужність.

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

Порівняння з натуральними числами

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

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

Легко побачити, що парні й непарні натуральні числа зліченні, адже ми вміємо визначити перше, друге, третє тощо парне/непарне число. А парні цілі числа? Тобто множина S = {…, −4, −2, 0, 2, 4, …}. Чи можемо їх упорядкувати? Можемо: достатньо взяти те саме впорядкування, що й раніше, і одразу після додатного парного числа записати його від'ємний варіант: S = {0, 2, −2, 4, −4, 6, −6, …}. Аналогічно, наприклад, для цілих чисел.

Потужність множини раціональних чисел

Цікавіший приклад — раціональні числа, дроби. Чи можемо їх упорядкувати? Можемо, але це вже трохи складніше. Побудуємо таблицю, що має нескінченно багато рядків і стовпців. У кожній клітинці буде дріб. У n-му стовпці та m-му рядку матимемо дріб n/m. Тобто в 1-му стовпці та 2-му рядку маємо $\frac12$, а в третьому стовпці та четвертому рядку маємо 3/4.

$$\begin{array}{ccccc} 1/1&2/1&3/1&4/1&…\\ 1/2&2/2&3/2&4/2&…\\ 1/3&2/3&3/3&4/3&…\\ 1/4&2/4&3/4&4/4&…\\ …&…&…&…&… \end{array}$$

Як тепер ці числа впорядкувати, пронумерувати? Ми не можемо нумерувати їх по рядках чи по стовпцях, бо одразу «втонемо» в одному рядку/стовпці. Натомість беремо числа по діагоналях: (перша діагональ:) 1/1, (друга діагональ:) 2/1, 1/2, (третя діагональ:) 3/1, 2/2, 1/3, (четверта діагональ:) 4/1, 3/2, 2/3, 1/4, … Там ще чимало повторюваних дробів, але це не заважає. Більше заважає те, що там немає від'ємних чисел. Це легко виправити: щоразу, записавши якийсь дріб, одразу після нього ставимо його від'ємний варіант. І тоді на самому початку бракує лише нуля. Ось і все: ми маємо всі раціональні числа в послідовності.

Загалом отримуємо послідовність: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Потужність множини дійсних чисел

Чи дійсних чисел стільки ж, скільки натуральних? Відповісти буде ще складніше, ніж у випадку раціональних чисел. Проведемо доведення від супротивного. Припустімо, що дійсні числа зліченні й існує бієктивне відображення на натуральні числа. Тобто припустімо, що їх можна впорядкувати. І нехай наступна таблиця — це і є таке впорядкування:

$$\begin{array}{ccccccccc} 0,&3&5&2&2&4&6&0&\ldots\\ 0,&2&9&2&4&3&7&5&\ldots\\ 0,&7&2&3&0&8&4&5&\ldots\\ 0,&1&4&3&7&9&0&6&\ldots\\ 0,&0&8&6&5&7&5&8&\ldots\\ 0,&7&5&4&6&3&6&3&\ldots\\ 0,&3&4&1&9&7&0&0&\ldots\\ \ldots \end{array}$$

У таблиці наведено перші сім дійсних чисел нашого впорядкування. Це впорядкування, звісно, може бути довільним, числа не обов'язково розташовані за зростанням.

За припущенням, у цій нескінченній таблиці впорядковано всі дійсні числа. (Таблиця знову нескінченна, тут лише перші сім записів.) Тепер ми спробуємо знайти/побудувати таке число, яке є дійсним, але не міститься в цій таблиці. Якщо ми таке число знайдемо, це буде суперечність із тим, що в таблиці є всі дійсні числа, звідки зробимо висновок, що множина дійсних чисел не є зліченною.

Те число, якого в таблиці немає, побудуємо так:

$$\begin{array}{ccccccccc} 0,&\fbox{3}&5&2&2&4&6&0&\ldots\\ 0,&2&\fbox{9}&2&4&3&7&5&\ldots\\ 0,&7&2&\fbox{3}&0&8&4&5&\ldots\\ 0,&1&4&3&\fbox{7}&9&0&6&\ldots\\ 0,&0&8&6&5&\fbox{7}&5&8&\ldots\\ 0,&7&5&4&6&3&\fbox{6}&3&\ldots\\ 0,&3&4&1&9&7&0&\fbox{0}&\ldots\\ \ldots \end{array}$$

Починаємо з того, що записуємо 0,… Так наше нове дійсне число виглядатиме на початку. На першому десятковому місці буде така цифра, якої немає на першому місці в першому дійсному числі нашого впорядкування (у таблиці це виділено рамкою). Там цифра 3, тож оберемо, наприклад, 1 і отримаємо число 0,1…

Продовжуємо. На другому місці буде цифра, якої немає на другому місці другого дійсного числа. Там 9, тож, наприклад, 2. Отримаємо число 0,12… На третьому місці буде цифра, відмінна від третьої цифри третього дійсного числа. Там 3, тож оберемо, скажімо, 7. Отримаємо 0, 127…

І так далі й так далі. На n-й позиції нового числа завжди буде цифра, відмінна від цифри, що стоїть на n-й позиції n-го числа нашого впорядкування.

Що ми цим отримуємо? Отримуємо число, яке відрізняється від усіх чисел нашого впорядкування принаймні однією цифрою. Візьмімо останній проміжний результат: 0,127… Це число точно відрізняється від першого числа нашого впорядкування принаймні першою цифрою — бо ми так його побудували. Від другого числа воно відрізняється принаймні другою цифрою. Від третього — третьою цифрою. Загалом це нове число відрізняється від числа впорядкування, що стоїть на n-му місці, принаймні цифрою на n-й позиції.

Отже, щойно побудованого числа в таблиці ми не знайдемо, хоча вона мала зображати бієкцію між натуральними та дійсними числами. Тому дійсних чисел більше, ніж натуральних. Множина дійсних чисел не зліченна — вона незліченна.