Хавьер Фресан - Том. 22. Сон разума. Математическая логика и ее парадоксы

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

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

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

Напомним, что а n, Ь n и с n принимают только значения 0 и 1. Составим элемент, который будет принадлежать к множеству бесконечных последовательностей нулей и единиц и при этом не будет упомянут в нашем списке. Для этого рассмотрим элементы, расположенные по диагонали и обведенные рамкой. Рассмотрим a 0 : если этот элемент равен 0, начнем нашу последовательность с 1, и наоборот. Так мы определим первый член нашей последовательности. Перейдем к b 1 если этот элемент равен 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 лет.