1.6. Нескінченні множини

Зчисленні та континуальні множини, потужність

У дискретній математиці, як і у всій математиці, в природознавстві дуже важлива Р°ль натурального ряду чисел N={1, 2, ...}. Хоча практично обчислення завжди виконуються зі скінченним відрізком {1, 2, .-, п} Цієї нескінченної множини, немає можливості вказати найбільше число п, яке не буде перевершене у всіх випадках життя. Тому доводиться досліджувати властивості всієї нескінченної множини чисел N. На дійсній числовій вісі R натуральні та цілі числа утворюють доволі «розріджені» підмножини N, Z (рис. 1.13), які інтуїтивно можна назвати «дискретні»- Множина раціональних чисел Q, що утворюються при діленні цілих чисел т/п, щільно розташовується на дійсній вісі R- інтервал (а, b) як завгодно малої довжини ε =b-а (а  b) містить нескінченну множину різних раціональних точок. Чи можна множину Q вважати «дискретною»? Виявляється так, хоча інтуїція відмовляється це визнати.

Рис. 1.13. Натуральні, цілі та раціональні числа на вісі R

Нарешті, вся дійсна вісь R — явно неперервна множина, і тут інтуїтивний висновок нас не підводить. Для строгого визначення дискретних та неперервних нескінченних множин використовуються зіставлення дискретних множин натуральному ряду чисел, а неперервних множин — відрізку [0, 1] дійсної вісі. Необхідно тільки уточнити термін «зіставити». Мається на увазі встановити взаємно однозначну відповідність.

Поняття взаємно однозначної відповідності є первинним у свідомості людини при диференційованому сприйнятті предметів зовнішнього світу. Якщо зал для глядачів заповнений і немає вільних місць, нам не обов'язково рахувати кількість присутніх глядачів, вона дорівнює числу крісел у залі. Щоб зробити цей висновок, ми інтуїтивно використовуємо наявність взаємно однозначної відповідності між глядачами і кріслами. Відзначимо одну особливість: фактично у цьому випадку реалізована конкретна взаємно однозначна відповідність глядачі — крісла (кожному глядачеві відповідає одне і тільки одне визначене крісло і навпаки). Після перерви деякі глядачі можуть помінятися місцями, і конкретна відповідність стане іншою, але висновок залишиться попереднім: число глядачів дорівнює числу місць.

Визначення

Взаємно однозначною називається така відповідність між множинами А і В, при якій кожному елементу а  А відповідає один і тільки один елемент b  В, і кожному елементу b  В відповідає один і тільки один елемент а  А. Функція, що визначає взаємно однозначну відповідність, називається бієктивною функцією або бієкцією.

Визначення

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

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

Для нескінченної множини строге поняття потужності не вводиться, але сам термін «потужність» використовується для позначення властивості, загальної для всіх еквівалентних множин. Якщо дві нескінченні множини А і В еквівалентні (А ~ В), то рівність їх потужностей формально записується як |А| = |В|.

Визначення

Множина А називається зчисленною, якщо вона еквівалентна натуральному ряду N (А ~ N). Термін «зчисленність» є точним замінником інтуїтивного поняття — «дискретність».

За допомогою бієкції φ = N → А можна «перелічити» всі елементи а з А, привласнивши їм індекси за правилом φ(n) = а_п. Можна записати, що А = {а_п, п=1, 2, ...}. Множини парних натуральних чисел N₄ = {2, 4, ..., т, ...}, всіх натуральних чисел N = {1, 2, ..., п, ...}, цілих чисел Z і раціональних чисел Q послідовно вкладені: N_ч  N  Z  Q. Хоча для будь-яких двох з цих множин немає рівності, вони еквівалентні одна одній, тобто мають однакову потужність і є зчисленними: |N_ч| = |N| = |Z| = |Q|. Тому відповідно до наших угод множини N_ч, N, Z, Q є дискретними.

Дійсно, еквівалентність N ~ N_ч аргументується за допомогою бієкції φ(n) = 2п : 2п = т. Множину цілих чисел Z можна «перелічити» (тобто присвоїти його елементам натуральні індекси) за правилом:

m n	1	2	3	4	…
1	1/1	2/1	3/1	4/1	…
2	1/2	2/2	3/2	4/2	…
3	1/3	2/3	3/3	4/3	…
4	1/4	2/4	3/4	4/4	…
…	…	…	…	…	…

Рис. 1.14. Таблиця множини Q₊

0 = z₁; 1 = z₂; -1 = z₃;

2 = z₄; -2 = z₅; 3 = z_6; …

Отже Z ~ N.

Для доведення еквівалентності множин Q і N достатньо вказати правило нумерації множини Q₊ додатних раціональних чисел, що утворяться діленням т/п натуральних чисел т і п.

Пронумеруємо стовпці та рядки нескінченної таблиці індексами т і п відповідно (рис. 1.14).

Будемо нумерувати послідовно числа п/т вздовж пунктирних похилих стрілок, починаючи з лівого верхнього кута таблиці і переходячи після проходження кожної стрілки до сусідньої, більш довгої. При цьому пропускаються відношення т/п, чисельні значення яких зустрічалися раніше:

Таким чином, множина Q раціональних чисел зчисленна:

Звичайно, існують нескінченні незчисленні множини, та їх потужність природно вважати більшою за |N|. Так, множина точок відрізка [0, 1] = {х  R; 0  х  1} не є зчисленною (теорема Г. Кантора). її потужність називається континуум і позначається малою буквою с: |[0, 1]| = с. Сама множина [0, 1] і будь-яка еквівалентна їй множина називаються континуальними.

Виявляється, що на дійсній вісі R континуальними (тобто еквівалентними одна одній і відрізку [0, 1]) є, наприклад, множини [а, b], (а, b), при будь-якому а < b; (0, +); множина (- , +), що дорівнює R.

Континуальні також множини точок будь-якого квадрату та кругу на площині R², паралелепіпеду та кулі у просторі R³ і самого простору R³: |R| = |R²| = |R³| = с.

Завдання

1. Довести такі твердження:

1. Із будь-якої нескінченної множини можна виділити зчисленну підмножину.

2. Будь-яка нескінченна підмножина зчисленної множини також зчисленна.

3. Сума (об'єднання) скінченної та зчисленної множин є зчисленна множина.

4. Об'єднання скінченного числа зчисленних множин є зчисленна множина.

2. Яка потужність множини многочленів будь-яких степенів з цілими коефіцієнтами?

3. Дійсне число називається алгебраїчним, якщо воно є коренем деякого многочлена з цілими коефіцієнтами. Всі інші числа називаються трансцендентними. Яка потужність множини алгебраїчних чисел?

22