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

Для n=1 P1=A1 і справедливість твердження випливає з умови зліченності множини A1. Нехай Pk-1=A1A2...Ak-1 - зліченна множина. Тоді зліченність множини Pk = Pk-1Ak випливає з наслідку 1.4.3.

Наслідок 1.4.5. Множина P усіх многочленів p(x) = a0xn+a1xn-1+...+an-1x+an з раціональними коефіцієнтами aiQ, i=0,1,...,n, n=0,1,2,..., є зліченною множиною.

Множину P можна подати у вигляді об’єднання зліченної сукупності множин Pn, де Pn - це множина многочленів з раціональними коефіцієнтами, степінь яких не перевищує n, n=0,1,2,.... Разом із тим, будь-якому многочлену p(x)=a0xn+a1xn-1+ ...+an-1x+an з множини Pn можна поставити у відповідність кортеж (a0,a1,a2,...,an), який складається з раціональних чисел ai - коефіцієнтів цього многочлена. Очевидно, ця відповідність є взаємно однозначною. Отже, Pn ~ Qn+1. Тоді з наслідків 1.4.2 і 1.4.4 випливає, що множина Pn - зліченна, а тому зліченною є і множина P.

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

Наслідок 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, b2a22,...,bnann,.... Додатково для того, щоб уникнути ситуації з можливістю зображення одного й того ж раціонального числа у двох формах, будемо вибирати значення цифр bi так, щоб bi0 і bi9, i=1,2,.... Утворений дріб є записом деякого дійсного числа y з інтервалу (0,1), однак він не належить розглядуваній зліченній множині. Справді, побудований дріб відрізняється від кожного з дробів нашої нумерації x1,x2,...,xn,... принаймні однією цифрою. Точніше, yxn тому, що дроби 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 (BM \ A). Позначимо C=(M\A)\B, тоді маємо M \ A=BC і M=(AB)C. Множина AB зліченна. Тоді з рівнопотужностей B~(AB) і C ~ C, а також того, що CB= і C(AB)=, випливає співвідношення BC~(AB)C, тобто M \ A ~ M.

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

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

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

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

Якщо M незліченна множина, то M A також