МНОЖИНИ І ВІДНОШЕННЯ

Доведення. Очевидно, що множина M \ A незліченна. Якби множина M'=M \ A була зліченною, то за теоремою 1.4 множина M = M' A була б також зліченною, що суперечило б умові теореми. Тоді за теоремою 1.2 множина M' містить зліченну підмножину B (BM \ A). Позначимо C=(M\A)\B, тоді маємо M \ A=BC і M=(AB)C. Множина AB зліченна. Тоді з рівнопотужностей B~(AB) і C ~ C, а також того, що CB= і C(AB)=, випливає співвідношення BC~B)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 також незліченна множина. Тоді за теоремою 1. 6 (M A) \ A ~ M A, тобто M ~ M  A, оскільки (MA) \ A = M.

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

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

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

Справедливість наслідків 1.6.2 і 1.6.3 випливає з континуальності множин R і C всіх дійсних і комплексних чисел відповідно, зліченності множин усіх раціональних і всіх алгебраїчних чисел та теореми 1.6.

Із доведених теорем випливає також рівнопотужність інтервалів (0,1) ~ [0,1) ~ (0,1] ~ [0,1].

Сформульована нижче теорема встановлює певний зв'язок між зліченними і континуальними множинами і у своєму доведенні знову використовує діагональний метод Кантора.

Теорема 1.7. Множина (A) всіх підмножин зліченної множини A має потужність континуум.

Доведення. Оскільки всі зліченні множини рівнопотужні множині N натуральних чисел, то достатньо довести континуальність булеана (N) множини N. Маючи взаємно однозначну відповідність між множиною N і деякою множиною A, неважко побудувати взаємно однозначну відповідність між їхніми булеанами (N) і (A).

Проведемо доведення теореми методом від супротивного. Припустімо, що множина (N) зліченна й існує нумерація всіх її елементів, тобто (N)={M1,M2,...,Mk,...}, де MkN, k=1,2,.... Поставимо у відповідність кожній множині Mk послідовність tk з нулів і одиниць m1(k), m2(k),...,mi(k),... за таким законом

Очевидно, ця відповідність є взаємно однозначною.

Розташуємо всі елементи множини (N) і відповідні їм послідовності у порядку нумерації:

Використовуючи діагональний метод Кантора, побудуємо нову послідовність L з нулів і одиниць l1,l2,..., lk,... таку,

Послідовності L відповідає деяка підмножина MN, а саме M={ n | ln=1, n=1,2,...}. Очевидно, підмножина M не входить у вказаний перелік M1,M2,...,Mk,..., оскільки послідовність L відрізняється від кожної з послідовностей tk принаймні в одній k-й позиції. Отже, і множина M відрізняється від кожної з множин Mk, k=1,2,.... Ця суперечність означає, що не існує переліку для елементів множини (N). Таким чином, множина (N) незліченна.Крім того, кожній послідовності tk можна поставити у відповідність нескінченний двійковий дріб 0,m1(k)m2(k)...mk(k)..., який зображує деяке дійсне число з інтервалу (0,1) у двійковій системі числення. I навпаки, будь-яке число з інтервалу (0,1) можна однозначно записати у вигляді нескінченного двійкового дробу. Виняток становлять числа зі зліченної множини раціональних чисел, які записуються за допомогою скінченних двійкових дробів і тому можуть мати дві різні форми зображення у вигляді нескінченних двійкових дробів - з періодом 0 і періодом 1.