Том 22. Сон разума. Математическая логика и ее парадоксы - [11]

Вернемся к конечным множествам и посмотрим, что произойдет, если мы будем не рассматривать две совокупности по отдельности, а станем по очереди извлекать из них по одному элементу: начнем с буквы Н и красного цвета и т. д., пока не дойдем до буквы С, которой соответствует фиолетовый цвет. В этот момент одно из двух множеств уже «закончилось», а в другом осталось еще три элемента — буквы Т, В и О, следовательно, кардинальное число этого множества больше. Операция, которую мы попытались проделать, в математике называется установлением биекции между двумя множествами и означает присвоение каждому элементу множества X элемента другого множества Y «один к одному» так, что выполняются следующие условия.

1. Не существует двух элементов X таких, которым соответствует один и тот же элемент Y.

2. Каждому элементу Y соответствует какой-либо элемент множества X.

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

Три примера отображения конечных множеств, лишь одно из которых (см. рис. 3) является биекцией, так как на рис. 1 двум элементам первого множества сопоставлен один элемент второго, а на рис. 2 один из элементов исходного множества остался без пары.

Преимущество этого подхода в том, что его можно применить к бесконечным множествам. Таким образом, будем говорить, что кардинальные числа двух множеств равны, если между множествами можно установить биекцию. Первое следствие этого, возможно, удивит читателя: существует столько же четных чисел, сколько четных и нечетных, вместе взятых. Как такое возможно? Для доказательства этого весьма неочевидного утверждения достаточно определить биекцию между натуральными и четными числами. Сопоставим 0 и 0, 1 и 2, 2 и 4, а произвольному п сопоставим число, в два раза большее него. При таком отображении различным числам всегда будут соответствовать разные числа, и любое четное число будет сопоставлено с числом, в два раза меньшим его. Так как оба свойства биекции выполняются, это означает, что существует столько же четных чисел, сколько и натуральных!

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

Существование подобных гостиниц, которые невозможно заполнить, — это не просто любопытный факт, связанный с четными числами, а основное свойство бесконечных множеств, как заметил Рихард Дедекинд в своей статье «Что такое числа и для чего они служат», опубликованной в 1888 году. Множество является бесконечным, если можно определить биекцию между ним и его частью. Очевидно, что с конечными множествами подобное невозможно, так как часть конечного множества не может быть поставлена в соответствие целому (как мы говорили выше, между двумя конечными множествами, число элементов которых равно m и n соответственно, можно установить биекцию только при m = n). Тем не менее натуральных чисел бесконечно много, так как часть этого множества, строго включенная в него, то есть множество четных чисел, имеет то же кардинальное число, что и все множество в целом. Следовательно, новое определение соответствует рассуждениям, основанным на аксиомах Пеано, с помощью которых мы в предыдущей главе доказали, что натуральных чисел бесконечно много. Однако множество натуральных чисел — это наименьшее бесконечное множество из всех, что можно представить.

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

Счетность множества означает, что между множеством X и множеством натуральных чисел можно установить биекцию. Так, каждому натуральному n можно поставить в соответствие элемент этого множества, который мы обозначим через х_n, так, что если n и m различны, то х_n и х_m также различны. С другой стороны, все элементы X можно записать в виде х_n для некоторого n. Когда дети идут на экскурсию с классом, учитель иногда присваивает им номера, чтобы никто не потерялся.

Перед тем как сесть в автобус, каждый ученик громко выкрикивает свой номер: пе-е-ервый! второ-о-ой! тре-е-етий! Каждый ученик имеет свой номер, и ни один из номеров не повторяется. Элементы счетных множеств также имеют свои порядковые номера: «пе-е-ервый!» — это