Остается бесконечное количество свободных номеров.
Но если каждое число, делящееся на 3, поселить в номере, соответствующем одной трети его значения, гостиница окажется полностью заселенной.
Это показывает нам, что множество чисел, делящихся на 3, – множество счетно-бесконечное (потому что, как можно видеть из таблицы, существует биекция между ним и множеством натуральных чисел).
Множество чисел, кратных гуголплексу, также бесконечно и также счетно, как и множество чисел, кратных пухплексу. Попытайтесь представить себе, какое огромное количество чисел придется пройти, прежде чем мы доберемся до пухплекса! После этого нужно будет пройти еще столько же, чтобы достигнуть удвоенного пухплекса! Тем не менее мощность множества чисел, кратных пухплексу, равна мощности множества чисел, кратных 21, а также мощности множества четных чисел и множества натуральных чисел.
Мощность всех этих множеств – ℵ0.
Хотите – верьте, хотите – нет!
Наши бледные рассуждения скрывают от нас бесконечное.
Каникулы алгебраических чисел в отеле Гильберта
Наша экспедиция в гостиницу Гильберта показала, что не всякое множество может в ней разместиться, хотя гостиница и бесконечна. Количество элементов множества всех чисел, заключенных между 0 и 1, оказалось слишком большим, чтобы все они смогли поселиться в гостинице.
Множество этих чисел несчетно-бесконечно, так как между ним и множеством натуральных чисел нет одно-однозначного и сюръективного соответствия. Существуют ли другие множества чисел, бесконечные, но несчетные, то есть такие множества, которые невозможно разместить в бесконечной гостинице?
Интересный пример множества этого типа дает множество неалгебраических чисел, которые мы сейчас определим. Но сначала проясним, что такое алгебраическое число.
Вспомним, что рациональное число – это число q, которое может быть записано в виде отношения двух целых чисел
Можно дать другое, эквивалентное определение: число q – рациональное число тогда, и только тогда, когда оно является решением уравнения «первой степени», а именно уравнения вида
где коэффициенты a и b – целые числа.
Ясно, что любое рациональное число
удовлетворяет равенству
и, следовательно, является решением уравнения первой степени
Например, число
является решением уравнения
Что же такое тогда алгебраическое число?
Число считается алгебраическим, если оно является корнем (то есть решением) уравнения вида:
,
где все коэффициенты ak – целые числа.
Число, не являющееся алгебраическим, называют «трансцендентным числом».
Левая часть приведенного выше уравнения называется многочленом (или полиномом) n-й степени, если n не равно 0.
Из этого определения немедленно следует, что все рациональные числа относятся к числам алгебраическим. Однако есть и иррациональные алгебраические числа{30}. Вот несколько примеров:
√2 – алгебраическое число, так как является решением уравнения x² − 2 = 0.
Кубический корень из
– алгебраическое число, так как является решением уравнения
– алгебраическое число (но не вещественное число), так как является решением уравнения x² + 1 = 0.
Золотое сечение ϕ – алгебраическое число, так как является решением уравнения x² − x − 1 = 0.
Короче говоря, алгебраические числа «многочисленны», потому что «многочисленны» уравнения с многочленами вида
С учетом этого следующее утверждение может показаться несколько удивительным:
Множество алгебраических чисел счетно.
Доказательство. Рассмотрим уравнение
Предположим, что an – положительное число. Если это не так, мы можем умножить все уравнение на (–1); получившееся уравнение будет иметь те же корни.
Подобно тому, как мы разбирались с расселением рациональных чисел в гостинице, определим для каждого многочлена «высоту» Н.
Символ |m| обозначает абсолютное значение (или модуль) числа. Если число положительно, его абсолютное значение равно ему самому: | 37 | = 37. Если число отрицательно, абсолютное значение становится положительным: |–234 | = 234.
Теперь мы можем выписать все уравнения (некоторые из которых не имеют решений) в порядке возрастания высоты.
Например, для Н = 1 существует всего один многочлен, и он представляет собой просто 1, то есть не зависит от х, и дает уравнение 1 = 0, не имеющее решений. Это уравнение не имеет смысла и не дает нам никаких алгебраических чисел.
Для Н = 2 мы получаем два уравнения: х = 0 и 2 = 0. Первое дает алгебраическое число 0, а второе снова оказывается бессмысленным и не имеет корней.
Для Н = 3 получаются следующие уравнения: 3 = 0, х – 1 = 0, 2х = 0, х + 1 = 0, и наконец, х² = 0. Первое из этих уравнений не дает алгебраических чисел, а из остальных мы получаем два новых алгебраических числа: 1 и –1.
Я надеюсь, что основная идея понятна.
Дойдя до Н = 5, мы встретимся с √2 (убедитесь в этом самостоятельно). Для каждого значения высоты существует конечное количество уравнений, и каждое уравнение имеет конечное число решений; следовательно, при каждом значении высоты мы добавляем конечное количество алгебраических чисел. Это доказывает, что множество алгебраических чисел – это на самом деле набор, состоящий из счетного числа конечных множеств. Следовательно, алгебраические числа легко можно разместить в бесконечной гостинице Гильберта. Это означает также, что множество алгебраических чисел счетно и его мощность – ℵ0.
В это довольно трудно поверить, но мощность множества чисел, делящихся на пухплекс в степени пухплекса, равна мощности множества алгебраических чисел.
ℵ: бо́льшая бесконечность – мощность континуума
Доказать, что множество счетно, совсем не трудно. Нужно всего лишь найти одно-однозначное и сюръективное соответствие с множеством натуральных чисел. Проблема сводится к следующему: чтобы доказать, что то или иное множество счетно, достаточно показать, что его элементы могут быть расположены в некотором последовательном порядке, но, чтобы доказать, что множество несчетно, необходимо доказать, что не существует абсолютно никакого способа расположить его элементы последовательно. Это похоже на «задачу» доказательства, что в комнате есть по меньшей мере один муравей, в сравнении с задачей доказательства, что нигде в комнате ни одного муравья точно нет. Как только мы найдем хотя бы одного муравья, мы получим доказательство первого утверждения, но то, что мы не находим муравьев в данный момент, совершенно не означает, что какой-нибудь муравей не найдется позже.
Как я уже отмечал, в 1891 г. Георг Кантор предложил замысловатый метод, помогающий доказать невозможность подсчета количества разнообразных объектов, – он называется «диагональным методом Кантора». Мы уже встречались с этим методом, когда профессор Финкельштейн-Островский-Канторович доказывал, что в бесконечной гостинице невозможно разместить числа, заключенные между 0 и 1, десятичное представление которых содержит только цифры 0 и 1. При помощи того же самого метода можно доказать, что и множество всех чисел, заключенных между 0 и 1, несчетно (докажите это!). В этом нет ничего неожиданного, поскольку множество «чисел, заключенных между 0 и 1, десятичное представление которых содержит только цифры 0 и 1» – это собственное подмножество множества всех чисел, заключенных между 0 и 1. Кроме того, если вспомнить, что любое существующее число может быть записано в двоичной системе счисления с использованием только цифр 0 и 1, можно легко убедиться, что мощность этих двух множеств должна быть одинаковой (почему?).
Бесконечные множества чисел, которые невозможно расположить в последовательном порядке, называются – что и неудивительно – несчетными. Множество всех точек на числовой прямой, заключенных между 0 и 1, несчетно, и его мощность не равна ℵ0. Следовательно, для обозначения мощности множества всех вещественных чисел (или любого отрезка прямой вещественных чисел) нужен новый символ! В качестве такого символа используют букву ℵ[50]. Говорят, что ℵ – мощность континуума. Однако следует отметить, что несчетные множества не всегда имеют мощность ℵ.
Слова, слова, слова
Поскольку концепция канторовой диагонали не только красива, но и важна, я объясню ее еще раз – теперь на примере доказательства, что множество всех слов бесконечной длины, составленных с использованием только двух букв (a и b), невозможно подсчитать. Другими словами, такое множество несчетно.
Если вы уже поняли объяснение, которое профессор Финкельштейн-Островский-Канторович дал Омеге относительно чисел в десятичной системе счисления, у вас не должно вызвать затруднений и следующее изложение. Речь идет в точности о том же самом, только на другом примере. Если вы не вполне поняли первое объяснение, я надеюсь, что вы поймете его на этот раз.
Доказательство будет строиться от противного, то есть мы предположим, что справедлива противоположная гипотеза: все такие слова можно расположить в некой последовательности. Затем мы увидим, что это предположение приводит к противоречию, что означает, что наша исходная гипотеза была ложной.
Вот расположение слов: