Множини і відношення, Детальна інформація

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

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

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

A* = {e} ( A ( A2 ( A3 (...,

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

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

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

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

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

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

x1 = 0, a11 a12 a13 ... a1n...,

x2 = 0, a21 a22 a23 ... a2n...,

x3 = 0, a31 a32 a33 ... a3n...,

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

xn = 0, an1 an2 an3 ... ann...,

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

Рухаючись по діагоналі (вказаної стрілками), утворимо новий нескінченний десятковий дріб 0,b1b2...bn... такий, що b1( a11, b2(a22,...,bn(ann,.... Додатково для того, щоб уникнути ситуації з можливістю зображення одного й того ж раціонального числа у двох формах, будемо вибирати значення цифр bi так, щоб bi(0 і bi(9, i=1,2,.... Утворений дріб є записом деякого дійсного числа y з інтервалу (0,1), однак він не належить розглядуваній зліченній множині. Справді, побудований дріб відрізняється від кожного з дробів нашої нумерації x1,x2,...,xn,... принаймні однією цифрою. Точніше, y(xn тому, що дроби y і xn відрізняються принаймні n-ю цифрою після коми (n=1,2,...). З одержаної суперечності випливає, що не існує переліку для множини всіх дійсних чисел з інтервалу (0,1). Отже, припущення щодо її зліченності хибне і розглядувана множина - незліченна. Теорема доведена.

Будь-яка множина, рівнопотужна множині всіх дійсних чисел з інтервалу (0,1), називається континуальною, або множиною потужності континуум.

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

Теорема 1.6. Якщо M - незліченна множина, а A - скінченна або зліченна підмножина множини M, то множини M\A і M рівнопотужні, тобто

M \ A ~ M.

Доведення. Очевидно, що множина M \ A незліченна. Якби множина M'=M \ A була зліченною, то за теоремою 1.4 множина M = M' ( A була б також зліченною, що суперечило б умові теореми. Тоді за теоремою 1.2 множина M' містить зліченну підмножину B (B(M \ A). Позначимо C=(M\A)\B, тоді маємо M \ A=B(C і M=(A(B)(C. Множина A(B зліченна. Тоді з рівнопотужностей B~(A(B) і C ~ C, а також того, що C(B=( і C((A(B)=(, випливає співвідношення B(C~(A(B)(C, тобто M \ A ~ M.

Сформулюємо декілька наслідків, які випливають із доведених теорем.

Наслідок 1.6.1. Якщо M - нескінченна множина, а множина A - скінченна або зліченна, то M ( A ~ M.

Будемо вважати, що M(A=(. Якщо M(A((, то у доведенні можна використати скінченну або зліченну множину A' = A \ M таку, що M(A=M(A' і M(A' =(.

Якщо M зліченна множина, то M(A також зліченна множина (теорема 1.4), отже M ( A ~ M.

Якщо M незліченна множина, то M ( A також незліченна множина. Тоді за теоремою 1. 6 (M ( A) \ A ~ M ( A, тобто M ~ M ( A, оскільки (M(A) \ A = M.

Наслідок 1.6.2. Множина всіх ірраціональних чисел континуальна.

Число, яке не є коренем жодного многочлена з раціональними коефіцієнтами, називається трансцендентним.

Наслідок 1.6.3. Множина всіх трансцендентних чисел континуальна.