Восемь этюдов о бесконечности. Математическое приключение - [52]
В это довольно трудно поверить, но мощность множества чисел, делящихся на пухплекс в степени пухплекса, равна мощности множества алгебраических чисел.
ℵ: бо́льшая бесконечность – мощность континуума
Доказать, что множество счетно, совсем не трудно. Нужно всего лишь найти одно-однозначное и сюръективное соответствие с множеством натуральных чисел. Проблема сводится к следующему: чтобы доказать, что то или иное множество счетно, достаточно показать, что его элементы могут быть расположены в некотором последовательном порядке, но, чтобы доказать, что множество несчетно, необходимо доказать, что не существует абсолютно никакого способа расположить его элементы последовательно. Это похоже на «задачу» доказательства, что в комнате есть по меньшей мере один муравей, в сравнении с задачей доказательства, что нигде в комнате ни одного муравья точно нет. Как только мы найдем хотя бы одного муравья, мы получим доказательство первого утверждения, но то, что мы не находим муравьев в данный момент, совершенно не означает, что какой-нибудь муравей не найдется позже.
Как я уже отмечал, в 1891 г. Георг Кантор предложил замысловатый метод, помогающий доказать невозможность подсчета количества разнообразных объектов, – он называется «диагональным методом Кантора». Мы уже встречались с этим методом, когда профессор Финкельштейн-Островский-Канторович доказывал, что в бесконечной гостинице невозможно разместить числа, заключенные между 0 и 1, десятичное представление которых содержит только цифры 0 и 1. При помощи того же самого метода можно доказать, что и множество всех чисел, заключенных между 0 и 1, несчетно (докажите это!). В этом нет ничего неожиданного, поскольку множество «чисел, заключенных между 0 и 1, десятичное представление которых содержит только цифры 0 и 1» – это собственное подмножество множества всех чисел, заключенных между 0 и 1. Кроме того, если вспомнить, что любое существующее число может быть записано в двоичной системе счисления с использованием только цифр 0 и 1, можно легко убедиться, что мощность этих двух множеств должна быть одинаковой (почему?).
Бесконечные множества чисел, которые невозможно расположить в последовательном порядке, называются – что и неудивительно – несчетными. Множество всех точек на числовой прямой, заключенных между 0 и 1, несчетно, и его мощность не равна ℵ>0. Следовательно, для обозначения мощности множества всех вещественных чисел (или любого отрезка прямой вещественных чисел) нужен новый символ! В качестве такого символа используют букву ℵ[50]. Говорят, что ℵ – мощность континуума. Однако следует отметить, что несчетные множества не всегда имеют мощность ℵ.
Слова, слова, слова
Поскольку концепция канторовой диагонали не только красива, но и важна, я объясню ее еще раз – теперь на примере доказательства, что множество всех слов бесконечной длины, составленных с использованием только двух букв (a и b), невозможно подсчитать. Другими словами, такое множество несчетно.
Если вы уже поняли объяснение, которое профессор Финкельштейн-Островский-Канторович дал Омеге относительно чисел в десятичной системе счисления, у вас не должно вызвать затруднений и следующее изложение. Речь идет в точности о том же самом, только на другом примере. Если вы не вполне поняли первое объяснение, я надеюсь, что вы поймете его на этот раз.
Доказательство будет строиться от противного, то есть мы предположим, что справедлива противоположная гипотеза: все такие слова можно расположить в некой последовательности. Затем мы увидим, что это предположение приводит к противоречию, что означает, что наша исходная гипотеза была ложной.
Вот расположение слов:
Применяя диагональный метод Кантора, аналогично тому, как мы действовали с числами, заключенными между 0 и 1, образуем новое слово А0, которое не содержится где бы то ни было в представленном в таблице множестве, в каком бы порядке мы ни располагали слова. Внимательно посмотрите на таблицу и обратите внимание на подчеркнутые буквы, стоящие на диагонали. Новое слово А0 будет построено следующим образом: его первая буква будет отличной от первой буквы слова А1 (поскольку первая буква в А1 – а, мы возьмем букву b); вторая буква будет отличной от второй буквы слова А2 (раз это буква b, мы используем букву а); третья буква будет отличной от третьей буквы слова А3 (на этот раз возьмем букву b) – и так далее.
Итак, наше новое слово A0 = babbbbabb…
Я предоставлю умудренному читателю самостоятельно убедиться, что слово А0 никоим образом не может встретиться в исходном бесконечном списке (то есть совпасть с каким бы то ни было его словом), потому что оно не может не отличаться от любого слова A
