Лекции и упражнения

5.2. КОНТИНУАЛЬНЫЕ МНОЖЕСТВА
69
5.2 Континуальные множества
У читателя могло возникнуть впечатление, что все бесконечные множества
являются счетными. Но это не так, как показывает следующая теорема:
Теорема 13. Множество точек на отрезке
[0; 1]
 не счетное.
Доказательство.
Предположим обратное  что можно как-то занумеровать все числа из от-
резка:
[0; 1] =
{
a
1
, . . . , a
n
, . . .
}
.
Рассмотрим десятичные записи каждого из этих чисел:
a
1
= 0
,
?
(1)
1
?
(1)
2
. . . ?
(1)
n
. . .
a
2
= 0
,?
(2)
1
?
(2)
2
. . . ?
(2)
n
. . .
. . .
a
n
= 0
,?
(
n
)
1
?
(
n
)
2
. . .
?
(
n
)
n
. . .
. . .
Если возможно два варианта записи числа, например
0
,
5
и
0
,
49
...
9
...
,
будем (для определенности) выбирать вариант с нулями, а не с девятками.
Выберем диагональную последовательность
?
(1)
1
,
?
(2)
2
, . . .
?
(
n
)
n
, . . . , по
ней построим последовательность
?
i
=
(
1
,
?
(
i
)
i
= 2;
2
,
?
(
i
)
i
6
= 2
,
т.е. просто заменим
все цифры 2 на 1, а остальные  на цифру 2. Составим из этих цифр число
b
= 0
,?
1
?
2
. . . ?
n
. . .
. Очевидно,
b
принадлежит отрезку
[0
,
1]
но не равно ни
одному из чисел
a
i
, поскольку отличается от каждого из них по крайней
мере в одном разряде. Противоречие.
5
Определение 51. Мощность множества
[0
,
1]
называется континуум и
обозначается
|
[0
,
1]
|
=
c
.
Следствие 6. Множество
R
 не счетное.
5.3 Теорема Кантора
Приведем здесь забавную задачу из книги Р.М.Смаллиана ѕКак же назы-
вается эта книгаї:
Однажды инспектор Крэг посетил некую общину и побеседовал с од-
ним из ее членов  социологом МакCнурдом, который сообщил следующее:
 Члены общины организовали несколько клубов. Каждый член общины
может являться членом более одного клуба. Каждый клуб получает на-
звание в честь одного из членов общины. Никакие два клуба не названы
5
Внимательный читатель может заметить, что записи
0
,
49
..
9
. . .
и
0
,
50
. . .
0
. . .
обо-
значают одно и то же число, хотя и отличаются в каждом разряде. Но в данном случае
число
b
составлено только из цифр 1 и 2, поэтому не может иметь альтернативной формы
записи.

70
ГЛАВА 5. МОЩНОСТЬ МНОЖЕСТВА
в честь одного и того же члена общины, и имя каждого члена общины
носит какой-то клуб. Член общины не обязательно должен быть членом
клуба, носящего его имя. Всякого, кто является членом клуба, носящего
его имя, мы называем номинабельным. Всякого, кто не является членом
клуба, носящего его имя, мы называем неноминабельным. Самое удиви-
тельное в нашей общине - это то, что все неноминабельные ее члены
входят в один клуб.
Инспектор Крэг на миг задумался и внезапно понял, что МакCнурд не
очень силен в логике: в его истории концы не сходятся с концами. Поче-
му?
Упражнение 148. Почему?
Определение 52. Будем обозначать
2
A
=
{
A
0
?
A
}
 множество всех
подмножеств
A
.
Заметим, что если
|
A
|
=
n
 конечное множество, то у него ровно
2
n
подмножеств.
Известный немецкий
6
математик Георг Кантор сформулировал в 1899
году следующую теорему:
Теорема 14 (Кантор). Пусть
A
 некоторое множество, тогда
|
A
|
<
|
2
A
|
Доказательство.
Предположим обратное, т.е.
|
A
|
=
|
2
A
|
. Тогда существует биекция
f
:
A
?
?
2
A
, которая каждому элементу
a
?
A
ставит в соответствие
f
(
a
)
?
A
.
Пусть
B
=
{
a
?
A
|
a
6?
f
(
a
)
}
. Поскольку
f
 биекция, то найдется
b
=
=
f
?
1
(
B
)
, то есть
f
(
b
) =
B
. Предположим, что
b
?
B
. Тогда (по опреде-
лению множества
B
)
b
6?
f
(
b
) =
B
. Если же предположить, что
b
6?
B
, то
получаем
b
?
f
(
b
) =
B
 в обоих случаях приходим к противоречию.
На этой теореме основан слуюющий парадокс:
Парадокс Кантора
Пусть
A
 множество всех множеств. Тогда
2
A
?
A
(т.к. любое подмно-
жество является его элементом). Следовательно
|
2
A
|
6
|
A
|
<
|
2
A
|
. Проти-
воречие.
Следствие 7. Для любого множества можно построить множество
большей мощности. В частности, множество
2
R
больше континуума и
называется гиперконтинуум.
5.4 Теорема Кантора  Бернштейна
Из леммы 1 вытекает, что для доказательства счетности бесконечного мно-
жества
A
достаточно построить его иньекцию в
N
. Это является частным
случаем некоторого общего факта, который позволяет легко доказывать
равномощность множеств.
6
Георг Кантор родился и жил до 11 лет в Санкт-Петербурге.

5.4. ТЕОРЕМА КАНТОРА  БЕРНШТЕЙНА
71
Рис. 5.1: Георг Кантор (18451918)
Теорема 15 (Кантор  Бернштейн). Пусть для множеств
A
и
B
суще-
ствуют инъекции
f
:
A
7?
B
и
g
:
B
7?
A
. Тогда
|
A
|
=
|
B
|
, т.е. множества
A
и
B
равномощны.
A
0
A
1
A
2
A
3
. . .
A
?
B
0
B
1
B
3
. . .
B
?
f
g
?
1
g
?
1
B
2
f
f
Рис. 5.2: Теорема Кантора  Бернштейна.
Доказательство.
Обозначим
A
0
=
A
\
g
(
B
)
,
B
0
=
B
\
f
(
A
)
.
7
A
1
=
g
(
B
0
)
,
B
1
=
f
(
A
0
)
. Несложно
заметить, что
A
0
?
A
1
=
?
,
B
0
?
B
1
=
?
и построить биекцию между
A
0
?
A
1
и
B
0
?
B
1
.
7
Напомним, что
f
(
A
)
обозначает образ множества
A
при отображении
f
.

72
ГЛАВА 5. МОЩНОСТЬ МНОЖЕСТВА
Далее рассмотрим множества
€
A
1
=
A
\
(
A
0
?
A
1
)
и
€
B
1
=
B
\
(
B
0
?
B
1
)
и проведем для них аналогичное построение:
A
2
= €
A
1
\
g
( €
B
1
)
,
B
2
= €
B
1
\
\
f
( €
A
1
)
и
A
3
=
g
(
B
2
)
,
B
3
=
f
(
A
2
)
. Продолжим это построение, на
k
м шаге
будем рассматривать множества
€
A
k
=
A
\
(
2
k
?
1
S
i
=0
A
i
и
€
B
k
=
B
\
(
2
k
?
1
S
i
=0
B
i
)
.
Для них построим
A
2
k
= €
A
k
\
g
( €
B
k
)
,
B
2
k
= €
B
k
\
f
( €
A
k
)
и
A
2
k
+1
=
g
(
B
2
k
)
,
B
2
k
+1
=
f
(
A
2
k
)
.
Также обозначим
A
?
=
A
\
(
?
S
i
=0
A
i
и
B
?
=
B
\
(
?
S
i
=0
B
i
)
.
Итак, получили разбиения множеств
A
и
B
на непересекающиеся компо-
ненты:
A
=
?
S
j
=0
A
k
?
A
?
;
и
B
=
?
S
j
=0
B
k
?
B
?
.
Построим теперь биективное
соответствие между ними. Рассмотрим отображение (см. рис. 5.2)
F
(
a
) =
(
f
(
a
)
,
a
?
A
2
k
или
a
?
A
?
;
g
?
1
(
a
)
,
a
?
A
2
k
+1
.
Оно является биекцией, т.к. для каждого
k
= 0
,
1
,
2
, . . .
отображение
f
:
:
A
2
k
7?
B
2
k
+1
будет биекцией и
g
?
1
:
A
2
k
+1
7?
B
2
k
+2
 тоже будет биекци-
ей.
Теорема 16. Квадрат
[0
,
1]
Ч
[0
,
1]
имеет мощность континуум.
Доказательство.
Очевидно, отрезок можно инъективно отобразить в квадрат. Построим инъ-
екцию квадрата в отрезок. Для любой пары чисел
(
x, y
)
выберем деся-
тичное разложение, не содержащее девяток в периоде:
x
= 0
,x
1
x
2
...x
n
...
,
y
= 0
,y
1
...y
n
...
. Отобразим их в число
f
(
x, y
) = 0
,x
1
y
1
x
2
y
2
...x
n
y
n
...
, очевид-
но, принадлежащее отрезку
[0
,
1]
.
Поскольку мы выбирали представление
x
и
y
без девяток в периоде, то их не будет и в
f
(
x, y
)
. Следовательно, отоб-
ражение  инъекция. Тогда, по теореме Кантора  Бернштейна получаем,
что отрезок и квадрат равномощны.
5.5 Множество Кантора
Рассмотрим отрезок
[0
,
1]
.
Шаг 1: Выбросим из него середину, т.е. интервал
(
1
3
,
2
3
)
. Получим два от-
резка
[0
,
1
3
]
и
[
2
3
,
1]
.
Шаг 2: Из каждого отрезка выбросим середину, получим 4 отрезка:
[0
,
1
9
]
,
[
2
9
,
1
3
]
,
[
2
3
,
7
9
]
и
[
8
9
,
1]
.
. . .
Шаг n: Имеется
2
n
?
1
отрезков вида
a
(
n
?
1)
i
3
n
?
1
,
b
(
n
?
1)
i
3
n
?
1
,
i
= 1
,
2
, . . . ,
2
n
?
1
. Из
каждого отрезка выбросим середину, получим
2
n
отрезков:
a
(
n
)
i
3
n
,
b
(
n
)
i
3
n
,
i
=
= 1
,
2
, . . . ,
2
n
.

5.5. МНОЖЕСТВО КАНТОРА
73
Шаг 1
Шаг 2
Шаг 3
. . .
Рис. 5.3: Множество Кантора
Так будем делать до бесконечности. Т.е. рассмотрим
K
=
?
T
n
=1
K
n
, где
K
n
 объединение отрезков, полученных на
n
-м шаге. Множество
K
назы-
вается множество Кантора (см. рис. 5.3).
Несложно заметить, что на каждом шаге выбрасываются интервалы,
длина которых составляет
1
3
от отрезков. Таким образом, суммарная дли-
на оставшихся отрезков составляет
2
3
от длины отрезков на предыдущем
шаге. Поэтому на
n
-м шаге суммарная длина отрезков составит
2
3
n
, что
стремится к нулю при
n
? ?
. Получается, что в этом множестве должно
остаться очень мало точек. Оказывается, что множество оставшихся точек
не только бесконечно, но еще и равномощно исходному отрезку.
Теорема 17.
|K|
=
c
.
Доказательство.
Запишем все числа на отрезке
[0
,
1]
в троичной системе счисления. Тогда на
n
-м шаге будут выброшены числа, имеющие 1 в
n
-м разряде (кроме чисел
вида
0
, a
1
. . . a
n
?
1
1(0)
и
0
, a
1
. . . a
n
?
1
1(2)
). Таким образом, числа, образован-
ные только цифрами 0 и 2 останутся. Выберем произвольное число из
[0
,
1]
,
запишем его в двоичной системе счисления, а потом заменим все цифры 1
на 2. Получим троичную запись некоторого числа, которое принадлежит
множеству Кантора. Таким образом, каждому
x
?
[0
,
1]
поставлено в соот-
ветствие
y
? K
, причем это отображение  инъекция. C другой стороны,
K ?
[0
,
1]
. Следовательно, по теореме Кантора  Бернштейна эти множества
равномощны.

74

жүктеу/скачать 1,95 Mb.

Достарыңызбен бөлісу: