Расин, Алгебра

Предложение 5.22. Объединение счетного семейства счетных множеств является счетным множеством.

Д о к а з а т е л ь с т в о. Пусть Ai, i N, – произвольное семейство счетных множеств. Определим множества Bi, i N, следующим образом:

B1 = A1, Bi = Ai \ (A1 A2 . . . Ai−1) при i > 2.

Проверим, что множества Bi попарно не пересекаются. В самом деле, пусть j < k и b Bj . Поскольку Bj Aj , элемент b содержится в Aj . Но Bk Ak \ Aj , поэтому b 6Bk.

Покажем теперь, что имеет место равенство

Так как Bi Ai при любом i N, правая часть равенства (7) содержится в его левой части. Проверим обратное включение. Пусть a S∞i=1 Ai и Ak – множество с наименьшим номером, содержащее

a. Тогда a 6A1 A2 . . . Ak−1. Поэтому a Bk, и, следовательно, a S∞i=1 Bi.

Каждое из множеств Bi конечно или счетно. Поэтому существует инъективное отображение fi : Bi −→ N. Определим отображение

∞

[

f : Bi −→ N × N

i=1

следующим способом: если b Bi, то f (b) = (i, fi(b). Правило f на самом деле задает отображение, поскольку Bi попарно не пересекаются. Кроме того, нетрудно проверить, что это отображение

Предложение 5.23. Множество Q всех рациональных чисел счетно.

Д о к а з а т е л ь с т в о. Обозначим через Q+ (соответственно Q−) множество всех положительных (соответственно отрицательных) рациональных чисел. Всякое положительное рациональное

100

число можно представить в виде несократимой дроби m/n, где m, n N. Поставив в соответствие каждой несократимой дроби m/n упорядоченную пару (m, n), мы получим инъективное отображение из Q+ в N × N. Отсюда вытекает, что Q+ счетно. Поскольку существует очевидное биективное отображение из Q+ на Q−, множество Q− также счетно. Так как Q = Q+ {0} Q−, получаем, что Q – счетное множество.

Предложение 5.24. Если X – счетное множество, то для каждого натурального n множество Xn счетно.

Д о к а з а т е л ь с т в о. Применим метод математической индукции. Поскольку X1 = X, при n = 1 утверждение выполнено. Пусть n = k > 1 и Xk счетно. Поскольку существует биективное отображение из Xk × X на Xk+1, при помощи теоремы 5.5 получаем, что Xk+1 также счетно.

Предложение 5.25. Если X – счетное множество, то множество Xf in всех конечных последовательностей, составленных из элементов множества X, счетно.

Для доказательства этого утверждения достаточно заметить, что множество Xf in всех конечных последовательностей равно

S

Xn. Применение предложения 5.24 и теоремы 5.5 показывает, что это множество счетно.

О п р е д е л е н и е. Бесконечная последовательность (xn) называется периодической, если существуют такие k, l > 1, что xm+l = = xm при любом m > k .

Выберем наименьшие k, l, обладающие свойством, сформулированным в определении. Тогда конечные последовательности x1, x2, . . . , xk и xk+1xk+2 . . . xk+l называются соответственно непериодической частью и периодом данной бесконечной последовательности. Например, бесконечная последовательность

(3, 4, 1, 2, 8, 5, 6, 4, 2, 8, 5, 6, 4, . . . , 2, 8, 5, 6, 4, . . .)

является периодической, причем k = 3, l = 5, непериодическая часть равна (3, 4, 1), а период равен (2, 8, 5, 6, 4).

101

Предложение 5.26. Если X – счетное множество, то множество всех бесконечных периодических последовательностей, составленных из элементов множества X, счетно.

Д о к а з а т е л ь с т в о. Пусть Xp – множество всех бесконечных периодических последовательностей, составленных из элементов множества X. Каждая последовательность (xn) из Xp однозначно определяет непериодическую часть и период. Тем самым задано отображение из Xp в прямое произведение Xf in ×Xf in. Поскольку непериодическая часть и период определяют последовательность также однозначно, указанное отображение инъективно. Из теоремы 5.5 и предложения 5.25 следует, что Xf in × Xf in – счетное множество. Так как построено инъективное отображение из Xp в счетное множество, можно заключить, что Xp также счетно.

5.7. Равномощность множеств

Пусть X, Y – произвольные непустые множества.

Если существует инъективное (соответственно биективное) отображение из X в Y , то говорят, что мощность X не больше мощности Y (соответственно мощность X равна мощности Y ).

Введем обозначения: |X| 6 |Y |, если мощность X не больше мощности Y , и |X| = |Y |, если мощность X равна мощности Y . Если |X| = |Y |, то будем также говорить, что множества X и Y равномощны.

Заметим, что из включения X Y вытекает неравенство |X| 6 6 |Y |. Обратное утверждение, разумеется, неверно.

Пусть X, Y – счетные множества, Z – бесконечное множество. Тогда |X| = |Y | и |X| 6 |Z|. Последнее неравенство вытекает из известного нам утверждения: всякое бесконечное множество содержит счетное подмножество.

Кроме того, имеет место следующее простое утверждение.

Предложение 5.27. Пусть X – бесконечное, а Y – счетное множество. Тогда множества X Y и X равномощны.

Д о к а з а т е л ь с т в о. Поскольку X бесконечно, оно содержит счетное подмножество Z. Множество Z Y счетно, поэтому су-

102

ществует биективное отображение g из Z Y на Y . Нетрудно видеть, что отображение

f : X Y −→ X,

заданное правилом

f (x) =

x, если x X \ Z, g(x), если x Z Y,

также является биективным.

Приведем несколько важных примеров равномощных множеств. 1. Интервалы (0; 1) и (a; b) равномощны.

В самом деле, отображение f : (0; 1) −→ (a; b), определенное формулой f (x) = (b − a)x + a, очевидно, является биективным.

2. Интервал (0; 1) и множество R равномощны. Действительно, пусть

Легко проверить, что g биективное отображение.

3. Интервал (0; 1) и полуинтервал (0; 1] равномощны. Положим

h(x) =

x/2, если x = 1/2n, n > 0 x, в противном случае.

Читатель без труда убедится, что h биективно отображает полуинтервал (0; 1] на интервал (0; 1).

Из свойств инъективных и биективных отображений вытекают следующие утверждения.

Предложение 5.28. Пусть X, Y , Z – произвольные непустые множества. Тогда

1)|X| = |X|;

2)если |X| = |Y |, то |Y | = |X|;

3)если |X| = |Y | и |Y | = |Z|, то |X| = |Z|.

103

Предложение 5.29. Пусть X, Y , Z – произвольные непустые множества. Тогда

1)|X| 6 |X|;

2)если |X| 6 |Y | и |Y | 6 |Z|, то |X| 6 |Z|;

3)если |X| 6 |Y |, то |ZX | 6 |ZY |;

4)если |Y | 6 |Z|, то |Y X | 6 |ZX |.

А что будет в том случае, когда одновременно |X| 6 |Y | и |Y | 6 |X| ? Оказывается, справедлива

Теорема 5.6. Если |X| 6 |Y | и |Y | 6 |X|, то |X| = |Y |.

Эту теорему часто называют теоремой Кантора1– Бернштейна2.

Доказательство теоремы 5.6 основано на следующем вспомогательном утверждении.

Лемма 1. Пусть X – бесконечное множество, Y – его собственное подмножество, равномощное X. Если Z0 X \ Y , то множества Y Z0 и Y равномощны.

Д о к а з а т е л ь с т в о. Пусть f – биективное отображение из X на Y . Для каждого натурального числа n рассмотрим множество Zn = f n(Z0). Ясно, что

В самом деле, включение f (Z0 Z) Z вытекает из равенств (8). Проверим обратное включение. Пусть y Z. Тогда y Zn при некотором n > 1. Стало быть, y = f (u) для некоторого u Zn−1. Так как Zn−1 Z0 Z, получаем, что y = f (u) f (Z0 Z).

Рассмотрим отображение g из Z0 Y в Y , определенное пра-

1Г. Кантор (1845–1918) – немецкий математик, создатель теории множеств. 2Ф. Бернштейн (1878–1950) – немецкий математик.

104

Из равенства (9) сразу вытекает, что g – сюръективное отображение. Проверим, что g инъективно. Пусть u, v Z0 Y и g(u) = = g(v). Из равенства (9) и определения отображения g следует, что либо u, v Y \ Z, либо u, v Z0 Z. В том случае, когда u, v Y \ Z, имеем

u = g(u) = g(v) = v.

Если же u, v Z0 Z, то

f (u) = g(u) = g(v) = f (v),

откуда, в силу инъективности f снова получаем u = v. Стало быть, из равенства g(u) = g(v) следует равенство u = v.

Итак, g – биективное отображение из Z0 Y на Y ; поэтому Z0 Y и Y равномощны.

Д о к а з а т е л ь с т в о теоремы 5.6. Поскольку |X| 6 |Y | и |Y | 6 6 |X|, существуют инъективные отображения

f : X −→ Y, g : Y −→ X.

Рассмотрим множества X0 = g(Y ) и X1 = g◦f (X). Ясно, что X1X0 X и |X1| = |X|, |X0| = |Y |. Если X1 = X0, то, в частности, |X1| = |X0|, и из предложения 5.28 следует равномощность X и Y . Предположим, что X1 X0. Тогда к множеству X и его подмножествам X1 и Z0 = X0 \ X1 применима лемма 1. Поэтому |X1| = |X1 Z0| = |X0|. Поскольку проверена равномощность множеств X1, X0, то множества X и Y также равномощны.

5.8.Несчетные множества

Вэтом разделе мы приведем несколько примеров бесконечных множеств, не являющихся счетными. Такие множества называются несчетными.

Пусть X – бесконечное множество. Чтобы убедитьтся в том, что X несчетно, достаточно установить, что не существует биективного отображения из N на X. Иными словами, нужно проверить, что |N| 6= |X|. Поскольку в этом случае |N| 6 |X|, то естественно сказать, что мощность множества N строго меньше мощности

105

множества X. Нетрудно понять, что соответствующее определение можно дать и для более общего случая.

Будем говорить, мощность множества X строго меньше мощности множества Y (|X| < |Y |), если |X| 6 |Y | и |X| =6 6= |Y |. Часто вместо |X| < |Y | пишут |Y | > |X| и говорят, что

мощность Y строго больше мощности X. Для того чтобы убедиться в справедливости неравенства |X| < |Y |, достаточно проверить два утверждения:

1)существует инъективное отображение из множества X во множество Y ;

2)не существует сюръективного отображения из X на Y . Действительно, если выполнено утверждение 1), то |X| 6 |Y |.

Из выполнимости утверждения 2) вытекает, что не существует, в частности, и биективного отображения X на Y , откуда |X| =6 |Y |.

Теорема 5.7. Множество всех бесконечных последовательностей, составленных из элементов множества {0, 1}, является несчетным.

Д о к а з а т е л ь с т в о. Предположим, что рассматриваемое множество счетно. Тогда все последовательности из нулей и единиц можно представить в виде строк бесконечной таблицы

a11 a12 . . . a1n . . .

Для каждого натурального n определим bn = 1 − ann и рассмотрим бесконечную последовательность (bn). Легко понять, что эта последовательность отлична от каждой из последовательностей, являющихся строками таблицы (10). В самом деле, предположим, что последовательность (bn) совпадает с k-ой строкой из таблицы (10). Это значит, что равенство bn = akn выполнено при любом n. В частности, оно выполнено и при n = k. Но равенство bk = akk невозможно, поскольку bk = 1 −akk и akk {0, 1}. Таким образом, получено противоречие: с одной стороны, мы предположили, что

106

каждая последовательность из нулей и единиц является строкой таблицы (10), а с другой – нашли последовательность, не являющуюся строкой этой таблицы.

Другим примером несчетного множества является множество 2N, состоящее из всех отображений множества N в двухэлементное множество. Оказывается, существует биективное отображение из 2N на множество всех бесконечных последовательностей из нулей и единиц. Иными словами, эти два множества равномощны. Проверим это утверждение. Пусть f – произвольное отображение из N в двухэлементное множество {0, 1}. Тогда однозначно определена последовательность (an), где an = f (n). Обратно, если задана последовательность (an), то правило f (n) = an однозначно определяет отображение f : N −→ 2.

Множества, равномощные множеству 2N, играют важную роль

вразличных разделах математики.

Оп р е д е л е н и е. Всякое множество, равномощное множеству 2N, называется множеством мощности континуум.

Ниже будут приведены примеры различных множеств мощности континуум. А сейчас мы докажем утверждение, обобщающее утверждение о несчетности множества 2N.

Теорема 5.8 (теорема Кантора). Пусть X – произвольное непустое множество. Тогда |X| < |2X |.

Д о к а з а т е л ь с т в о. Нетрудно понять, что |X| 6 |2X |. В самом деле, для каждого элемента x X определено такое отображение

hx : X −→ 2,

что hx(y) = 1 тогда и только тогда, когда y = x. Ясно, что тем самым задано отображение

ϕ : X −→ 2X ,

определенное правилом ϕ(x) = hx. Нетрудно понять, что отображение ϕ инъективно.

Осталось убедиться в том, что не существует сюръективного отображения из X на 2X .

107

Рассмотрим произвольное отображение

ϕ: X −→ 2X

ипроверим, что его образ отличен от множества 2X . Пусть x – произвольный элемент множества X. Тогда определено отображение

ϕ(x) : X −→ 2.

Для удобства будем вместо ϕ(x) писать ϕx. Определим теперь отображение

f : X −→ 2

при помощи правила f (x) = 1 − ϕx(x), x X. Легко видеть, что при любом x X выполнено неравенство

В самом деле, предположим, что f = ϕy для некоторого y X. Тогда должно выполняться равенство f (y) = ϕy(y). Но по определению f (y) = 1 − ϕy(y), и мы получаем противоречивое утверждение ϕy (y) = 1 − ϕy(y). Итак, мы доказали, что каково бы ни было отображение ϕ : X −→ 2X , обязательно найдется отображение f : X −→ 2, не принадлежащее образу отображения ϕ. Иными словами, отображение ϕ не является сюръективным, а потому оно не может быть и биективным.

Таким образом, проверено, что |X| 6 |2X | и |X| 6= |2X |, откуда следует неравенство |X| < |2X |.

Способ, примененный при доказательстве теорем 5.7 и 5.8, часто называют диагональным методом Кантора. Разумеется, такие доказательства используются не только при изучении множеств, но и в других разделах современной математики.

Вернемся к обсуждению множеств мощности континуум.

Теорема 5.9. Пусть X – произвольное непустое множество, причем 2 6 |X| 6 |2N|. Тогда множество XN имеет мощность континуум.

Д о к а з а т е л ь с т в о. Так как 2 6 |X| 6 |2N|, с использованием

108

Из соотношений (12) – (14) легко следует, что |2N| 6 |XN| и |XN| 6 6 |2N|. Теорема Кантора-Бернштейна показывает теперь, что

|XN| = |2N|.

Из теоремы 5.9 вытекает ряд важных следствий.

Предложение 5.30. Множество чисел из интервала (0; 1) имеет мощность континуум.

Д о к а з а т е л ь с т в о. Известно, что каждое действительное число d (0; 1) можно однозначно представить в виде бесконечной десятичной дроби 0, d1d2 . . . dn . . ., не содержащей в периоде цифры 9. Пусть D = {0, 1, 2, . . . , 9} – множество десятичных цифр. Нетрудно понять, множество чисел из полуинтервала [0; 1) равномощно множеству всех бесконечных последовательностей, составленных из элементов множества D и не содержащих 9 в периоде. Множество DN, состоящее из всех бесконечных последовательностей элементов из D, имеет мощность континуум (это следует из теоремы 5.9). Обозначим через X множество всех бесконечных последовательностей, имеющих 9 в периоде. Это множество, очевидно, бесконечно, и потому, в силу предложения 5.26, счетно. Из предложения 5.27 вытекает, что множество DN \ X равномощно множеству DN. Последнее множество континуально, а потому и множество DN \ X имеет мощность континуум. Итак, мы проверили, что множество точек полуинтервала [0; 1) имеет мощность континуум. Осталось заметить, что интервал (0; 1) и полуинтервал [0; 1) равномощны.

Следствие 1. Любой интервал имеет мощность континуум.

Следствие 2. Множество R имеет мощность континуум.

109