Множини і відношення (стр. 5 из 12)

З теорем 1.2 і 1.3, зокрема, випливає, що зліченні множини є до певної міри найпростішими нескінченними множинами, бо, з одного боку, вони містяться в будь-якій нескінченній множині, а з другого - містять в собі тільки скінченні множини, або нескінченні множини, які є зліченними.

Теорема 1.4. Об’єднання скінченної або зліченної сукупності зліченних множин є зліченною множиною.

Доведення. Розглянемо спочатку скінченну сукупність зліченних множин {A₁,A₂,...,A_k}, де A_i={a₁ⁱ,a₂ⁱ,...,a_nⁱ,...}, i=1,2,...,k. Запишемо всі елементи множин A₁,A₂,...,A_k в рядок таким чином: a₁¹,a₁²,...,a₁^k,a₂¹,a₂²,...,a₂^k,...,a_n¹,a_n²,...,a_n^k,....

Перенумеруємо записані елементи в порядку їх розташування в рядку. При цьому елемент, який вже одержав свій номер і повторно з'являється в рядку, з подальшої нумерації вилучається. В результаті кожен елемент об’єднання одержить свій номер, що і потрібно було довести.

У випадку зліченної сукупності множин A_i={a₁ⁱ,a₂ⁱ,...,a_nⁱ,...}, i=1,2,..., перепишемо всі елементи множин A_i у такому порядку: a₁¹,a₁²,a₂¹,a₁³,a₂²,a₃¹,a₁⁴,a₂³,a₃²,a₄¹,....

Принцип переписування елементів множин A зображений за допомогою стрілок на рис.1.4.

a₁¹, a₂¹, a₃¹, ..., a_n¹,.... A₁

a₁², a₂², a₃², ..., a_n²,.... A₂

a₁³, a₂³, a₃³, ..., a_n³,.... A₃

a₁⁴, a₂⁴, a₃⁴, ..., a_n⁴,.... A₄

...................................

Рис. 1.4.

Далі проводимо міркування аналогічні випадку скінченної сукупності множин. Теорему доведено.

З теореми 1.4 випливає низка цікавих наслідків.

Наслідок 1.4.1. Множина Z всіх цілих чисел зліченна.

Справді, подамо множину Z у вигляді Z = NÈ {0} ÈN'¢, де N'¢ = { -1,-2,-3,... } - множина від’ємних цілих чисел, яка, очевидно, є зліченною.

Числова множина W називається щільною, якщо для будь-якої пари чисел a,bÎW (a<b) завжди існує число cÎW таке, що a<c<b.

Безпосередньо з означення випливає, що щільна множина завжди є нескінченною. Більш того, для кожної пари чисел a,bÎW існує безліч чисел cÎW, для яких виконується a<c<b.

Очевидно, що множина Z цілих чисел, а також будь-яка її підмножина (зокрема, множина N натуральних чисел) - не щільні. У той же час множина Q раціональних чисел є щільною множиною. Справді, для будь-яких раціональних чисел r₁ і r₂ (r₁<r₂) число r=(r₁+r₂)/2 задовольняє нерівності r₁<r<r₂. Зокрема, для всіх чисел r' з нескінченної множини раціональних чисел {r₁+(r₂-r₁)/2ⁱ | i=1,2,...} виконуються нерівності r₁<r' <r₂.

Здавалося б зі щільності множини раціональних чисел повинно було б випливати, що ця множина має більшу потужність, ніж множина N або множина Z. Однак має місце таке твердження.

Наслідок 1.4.2. Множина Q всіх раціональних чисел зліченна.

Справді, множину Q можна подати як об’єднання таких зліченних множин:

A₁ = {0,1,-1,2,-2,3,-3,...} - усі цілі числа (або дроби виду , nÎZ),

A₂ = {} - усі дроби виду , nÎZ.

A₃ = {} - усі дроби виду , nÎZ,

.....................................................

A_k = {} - усі дроби виду , nÎZ,

......................................................

Наслідок 1.4.3. Декартів добуток A´B зліченних множин A і B є зліченною множиною.

Справедливість цього твердження випливає з того, що множину всіх пар (a,b)ÎA´B, де A={a₁,a₂,...,a_n,...} і B={b₁,b₂,...,b_n,...} можна подати як об’єднання такої зліченної сукупності зліченних можин

D₁ = {(a₁, b₁ ), (a₁, b₂ ),..., (a₁, b_n ),... },

D₂ = {(a₂, b₁ ), (a₂, b₂ ),..., (a₂, b_n ),... },

...........................................

D_k = {(a_k, b₁ ), (a_k, b₂ ),..., (a_k, b_n ),... },

...........................................

Зокрема, множина всіх точок координатної площини з раціональними координатами зліченна.

Наслідок 1.4.4. Декартів добуток P_n=A₁´A₂´...´A_n зліченних множин A₁, A₂,..., A_n - є зліченною множиною для довільного n.

Доведення проведемо методом математичної індукції.

Для n=1 P₁=A₁ і справедливість твердження випливає з умови зліченності множини A₁. Нехай P_k-1=A₁´A₂´...´A_k-1 - зліченна множина. Тоді зліченність множини P_k = P_k-1´A_kвипливає з наслідку 1.4.3.

Наслідок 1.4.5. Множина P усіх многочленів p(x) = a₀xⁿ+a₁x^n-1+...+a_n-1x+a_n з раціональними коефіцієнтами a_iÎQ, i=0,1,...,n, n=0,1,2,..., є зліченною множиною.

Множину P можна подати у вигляді об’єднання зліченної сукупності множин P_n, де P_n - це множина многочленів з раціональними коефіцієнтами, степінь яких не перевищує n, n=0,1,2,.... Разом із тим, будь-якому многочлену p(x)=a₀xⁿ+a₁x^n-1+ ...+a_n-1x+a_n з множини P_nможна поставити у відповідність кортеж (a₀,a₁,a₂,...,a_n), який складається з раціональних чисел a_i - коефіцієнтів цього многочлена. Очевидно, ця відповідність є взаємно однозначною. Отже, P_n ~ Qⁿ⁺¹. Тоді з наслідків 1.4.2 і 1.4.4 випливає, що множина P_n - зліченна, а тому зліченною є і множина P.

Назвемо число алгебраїчним, якщо воно є коренем деякого многочлена з раціональними коефіцієнтами. Відомо, що кожен такий многочлен має скінченну кількість коренів (не більшу від степені многочлена). Таким чином, множину всіх алгебраїчних чисел можна подати у вигляді об’єднання зліченної сукупності скінченних множин. Отже, має місце

Наслідок 1.4.6. Множина всіх алгебраїчних чисел зліченна.

Наслідок 1.4.7. Множина A всіх слів у заданому скінченному алфавіті A зліченна.

Справедливість твердження випливає з того, що

A^* = {e} ÈAÈA²ÈA³È...,

тобто множина A^* є зліченним об’єднанням скінченних множин {e} і Aⁿ, де Aⁿ - множина всіх слів довжини n в алфавіті A.

9. Незліченні множини

Наступні питання, які логічно випливають із висловленого вище припущення про рівнопотужність усіх нескіченних множин: чи всі нескінченні множини зліченні, або чи існують нескінченні множини, які не будуть зліченними? Факт існування множин, які не є зліченними (незліченних множин), вперше був встановлений Г.Кантором за допомогою запропонованого ним діагонального методу, який набув згодом фундаментального значення в різних розділах математики. Зокрема, цей метод лежить в основі доведення наступної важливої теореми, яка належить Г.Кантору.

Теорема 1.5. Множина всіх дійсних чисел з інтервалу (0,1) незліченна.

Доведення. Відомо, що кожному дійсному числу з інтервалу (0,1) можна поставити у відповідність нескінченний десятковий дріб 0,a₁a₂a₃.... Для ірраціональних чисел цей нескінченний десятковий дріб є неперіодичним. Для кожного раціонального числа, яке зображується скінченним десятковим дробом, з двох можливих варіантів запису його у вигляді нескінченного періодичного десяткового дробу (з періодом 0 або періодом 9) зафіксуємо період 9. Наприклад, число 0,123 (або 0,123000...) будемо записувати у вигляді 0,122999..., а число 0,7 - у вигляді 0,699.... Очевидно, що запропонована відповідність буде взаємно однозначною.

Проведемо доведення теореми методом від супротивного. Припустімо, що сформульоване твердження хибне і множина всіх дійсних чисел з інтервалу (0,1) зліченна. Тобто існує нумерація цих чисел x₁,x₂,...,x_n,.... Перепишемо у вигляді нескіченних десяткових дробів усі числа з інтервалу (0,1) в порядку їхньої нумерації

x₁ = 0, a₁₁a₁₂a₁₃... a_1n...,

x₂ = 0, a₂₁a₂₂a₂₃... a_2n...,

x₃ = 0, a₃₁a₃₂a₃₃... a_3n...,

...............................

x_n = 0, a_n1a_n2a_n3... a_nn...,

...............................

Рухаючись по діагоналі (вказаної стрілками), утворимо новий нескінченний десятковий дріб 0,b₁b₂...b_n... такий, що b₁¹a₁₁, b₂¹a₂₂,...,b_n¹a_nn,.... Додатково для того, щоб уникнути ситуації з можливістю зображення одного й того ж раціонального числа у двох формах, будемо вибирати значення цифр b_i так, щоб b_i¹0 і b_i¹9, i=1,2,.... Утворений дріб є записом деякого дійсного числа y з інтервалу (0,1), однак він не належить розглядуваній зліченній множині. Справді, побудований дріб відрізняється від кожного з дробів нашої нумерації x₁,x₂,...,x_n,... принаймні однією цифрою. Точніше, y¹x_n тому, що дроби y і x_n відрізняються принаймні n-ю цифрою після коми (n=1,2,...). З одержаної суперечності випливає, що не існує переліку для множини всіх дійсних чисел з інтервалу (0,1). Отже, припущення щодо її зліченності хибне і розглядувана множина - незліченна. Теорема доведена.