– А если выселить из гостиницы все натуральные числа? Не поможет ли это? – все же не сдавалась Омега.
– Ничуть не поможет, – уверенно отвечал профессор.
– Как же может быть, что в бесконечной гостинице, тем более пустой, не хватит места для одной-единственной группы постояльцев? – по-прежнему не желала мириться с этой неприятной новостью Омега.
– Не упрямьтесь, – сказал профессор. – Вместо того чтобы искать способы расселения этих чисел, позвольте, я докажу вам, что в бесконечной гостинице не найдется места не только для всех чисел между 0 и 1, но даже и для всех чисел, записанных с использованием только цифр 0 и 1.
– Вы серьезно? – спросила администратор.
– Профессор Финкельштейн-Островский-Канторович всегда серьезен, когда говорит о математике или музыке, – ответил он, говоря о себе в третьем лице.
– Ну хорошо. Тогда извольте объясниться. – И Омега приготовилась выслушать его объяснение.
Объяснение профессора Финкельштейна-Островского-Канторовича
– Прежде всего мы должны договориться, что записываем все числа в бесконечной нотации. Я хочу сказать, что вместо 0,101 мы будем писать 0,101000… Теперь начнем с предположения, что нам все же удалось решить эту задачу, и мы смогли найти в гостинице номера для всех чисел.
– Я полагаю, вы собираетесь показать мне доказательство от противного, не так ли? Как это типично для математиков! – сказала Омега.
– Вот как будет выглядеть распределение чисел по номерам: число А1 будет в номере 1, число А2 – в номере 2, число А3 – в номере 3 и так далее. Кто же такие все эти «А»? Мы сможем узнать их, потому что под своими «новыми» именами они будут выглядеть следующим образом:
A1 = 0,a11a12a13a14a15…
A 2 = 0,a21a22a23a24a25…
A 3 = 0,a31a32a33a34a35…
A 4 = 0,a41a42a43a44a45…
A 5 = 0,a51a52a53a54a55…
..……………………
Другими словами, aik – это k-я цифра после запятой в числе, которое будет жить в i-м номере. При этом следует помнить, что любая цифра, обозначенная aik, – это либо 0, либо 1. Приведу пример. Предположим, что число 0,111000110010… живет в номере 3. Следовательно, для этого числа a31 = 1, a32 = 1, a33 = 1, a34 = 0, a35 = 0… – дальше все очевидно. Так вот, – продолжал профессор, – я могу предъявить вам число, которое находится между 0 и 1, то есть входит в группу постояльцев, приехавших с Дельты-Континуума, но не относится к числам, живущим в гостинице. Этот факт докажет, что найти в гостинице место для всех чисел, расположенных между 0 и 1, невозможно, потому что список, который мы составили, получился слишком общим.
Обозначим число, не живущее в гостинице, В. Разумеется, мы запишем его в виде B = 0, b1b2b3b4… где bi может быть равно либо 0, либо 1, и образуем его так, чтобы никакое bi не было равно aii (aii – это все числа, стоящие на диагонали составленного нами списка). Как мы это сделаем?
Идея чрезвычайно проста. Если aii = 0, то bi должно быть равно 1. Если же aii = 1, то bi должно быть равно 0.
Приведу пример. Допустим, мы как-то расположили все числа от 0 до 1, в записи которых используются только цифры 0 и 1. Они расположены совершенно в произвольном порядке, но предположим, что мы расставили их следующим образом:
A1 = 0,010010001…
A 2 = 0,010101010…
A 3 = 0,110110110…
A 4 = 0,100110111…
A 5 = 0,011111110…
..……………………
Сформируем теперь число В. Цифру b1 мы определим равной 1, потому что a11 = 0 (первая цифра после запятой в числе А1 равна 0); цифра b2 должна быть равна 0, потому что a22 = 1 (a22 – это вторая цифра после запятой в числе А2); цифра b3 должна быть равна 1, потому что a33 = 0. И так далее.
– Но откуда вы знаете, что число В не живет в гостинице? – не смогла смолчать Омега.
– Это совершенно очевидно. Первая цифра после запятой в числе В, то есть b1, должна отличаться от первой цифры после запятой в числе A1 (то есть от цифры a11). Мы уверены в этом, потому что мы специально построили число В так, чтобы на этом месте стояла другая цифра. Отсюда очевидно, что число В не может быть равно числу А1, даже если бы все остальные его цифры в точности совпадали со всеми остальными цифрами числа А 1.
Перейдем теперь ко второй цифре после запятой в числе В, то есть к цифре b2. Она должна отличаться от второй цифры после запятой в числе А2 – по той же самой причине. Следовательно, каковы бы ни были другие цифры числа В, это число никак не может быть равно числу А2.
Продолжим аналогичные рассуждения для всех остальных цифр числа В – для всего их бесконечного количества. Результат будет тем же самым для каждой из них. В числе В всегда будет по меньшей мере одна цифра, отличающая его от чисел, входящих в группу Ai. Следовательно, мы должны заключить, что число В не может быть равно никакому конкретному числу А. Другими словами, число В не является постояльцем гостиницы. Оно приехало с Дельты-Континуума вместе со всеми своими друзьями, но, в отличие от них, в гостинице не поселилось.
– Если это так, я внесу число В в самое начало списка, перед А1! – Омега запрыгала на месте, чрезвычайно возбужденная идеей, которая только что пришла ей в голову. Надо сказать, что разговоры с Омегой не были трудными для профессора, но иногда раздражали его.
– Да вы попросту ничего не поняли из моего объяснения! Смотрите: даже если вы добавите число В в начало списка, я всегда смогу сформировать некое новое число – назовем его Y, – которого в списке не будет, точно так же, как я сформировал число В.
– Вы правы. Но я все равно не понимаю, как может быть, что кому-то из постояльцев не найдется места в бесконечной гостинице.
– Это значит, что, хотя количество номеров в вашей гостинице и бесконечно, количество постояльцев, которые хотят в ней поселиться, еще более бесконечно, – объяснил профессор.
