В поисках бесконечности - [27]

Счетное множество — самое маленькое из бесконечных.

Мы уже говорили, что любая бесконечная часть множества натуральных чисел счетна. Это означает, что не может существовать бесконечное множество, мощность которого была бы меньше мощности счетного множества. Докажем теперь, что в каждом бесконечном множестве есть счетное подмножество. Отсюда будет следовать, что мощность счетного множества не больше мощности любого бесконечного множества, то есть что эта мощность — самая маленькая из бесконечных.

Чтобы выбрать счетное подмножество из бесконечного множества A, поступим так. Выберем один элемент x₁ — это можно сделать, так как множество A бесконечно и, во всяком случае, не пусто. Ясно, что после удаления элемента x₁ множество A не исчерпывается, и мы сможем выбрать из него второй элемент x₂. После этого выберем третий элемент x₃ и т. д. В результате мы извлечем из множества А счетное подмножество занумерованных элементов

X = {x₁, x₂, ..., x_n, ...}.

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

Y = {x₁, x₃, x₅, ...},

а оставшееся множество еще содержит бесконечное множество элементов {x₂, x₄, x₆, ..., x_2n, ...} и, быть может, еще много других элементов.

Нетрудно доказать следующие теоремы.

Мощность бесконечного множества не изменяется от прибавления к нему счетного множества.

Мощность несчетного множества не меняется от удаления из него счетного множества.

Эти теоремы еще раз подтверждают, что счетные множества — самые малые из бесконечных множеств.

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

Все построенные до сих пор множества оказались счетными. Это наводит на мысль: а не являются ли вообще все бесконечные множества счетными? Если бы это оказалось так, то жизнь математиков была бы легкой: все бесконечные множества имели бы поровну элементов и не понадобился бы никакой анализ бесконечности. Но выяснилось, что дело обстоит куда сложнее: несчетные множества существуют и притом могут иметь самые разные мощности. Одно несчетное множество всем хорошо знакомо — это множество всех точек на прямой линии. Но прежде чем говорить об этом множестве, мы расскажем о другом, тесно связанном с ним множестве A вариантов заполнения необыкновенной гостиницы.

Заметим, что доказать несчетность какого-то множества вообще нелегко. Ведь доказать, что какое-то множество счетно, это значит просто придумать правило, по которому нумеруются его элементы. А доказать несчетность какого-то множества, это значит доказать, что такого правила нет и быть не может. Иными словами, какое бы правило мы ни придумали, всегда найдется незанумерованный элемент множества. Чтобы доказывать несчетность множеств, Кантор придумал очень остроумный способ, получивший название диагонального процесса. Метод доказательства Кантора станет ясен из следующего рассказа Иона Тихого.

Несостоявшаяся перепись.

До сих пор я рассказывал об удачах директора необыкновенной гостиницы: о том, как ему удалось вселить в заполненную гостиницу еще бесконечно много постояльцев, а потом даже жителей из бесконечного множества столь же необычных гостиниц. Но был случай, когда и этого мага и чародея постигла неудача.

Из треста космических гостиниц пришел приказ составить заранее все возможные варианты заполнения номеров. Эти варианты потребовали представить в виде таблицы, каждая строка которой изображала бы один из вариантов. При этом заполненные номера должны были изображаться единицами, а пустые нулями. Например, вариант

101010101010...

означал, что все нечетные номера заняты, а все четные пустые, вариант

11111111111...

означал заполнение всей гостиницы, а вариант

000000000000...

означал полный финансовый крах — все номера пустовали.

Директор был перегружен работой и поэтому придумал простой выход из положения. Каждой дежурной по этажу было поручено составить столько вариантов заполнения, сколько номеров было в ее ведении. При этом были приняты меры" чтобы варианты не повторялись. Через несколько дней списки были представлены директору, и он объединил их в один список.

- Уверены ли Вы, что этот список полон? — спросил я директора.- Не пропущен ли какой-нибудь вариант?

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

И тут у меня блеснула идея (впрочем, быть может, я несколько преувеличиваю свои способности, просто беседы с профессором Тарантогой о бесконечных множествах не прошли бесследно).

- Могу ручаться, что список неполон. Я берусь указать вариант, который наверняка пропущен.

- С тем, что список неполон, я еще соглашусь. А вот пропущенного варианта указать не удастся — ведь здесь уже бесконечно много вариантов.

Мы заключили пари. Чтобы выиграть его, я предложил прибить каждый вариант на дверь того номера, которому он соответствовал (если читатель помнит, вариантов было составлено именно столько, сколько было номеров в гостинице). А потом я поступил очень просто. Подойдя к двери первого номера, я увидел, что соответствующий вариант начинается с цифры 0. Немедленно в блокноте появилась цифра 1; это и была первая цифра варианта, который мне хотелось составить.