ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.12.2020
Просмотров: 2178
Скачиваний: 53
Несчетные множества
75
мощность счетного множества не больше мощности любого беско-
нечного множества, то есть что эта мощность — самая маленькая
из бесконечных.
Чтобы выбрать счетное подмножество из бесконечного множе-
ства
A
, поступим так. Выберем один элемент
x
1
— это можно сде-
лать, так как множество
A
бесконечно и, во всяком случае, не пусто.
Ясно, что после удаления элемента
x
1
множество
A
не исчерпыва-
ется, и мы сможем выбрать из него второй элемент
x
2
. После этого
выберем третий элемент
x
3
и т. д. В результате мы извлечем из мно-
жества
A
счетное подмножество занумерованных элементов
X
=
{
x
1
, x
2
, . . . , x
n
, . . .
}
.
Немного усовершенствовав это доказательство, можно добиться,
чтобы после удаления счетного подмножества осталось бесконеч-
ное множество. Для этого надо после извлечения подмножества
X
вернуть обратно все элементы с четными номерами. В результате
получится, что мы извлекли счетное подмножество
Y
=
{
x
1
, x
3
, x
5
, . . .
}
,
а оставшееся множество еще содержит бесконечное множество эле-
ментов:
{
x
2
, x
4
, x
6
, . . . , x
2
n
, . . .
}
(и, быть может, еще много других
элементов).
Нетрудно доказать следующие теоремы.
Мощность бесконечного множества не изменяется от прибав-
ления к нему счетного множества.
Мощность несчетного множества не меняется от удаления
из него счетного множества.
Эти теоремы еще раз подтверждают, что счетные множества —
самые малые из бесконечных множеств.
Несчетные множества
Все построенные до сих пор множества оказались счетными. Это
наводит на мысль, а не являются ли вообще все бесконечные множе-
ства счетными? Если бы это оказалось так, то жизнь математиков
была бы легкой: все бесконечные множества имели бы поровну эле-
ментов и не понадобился бы никакой анализ бесконечности. Но выяс-
нилось, что дело обстоит куда сложнее, несчетные множества суще-
ствуют, и притом с разными мощностями. Одно несчетное множество
всем хорошо знакомо — это множество всех точек на прямой линии.
76
Глава II. В мире чудес бесконечного
Но прежде чем говорить об этом множестве, мы расскажем о другом,
тесно связанном с ним множестве
A
вариантов заполнения необык-
новенной гостиницы.
Заметим, что доказать несчетность какого-то множества вообще
нелегко. Ведь доказать, что какое-то множество счетно, это значит
просто придумать правило, по которому нумеруются его элементы.
А доказать несчетность какого-то множества, это значит доказать,
что такого правила нет и быть не может. Иными словами, какое бы
правило мы ни придумали, всегда найдется незанумерованный эле-
мент множества. Чтобы доказывать несчетность множеств, Кантор
придумал очень остроумный способ, получивший название диаго-
нального процесса (фактически мы с ним уже сталкивались на с. 13).
Метод доказательства Кантора станет ясен из следующего рассказа
Йона Тихого.
Несостоявшаяся перепись
До сих пор я рассказывал об удачах директора необыкновенной
гостиницы: о том, как ему удалось вселить в заполненную гостиницу
еще бесконечно много постояльцев, а потом даже жителей из беско-
нечного множества столь же необычных гостиниц. Но был случай,
когда и этого мага и чародея постигла неудача.
Из треста космических гостиниц пришел приказ составить за-
ранее все возможные варианты заполнения номеров. Эти варианты
потребовали представить в виде таблицы, каждая строка которой
изображала бы один из вариантов. При этом заполненные номера
должны были изображаться единицами, а пустые нулями. Напри-
мер вариант
101010101010
. . .
означал, что все нечетные номера заняты, а все четные пустые, ва-
риант
11111111111
. . .
означал заполнение всей гостиницы, а вариант
000000000000
. . .
означал полный финансовый крах — все номера пустовали.
Директор был перегружен работой и поэтому придумал простой
выход из положения. Каждой дежурной по этажу было поручено со-
ставить столько вариантов заполнения, сколько номеров было в ее
Несостоявшаяся перепись
77
ведении. При этом были приняты меры, чтобы варианты не повто-
рялись. Через несколько дней списки были представлены директору,
и он объединил их в один список.
— Уверены ли вы, что этот список полон? — спросил я директо-
ра. — Не пропущен ли какой-нибудь вариант?
— Не знаю, — ответил он. — Вариантов в списке бесконечно мно-
го, и я не понимаю, как проверить, нет ли еще какого-нибудь вари-
анта.
И тут у меня блеснула идея (впрочем, быть может, я несколь-
ко преувеличиваю свои способности, просто беседы с профессором
Тарантогой о бесконечных множествах не прошли бесследно).
— Могу ручаться, что список неполон. Я берусь указать вариант,
который наверняка пропущен.
— С тем, что список неполон, я еще соглашусь. А вот пропущен-
ного варианта указать не удастся — ведь здесь уже бесконечно много
вариантов.
Мы заключили пари. Чтобы выиграть его, я предложил прибить
каждый вариант на дверь того номера, которому он соответствовал
(если читатель помнит, вариантов было составлено именно столь-
ко, сколько было номеров в гостинице). А потом я поступил очень
просто. Подойдя к двери первого номера, я увидел, что соответ-
ствующий вариант начинается с цифры 0. Немедленно в блокноте
появилась цифра 1; это и была первая цифра варианта, который
мне хотелось составить.
Когда я подошел к двери второго номера, то первая цифра соот-
ветствующего варианта меня не интересовала, ведь первая цифра
моего варианта была уже написана. Поэтому все внимание было
обращено на вторую цифру. Увидев, что эта цифра 1, я записал
в своем блокноте цифру 0. Точно так же, обнаружив, что третья
цифра варианта, прибитого к двери третьего номера, тоже 1, я за-
писал в блокноте цифру 0. Вообще, если я обнаруживал, что
n
-я
цифра
n
-го варианта есть 0, то писал в своем блокноте на
n
-м ме-
сте цифру 1, если же
n
-я цифра
n
-го варианта была 1, то я писал
у себя 0.
Когда я обошел все номера гостиницы
1
, то в блокноте оказалась
записанной последовательность нулей и единиц.
Войдя в кабинет директора, я сказал:
— Вот, полюбуйтесь на пропущенный вариант.
1
Гм, гм, сколько же времени он затратил?
78
Глава II. В мире чудес бесконечного
— А откуда известно, что он пропущен?
— Он не может быть первым, так как отличается от него первой
цифрой; не может быть вторым, так как отличается от него второй
цифрой; третьим, так как отличается от него третьей цифрой; и во-
обще
n
-м, так как отличается от него
n
-й цифрой.
Пари было выиграно, и я получил вечное право бесплатного про-
живания в этой гостинице.
Но одновременно стало ясно, что какое бы счетное множество
вариантов ни взять, всегда найдется вариант, не вошедший в это мно-
жество (эти варианты всегда можно развесить по дверям номеров).
А это и значит, что множество всех вариантов заполнения гости-
ницы несчетно, задача, поставленная перед директором, оказалась
невыполнимой.
Было решено дать об этом телеграмму. Надо сказать, что и те-
леграф в необыкновенной гостинице был тоже необычным, он пе-
редавал телеграммы, состоящие не из конечного, а из бесконечного
(точнее говоря, счетного) множества точек и тире. Например, они
имели такой вид:
—
·
—
·
— — —
·
и т. д.
Я сразу сообразил, что и множество таких телеграмм тоже несчет-
но, ведь вместо точек и тире можно ставить нули и единицы, а тогда
не будет никакой разницы между телеграммами со счетным множе-
ством знаков и множеством всех вариантов заполнения гостиницы.
Отправив телеграмму, я тепло попрощался с директором гости-
ницы и полетел в галактику РЩ-8067, где должен был произвести
астрографическую съемку...
Несчетность континуума
Теперь уже несложно доказать, что множество всех точек на пря-
мой линии несчетно. Вместо этого множества можно говорить о мно-
жестве всех действительных чисел, так как каждой точке прямой
соответствует действительное число и обратно.
Каждое действительное число можно записать в виде бесконеч-
ной десятичной дроби вида
a, α
1
α
2
α
3
. . . α
n
. . .
Несчетность континуума
79
Некоторые из них имеют даже по две записи, например:
0
,
500000
. . .
и
0
,
49999999
. . .
— это одно и то же число. Для определенности будем
пользоваться записью с нулями.
Предположим, что нам удалось каким-то образом перенумеро-
вать все действительные числа. Чтобы доказать, что это предполо-
жение неверно, достаточно построить хоть одно незанумерованное
число. Следуя примеру Йона Тихого, поступим следующим обра-
зом. Сначала напишем нуль и поставим после него запятую. Потом
возьмем число, получившее первый номер, и посмотрим на его пер-
вый десятичный знак после запятой (то есть на число десятых).
Если эта цифра отлична от 1, то в числе, которое мы пишем, по-
ставим после запятой 1, а если эта цифра равна 1, то поставим после
запятой 2. Затем перейдем к числу, получившему второй номер,
и посмотрим на его вторую цифру после запятой. Снова, если эта
цифра отлична от единицы, то в числе, которое мы пишем, поста-
вим на месте сотых цифру 1, если же эта цифра является единицей,
то поставим цифру 2. Точно так же будем действовать и дальше,
каждый раз обращая внимание лишь на
n
-ю цифру числа, полу-
чившего
n
-й номер. В результате мы выпишем некоторое число, на-
пример:
N
= 0
,
1121211
. . .
Ясно, что это число не получило никакого номера: в первом деся-
тичном знаке оно отличается от числа с номером 1, во втором —
от числа с номером 2,
. . .
, в
n
-м — от числа с номером
n
и т. д.
(см. с. 13).
Чтобы читателю стало яснее, как выписывается число, не полу-
чившее номера, предположим, что при выбранной нумерации первые
пять чисел имеют следующий вид:
4
,
27364
. . .
−
1
,
31226
. . .
7
,
95471
. . .
0
,
62419
. . .
8
,
56280
. . .
Тогда число, не получившее номера, будет начинаться со следующих
десятичных знаков:
0
,
12121
. . .
Разумеется, не только это, но и многие другие числа не получили
номеров (мы могли бы заменять все цифры, кроме 2, на 2, а цифру 2