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

Справедливість наслідків 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),... за таким законом

( 1, якщо i(Mk,

mi(k) = (

( 0, якщо i(Mk.

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

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

M1 - m1(1), m2(1),...,mk(1),...

M2 - m1(2), m2(2),...,mk(2),...

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

Mk - m1(k), m2(k),...,mk(k),...

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

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

( 1, якщо mk(k)=0,

lk = (

( 0, якщо mk(k)=1, k = 1,2,3,....

Послідовності 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.

Кожному з таких чисел відповідають дві різні послідовності t' і t'', а отже, і два різні елементи множини ((N): один - для зображення з періодом 0, другий - з періодом 1. Позначимо через T множину тих підмножин множини N, які при побудованій вище відповідності зіставляються нескінченним двійковим дробам із періодом, T(((N). Тоді існує взаємно однозначна відповідність між множиною всіх дійсних чисел з інтервалу (0,1) і множиною ((N) \ T. Однак, оскільки множина T зліченна, то за теоремою 1.6 маємо ((N) ~ ((N) \ T. Таким чином, множина ((N), а значить і множина ((A) для будь-якої зліченної множини A, мають потужність континуум.

10. Кардинальні числа

або Card A) будемо називати деякий об’єкт для позначення потужності будь-якої множини із сукупності S.

Зокрема, для скінченної множини A кардинальним числом |A| є натуральне число, яким позначається кількість елементів будь-якої з множин сукупності S. Таким чином, можна вважати, що кардинальне число є узагальненням поняття числа елементів.

Природно виникає питання про порівняння кардинальних чисел нескінченних множин.

Нехай A і B нескінченні множини, тоді логічно можливі такі чотири випадки:

1. Iснує взаємно однозначна відповідність між A і B, тобто A ~ B і |A|=|B|.

2. Існує взаємно однозначна відповідність між множиною A і деякою власною підмножиною B' множини B. Тоді кажуть, що потужність множини A не менша від потужності множини B і записують |A|(|B|.