Сон разума. Математическая логика и ее парадоксы

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

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

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

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

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

.

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

Перед тем как сесть в автобус, каждый ученик громко выкрикивает свой номер: пе-е-ервый! второ-о-ой! тре-е-етий! Каждый ученик имеет свой номер, и ни один из номеров не повторяется. Элементы счетных множеств также имеют свои порядковые номера: «пе-е-ервый!» — это x₁ «второ-о-ой!» — х₂. Счетные множества — это множества, элементы которых можно выстроить в ряд. Мы показали, что множество четных чисел является счетным, так как их можно упорядочить: 0, 2, 4, 6, 8, 10… Это же справедливо и для положительных и отрицательных чисел, так как можно, начав с нуля, называть их поочередно: 0, 1, —1, 2, —2.

Элементы любого ли множества можно выстроить в ряд? Если это так, то все множества будут счетными, и мы придем к тому же, с чего начали, когда использовали примитивный метод подсчета элементов множества. Однако пусть читатель не беспокоится: одним из величайших достижений Георга Кантора стало открытие множеств, которые не являются счетными. Пусть дано множество, образованное бесконечными последовательностями нулей и единиц, то есть объектами вида 0100100010… или 1100101001… Покажем, что если мы будем считать это множество счетным, то придем к противоречию. В самом деле, если бы это множество было счетным, мы могли бы записать все его элементы в виде списка следующим образом:

Напомним, что а_n, Ь_n и с_n принимают только значения 0 и 1. Составим элемент, который будет принадлежать к множеству бесконечных последовательностей нулей и единиц и при этом не будет упомянут в нашем списке. Для этого рассмотрим элементы, расположенные по диагонали и обведенные рамкой. Рассмотрим a₀: если этот элемент равен 0, начнем нашу последовательность с 1, и наоборот. Так мы определим первый член нашей последовательности. Перейдем к b₁ если этот элемент равен 0, то вторым членом нашей последовательности будет 1. Если же, напротив, этот элемент равен 1, то вторым членом последовательности будет 0. В общем случае для определения n– го члена нашей последовательности мы будем рассматривать соответствующий элемент на диагонали и записывать противоположное ему значение. Таким образом, мы получим последовательность, все члены которой будут иметь значение 0 или 1, следовательно, эта последовательность будет принадлежать к рассматриваемому множеству. Например, если наш список будет начинаться так:

то первыми членами составленной нами последовательности будут 1, 0, 0.

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

Мы посвятили несколько страниц объяснению основных понятий теории множеств не только для того, чтобы даже сформулировать парадокс Рассела. Доказательство того, что множество последовательностей нулей и единиц не является счетным, читатель может счесть не более чем виртуозным упражнением, однако оно позволит нам показать в главе 5, что существуют задачи, с которыми не могут справиться даже компьютеры, и установить пределы «сну разума», о котором говорится в названии этой книги. Мы также надеемся, что смогли продемонстрировать читателю, сколько тайн встречается тем, кто путешествует по миру бесконечных множеств.

* * *

ПРЕПОДАВАНИЕ ТЕОРИИ МНОЖЕСТВ В ШКОЛЕ

В 70-е годы группа последователей французской математической группы Бурбаки, которые, однако, в большинстве своем не были математиками, захотели ввести теорию множеств в курс начальных школ Европы. В этой учебной программе натуральные числа объяснялись как кардинальные числа конечных множеств. 0 определялся как кардинальное число пустого множества, а сложение 2 и 3 объяснялось как объединение множества из 2 элементов с другим множеством из 3 элементов, при этом не важно, что результат будет обозначаться 5, важно, что 2 + 3 = 3 + 2, так как не имеет значения, в каком порядке мы будем объединять элементы множеств. Как рассказывал Пьер Картье, в то время бывший секретарем группы Бурбаки, в результате этой политики в сфере образования дети возвращались из школы домой и плакали: «Мама, я не хочу быть множеством».

Диаграммы Венна — наиболее типичный способ представления множеств.

* * *

Парадокс Рассела

Бертран Рассел познакомился с теорией множеств в 1896 году. Ему было довольно трудно принять ее: автор книги, из которой Рассел узнал о существовании этой теории, входил в число тех, кто считал, что теория Кантора была недостаточно строгой, и уподоблял ее теологии, а Рассел в этот период стремился к максимальной научной строгости. Однако позднее он понял, что многие обвинения в адрес Кантора были необоснованными, и включил идеи этого немецкого математика в последнее издание «Начал математики», вышедшее в мае 1903 года. Знакомясь с новой литературой, чтобы дополнить последнее издание книги, Рассел открыл для себя труд Готлоба Фреге, который предвосхитил многие из его открытий, опередив Рассела на 20 лет.