Число 0,232233222333222… также вычислимо, потому что можно легко найти его десятичное представление любой длины. Примечание: это число не рационально! Не хотите ли доказать это утверждение?
Алгебраические числа также вычислимы, потому что существуют разные методы решения любого уравнения вида
и определения его корней с любой точностью, какой только можно пожелать.
А кроме того, есть числа, не принадлежащие ни к одной из названных категорий, но все равно вычислимые. Два из них – числа π и e.
Что такое π?
Десятичное представление иррационального числа π бесконечно, никогда не повторяется и не имеет алгебраической формулы. Тем не менее и это число вычислимо.
Еще Архимед знал о существовании алгоритма, позволяющего получить десятичное представление π со всевозрастающей точностью. Этот алгоритм был основан на построении правильных многоугольников с n вершинами, вписанных в окружность. По мере стремления n к бесконечности форма такого многоугольника стремится к окружности.
В 1593 г. французский математик Франсуа Виет нашел замечательную формулу для вычисления π при помощи набора вложенных радикалов{33}.
Помимо исключительной внутренней красоты этой формулы в ней есть еще один чрезвычайно важный элемент – стоящее в ее конце многоточие, которое означает «продолжать ту же процедуру до бесконечности». Трудно поверить, но это был первый случай, когда бесконечный процесс был явно обозначен в математической формуле.
Это напоминает мне одну историю о Людвиге Витгенштейне: он, как рассказывают, предлагал слушателям своих лекций вообразить человека, который бормотал на ходу: «…5, 1, 4, 1, запятая, 3 – всё!» Когда этого человека спросили, что это такое он делает, он ответил, что только что закончил перечисление десятичного представления числа π от конца к началу, чем занимался до этого целую вечность. Эта история кажется гораздо более абсурдной, чем рассказ о человеке, который решил сесть и записать десятичное представление π от начала до конца – и будет заниматься этим вечно. Почему?
Но вернемся к числу π. Интересно отметить, что многие другие помимо Архимеда и Виета пытались вычислить десятичное представление числа π, и все эти попытки в конце концов приводили к нескончаемым столбцам или нескончаемым операциям умножения. Однако в 1656 г. английский математик Джон Валлис открыл следующую формулу:
Если попарно перемножить последовательные сомножители, формулу можно записать в следующем виде:
Это бесконечное равенство действительно да- ет все следующие и следующие цифры десятичного представления π.
Интересно отметить, что именно Джон Валлис впервые использовал в 1655 г. символ бесконечности ∞ (по правде говоря, в своей работе о вычислении площадей под названием «О конических сечениях» (De sectionibus conicis) он использовал выражение 1/∞).
В 1671 г. шотландский математик и астроном Джеймс Грегори предложил еще одну формулу для вычисления π в виде бесконечной суммы:
Какая красивая формула! Простая, изящная и эффектная.
Этот рассказ был бы, однако, неполным, если бы я не упомянул, что сегодня честь открытия приведенной выше формулы приписывают индийскому математику XIV в. Мадхаве, который, по-видимому, знал ее задолго до Грегори. Некоторые исследователи утверждают, что Мадхава не только знал эту формулу, но и нашел способ вычисления отклонения ее результатов от истинного значения π и даже разработал еще одну формулу для вычисления π, дающую гораздо более прямое приближение к значению этого числа, чем формула Грегори. Вот она:
Честно говоря, тут я воспользовался случаем, чтобы показать вам некоторые особенно красивые формулы для вычисления значения π. Чтобы доказать, что π – вычислимое число, достаточно было бы показать всего лишь одну из них.
Что такое е?
Число Эйлера е также не относится к алгебраическим числам, но, поскольку оно определено как предел некоторой последовательности, его значение также вычислимо, и, как и в случае числа π, есть несколько способов этого вычисления. Ниже я привожу несколько изящных и (сравнительно) простых примеров. Возможно, вы уже знакомы с первыми двумя.
Ибо в конечном счете что же он такое – человек во Вселенной? Небытие в сравнении с бесконечностью, все сущее в сравнении с небытием, нечто среднее между всем и ничем. Бесконечно далекий от понимания этих крайностей – конца мироздания и его начала…
Невычислимые вещественные числа
А существуют ли числа вещественные, но невычислимые? Они не просто существуют – их очень много. Собственно говоря, поскольку, как мы отметили раньше, количество алгоритмов счетно, мощность множества вычислимых чисел должна быть равна ℵ0. А поскольку мощность множества вещественных чисел равна ℵ, это означает, что должно существовать ℵ вещественных чисел, которые не являются вычислимыми! Другими словами, невычислимы почти все вещественные числа. Для определения большинства вещественных чисел не существует алгоритмов. Можно ли говорить о невычислимых числах? Можете ли вы найти пример вещественного числа, которое было бы невычислимым?
Некоторые математики утверждают, что во всем наборе вещественных чисел нет необходимости, и для всех практических целей вполне можно обойтись одними только вычислимыми числами.
Тем, кто хочет узнать больше (гораздо больше!) о вычислимых числах и их интереснейшей связи с концепциями Алана Тьюринга, я настойчиво рекомендую прочитать книгу «Новый ум короля. О компьютерах, мышлении и законах физики» (1989)[59], которую написал британский математик, философ и обладатель бесчисленных (можно ли сказать «бесконечных»?) наград и званий сэр Роджер Пенроуз.
Сэр Роджер Пенроуз разработал в сотрудничестве со своим отцом, Лайонелом Пенроузом, несколько невозможных геометрических фигур и послал их голландскому художнику М. К. Эшеру (одному из героев книги «Гёдель, Эшер, Бах»), а тот использовал их в своих гравюрах. К числу наиболее знаменитых из этих фигур относятся две следующие{34}:
Треугольник Пенроуза
Лестница Пенроуза – нескончаемое путешествие
Только представьте себе, как вы поднимаетесь по этой лестнице – все поднимаетесь и поднимаетесь и все же все время возвращаетесь в одну и ту же точку. Эшер добавил череду вечно поднимающихся и вечно спускающихся монахов: все они оказываются в том же месте, с которого начали движение.
Ну что же, мы познакомились с несколькими интересными концепциями, но теперь нам пора вернуться к теории Кантора и узнать, что бесконечность бесконечна.
Бесконечность бесконечна
Существует ли множество чисел, мощность которого больше мощности множества вещественных чисел? Есть ли вообще «наибольшее» значение мощности?
Тот факт, что множества, имеющего наибольшую мощность, не существует, доказал сам Кантор. Собственно говоря, в этом случае доказательство Кантора было конструктивным, потому что он показал, что для любого данного множества всегда можно найти множество еще большей мощности и как это сделать. Такие множества называются показательными множествами, или булеанами.
Булеаны
Прежде чем мы перейдем к самой теореме, познакомимся с одной новой концепцией.
Пусть дано множество А. Множество, состоящее из всех подмножеств А, называется булеаном А и обозначается Р(А).
Предположим, например, что A = {17, 42, 0}. Тогда булеан Р(А) будет построен следующим образом: P(A) = {{}, {17}, {42}, {0}, {17, 42}, {17, 0}, {42, 0}, {17, 42, 0}}.
Символ «{}» обозначает пустое множество, которое считается подмножеством любого множества А. Возможно, вы помните, что ранее в этой книге мы использовали для обозначения пустого множества символ ∅. Оба эти символа – {} и ∅ – обозначают одно и то же. Отметим, что множество А также считается подмножеством самого себя. Если подсчитать количество подмножеств, окажется, что в самом множестве А содержится три элемента, а в булеане А – восемь элементов.
Я уверен, что вам тут же пришло в голову равенство 2³ = 8. Случайна ли эта связь? Нет, не случайна.
Если #A = n, то #P(A) = 2n (где # – количество элементов).
Доказательство того, что булеан множества, содержащего n элементов, содержит 2n подмножеств, получено при поддержке Уильяма Шекспира и состоит в следующем: каждый элемент исходного множества должен решить, «быть или не быть» элементом каждого конкретного подмножества. Следовательно, поскольку у каждого элемента есть две возможности относительно каждого отдельного подмножества, суммарное число возможностей для n элементов равно 2n.
Чтобы пояснить эту концепцию на конкретном примере, предположим, что мы набираем подмножество из элементов множества A = {17, 42, 0}. 17 и 0 «решают» стать элементами этого подмножества, а 42 отказывается. В сочетании эти решения дают подмножество {17, 0}. Решения каждого из элементов множества однозначно определяет состав каждого конкретного подмножества; следовательно, количество подмножеств равно количеству уникальных решений, то есть 2 × 2 × 2 × … × 2 = 2n.
Ч. т. д.
Мощность любого множества А строго меньше, чем мощность P(A).