В поисках бесконечности

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

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

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

Чтобы выбрать счетное подмножество из бесконечного множества 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...

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