Наум Виленкин - В поисках бесконечности

Мы скажем, что если A можно поставить во взаимно однозначное соответствие с частью множества B, то множество B имеет не меньше элементов, чем множество A. Можно доказать, что это отношение обладает всеми свойствами неравенств:

1. каждое множество имеет не меньше элементов, чем оно само;

2. если в одном множестве не меньше элементов, чем во втором, а во втором — не меньше элементов, чем в третьем, то первое множество имеет не меньше элементов, чем третье;

3. если каждое из двух множеств имеет не меньше элементов, чем другое, то оба имеют поровну элементов (то есть между элементами этих множеств можно установить взаимно однозначное соответствие).

Первое свойство вытекает из того, что, ставя в соответствие каждому элементу множества A сам этот элемент, получаем взаимно однозначное отображение A на себя. Прозрачен и смысл второго свойства: если A можно взаимно однозначно отобразить на часть множества B, а B — на часть множества C, то существует взаимно однозначное отображение A на часть C.

А вот третье свойство при всей простоте его формулировки означает довольно сложное утверждение: если можно взаимно однозначно отобразить множество A на часть множества B, а множество B на часть множества A, то существует и взаимно однозначное отображение всего множества A на B. То, что дело обстоит таким образом, с самого начала подозревал Г. Кантор. Однако ему в течение долгого времени не удавалось найти доказательства этого утверждения. О своих затруднениях он рассказал в 1897 г. на лекциях по теории множеств для студентов университета в Галле. Через несколько дней один из слушателей, 19-летний Феликс Бернштейн [48] Бернштейн Феликс (1878-1956) — немецкий математик. , принес Кантору доказательство этого утверждения, основанное на той же идее, с помощью которой директор космической гостиницы помещал в нее новых постояльцев. Поэтому сейчас это утверждение называют теоремой Кантора-Бернштейна . Лишь через много лет в оставшихся после смерти немецкого математика Дедекинда бумагах нашли полученное им еще в 1887 г. доказательство той же теоремы.

Выясним теперь, в каких же случаях говорят, что мощность множества A меньше мощности множества B. Может случиться, что множество B имеет не меньше элементов, чем множество A, но эти множества не эквивалентны. Иными словами, может случиться, что есть взаимно однозначное соответствие между множеством A и частью B 1множества B, но не существует взаимно однозначного соответствия между A и всем множеством B. Вот в этом случае мы и будем говорить, что A имеет меньше элементов, чем B.

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

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

X = {x 1, x 2, ..., x n, ...}.

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

Y = {x 1, x 3, x 5, ...},

а оставшееся множество еще содержит бесконечное множество элементов {x 2, x 4, x 6, ..., x 2n, ...} и, быть может, еще много других элементов.

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

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

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

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

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

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

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

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

101010101010...

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

11111111111...

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

000000000000...

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

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