кциях по теории множеств для студентов университета в Галле. Через несколько дней один из слушателей, 19-летний Феликс Бернштейн[48], принес Кантору доказательство этого утверждения, основанное на той же идее, с помощью которой директор космической гостиницы помещал в нее новых постояльцев. Поэтому сейчас это утверждение называют теоремой Кантора-Бернштейна. Лишь через много лет в оставшихся после смерти немецкого математика Дедекинда бумагах нашли полученное им еще в 1887 г. доказательство той же теоремы.
Выясним теперь, в каких же случаях говорят, что мощность множества A меньше мощности множества B. Может случиться, что множество B имеет не меньше элементов, чем множество A, но эти множества не эквивалентны. Иными словами, может случиться, что есть взаимно однозначное соответствие между множеством A и частью B1 множества B, но не существует взаимно однозначного соответствия между A и всем множеством B. Вот в этом случае мы и будем говорить, что A имеет меньше элементов, чем B.
Счетное множество — самое маленькое из бесконечных.
Мы уже говорили, что любая бесконечная часть множества натуральных чисел счетна. Это означает, что не может существовать бесконечное множество, мощность которого была бы меньше мощности счетного множества. Докажем теперь, что в каждом бесконечном множестве есть счетное подмножество. Отсюда будет следовать, что мощность счетного множества не больше мощности любого бесконечного множества, то есть что эта мощность — самая маленькая из бесконечных.
Чтобы выбрать счетное подмножество из бесконечного множества A, поступим так. Выберем один элемент x1 — это можно сделать, так как множество A бесконечно и, во всяком случае, не пусто. Ясно, что после удаления элемента x1 множество A не исчерпывается, и мы сможем выбрать из него второй элемент x2. После этого выберем третий элемент x3 и т. д. В результате мы извлечем из множества А счетное подмножество занумерованных элементов
X = {x1, x2, ..., xn, ...}.
Немного усовершенствовав это доказательство, можно добиться, чтобы после удаления счетного подмножества осталось бесконечное множество. Для этого надо после извлечения подмножества X вернуть обратно все элементы с четными номерами. В результате получится, что мы извлекли счетное подмножество
Y = {x1, x3, x5, ...},
а оставшееся множество еще содержит бесконечное множество элементов {x2, x4, x6, ..., x2n, ...} и, быть может, еще много других элементов.
Нетрудно доказать следующие теоремы.
Мощность бесконечного множества не изменяется от прибавления к нему счетного множества.
Мощность несчетного множества не меняется от удаления из него счетного множества.
Эти теоремы еще раз подтверждают, что счетные множества — самые малые из бесконечных множеств.
Несчетные множества.
Все построенные до сих пор множества оказались счетными. Это наводит на мысль: а не являются ли вообще все бесконечные множества счетными? Если бы это оказалось так, то жизнь математиков была бы легкой: все бесконечные множества имели бы поровну элементов и не понадобился бы никакой анализ бесконечности. Но выяснилось, что дело обстоит куда сложнее: несчетные множества существуют и притом могут иметь самые разные мощности. Одно несчетное множество всем хорошо знакомо — это множество всех точек на прямой линии. Но прежде чем говорить об этом множестве, мы расскажем о другом, тесно связанном с ним множестве A вариантов заполнения необыкновенной гостиницы.
Заметим, что доказать несчетность какого-то множества вообще нелегко. Ведь доказать, что какое-то множество счетно, это значит просто придумать правило, по которому нумеруются его элементы. А доказать несчетность какого-то множества, это значит доказать, что такого правила нет и быть не может. Иными словами, какое бы правило мы ни придумали, всегда найдется незанумерованный элемент множества. Чтобы доказывать несчетность множеств, Кантор придумал очень остроумный способ, получивший название диагонального процесса. Метод доказательства Кантора станет ясен из следующего рассказа Иона Тихого.
Несостоявшаяся перепись.
До сих пор я рассказывал об удачах директора необыкновенной гостиницы: о том, как ему удалось вселить в заполненную гостиницу еще бесконечно много постояльцев, а потом даже жителей из бесконечного множества столь же необычных гостиниц. Но был случай, когда и этого мага и чародея постигла неудача.
Из треста космических гостиниц пришел приказ составить заранее все возможные варианты заполнения номеров. Эти варианты потребовали представить в виде таблицы, каждая строка которой изображала бы один из вариантов. При этом заполненные номера должны были изображаться единицами, а пустые нулями. Например, вариант
101010101010...
означал, что все нечетные номера заняты, а все четные пустые, вариант
11111111111...
означал заполнение всей гостиницы, а вариант
000000000000...
означал полный финансовый крах — все номера пустовали.
Директор был перегружен работой и поэтому придумал простой выход из положения. Каждой дежурной по этажу было поручено составить столько вариантов заполнения, сколько номеров было в ее ведении. При этом были приняты меры" чтобы варианты не повторялись. Через несколько дней списки были представлены директору, и он объединил их в один список.
- Уверены ли Вы, что этот список полон? — спросил я директора.- Не пропущен ли какой-нибудь вариант?
- Не знаю,- ответил он.- Вариантов в списке бесконечно много, и я не понимаю, как проверить, нет ли еще какого-нибудь варианта.
И тут у меня блеснула идея (впрочем, быть может, я несколько преувеличиваю свои способности, просто беседы с профессором Тарантогой о бесконечных множествах не прошли бесследно).
- Могу ручаться, что список неполон. Я берусь указать вариант, который наверняка пропущен.
- С тем, что список неполон, я еще соглашусь. А вот пропущенного варианта указать не удастся — ведь здесь уже бесконечно много вариантов.
Мы заключили пари. Чтобы выиграть его, я предложил прибить каждый вариант на дверь того номера, которому он соответствовал (если читатель помнит, вариантов было составлено именно столько, сколько было номеров в гостинице). А потом я поступил очень просто. Подойдя к двери первого номера, я увидел, что соответствующий вариант начинается с цифры 0. Немедленно в блокноте появилась цифра 1; это и была первая цифра варианта, который мне хотелось составить.
Когда я подошел к двери второго номера, то первая цифра соответствующего варианта меня не интересовала, ведь первая цифра моего варианта была уже написана. Поэтому все внимание было обращено на вторую цифру. Увидев, что эта цифра 1, я записал в своем блокноте цифру 0. Точно так же, обнаружив, что третья цифра варианта, прибитого к двери третьего номера, тоже 1, я записал в блокноте цифру 0. Вообще, если я обнаруживал, что n-я цифра n-го варианта есть 0, то писал в своем блокноте на n-м месте цифру 1, если же n-я цифра n-го варианта была 1, то n писал у себя 0.
Когда я обошел все номера гостиницы, то в блокноте оказалась записанной последовательность нулей и единиц.
Войдя в кабинет директора, я сказал:
- Вот, полюбуйтесь на пропущенный вариант.
- А откуда известно, что он пропущен?
- Он не может быть первым, так как отличается от него первой цифрой, не может быть вторым, так как отличается от него второй цифрой, третьим, так как отличается от него третьей цифрой, и вообще n-м, так как отличается от него n-й цифрой.
Пари было выиграно, и я получил вечное право бесплатного проживания в этой гостинице.
Но одновременно стало ясно, что какое бы счетное множество вариантов ни взять, всегда найдется вариант, не вошедший в это множество (эти варианты всегда можно развесить по дверям номеров). А это и значит, что множество всех вариантов заполнения гостиницы несчетно, задача, поставленная перед директором, оказалась невыполнимой.
Было решено дать об этом телеграмму. Надо сказать, что и телеграф в необыкновенной гостинице был тоже необычным, он передавал телеграммы, состоящие не из конечного, а из бесконечного (точнее говоря, счетного) множества точек и тире. Например, они имели такой вид:
-.-----.--------. и т. д.
Я сразу сообразил, что и множество таких телеграмм тоже несчетно, ведь вместо точек и тире можно ставить нули и единицы, а тогда не будет никакой разницы между телеграммами со счетным множеством знаков и множеством всех вариантов заполнения гостиницы.
Отправив телеграмму, я тепло попрощался с директором гостиницы и полетел в галактику РГЦ-8067, где должен был произвести астрографическую съемку...
Несчетность континуума.
Теперь уже несложно доказать, что множество всех точек на прямой линии несчетно. Вместо этого множества можно говорить о множестве всех действительных чисел, так как каждой точке прямой соответствует действительное число и обратно.
Каждое действительное число можно записать в виде бесконечной десятичной дроби вида
a1, α1 α2 α3 ... αn ...
Некоторые из них имеют даже по две записи; например, 0,500000... и 0,49999999... — это одно и то же число. Для определенности будем пользоваться записью с нулями.
Предположим, что нам удалось каким-то образом перенумеровать все действительные числа. Чтобы доказать, что это предположение неверно, достаточно построить хоть одно незанумерованное число. Следуя примеру Иона Тихого, поступим следующим образом.