Итак, что же такое вещественное число? В общем случае это число с бесконечным числом знаков после запятой.
Но знаете, я не особо верю в бесконечно длинные числа сами по себе. Ведь у нас нет к ним доступа, мы не можем ими напрямую оперировать. У нас есть конечная вселенная, максимальная скорость света, текущее время обозначается конечным числом. Мы никогда не сможем получить бесконечно длинное число, даже если захотим. У нас есть доступ только к конечным ресурсам.
Но есть один способ сделать бесконечное через конечное - алгоритмы. Мы можем записать бесконечно длинное число некоторым алгоритмом, который получает на вход номер знака, а возвращает цифру нашего бесконечного числа. Мы такими алгоритмами пользуемся постоянно, например: sqrt(2), pi, e. Для любого N мы можем вычислить N-й знак любого нужного нам числа. Ну, в теории. И таким образом мы можем представить все нужные нам вещественные числа.
Для бесконечно длинных чисел существует так называемый диагональный аргумент, который доказывает что бесконечность вещественных чисел больше бесконечности натуральных.
Начинается он с того что нам нужно взять и каждому бесконечно длинному вещественному числу сопоставить некоторое натуральное число, пронумеровать их и выписать в бесконечную таблицу. Но давайте не трогать просто бесконечные числа, и вместо этого поставим вместо них все известные нам алгоритмы. Всё-равно ведь мы можем вычислить всё до нужного нам знака, да? Да и что такое алгоритм? Это набор символов, а значит любой конечный алгоритм можно представить конечным натуральным числом, значит их множество счётно. Ну и надо брать только те алгоритмы, которые завершаются. Ведь очевидно, что бесконечно работающая программа для какого-то знака не способна выдать этот знак.
Окей, таблица есть, а дальше в диагональном аргументе говорится следующее: берём каждую цифру на диагонали и заменяем её на другую, таким образом у нас получится новое бесконечно длинное число, которое не имеется в изначальной таблице. Но если мы считаем что бесконечные числа не могут существовать сами по себе, то это немного не так. Сам этот процесс выписывания диагонального числа тоже является алгоритмом, который перебирает другие алгоритмы, а значит существует два варианта:
- Этот алгоритм не противоречив, всегда завершается и описывает какое-то число, которое уже есть в множестве, просто потому что он алгоритм с данными свойствами.
- Этот алгоритм противоречив (например, нарушает проблему останова) или не способен остановиться, а значит изначально не был в этом множестве, и вообще из него нельзя сформировать контр-аргумент.
И так на самом деле с любым возможным алгоритмом: что бы мы ни делали, мы не сможем получить число, не находящееся в этом множестве, потому что всё что мы делаем является алгоритмом, будь то псевдослучайные числа, полный перебор или вычисление задачи трёх тел.
И что самое странное, мы даже не можем придумать вселенную, которая была бы основана не на алгоритмах.
Мы ограничены нашими законами физики и законами логики.
Но раз у нас нет никакого доступа к этим вещественным числам, можем они существуют каким-то другим образом сами по себе? Может быть, но я не вижу никакого смысла использовать их в наших рассуждениях, ведь они не могут возникнуть ни в каком вычислении. А значит, согласно Бритве Оккама, их можно не учитывать.
Поэтому:
Бесконечность вещественных чисел равна бесконечности натуральных чисел.
Автор: Шепрут Илья. 1 февраля 2022.
Решение состоит в том, что не всякое вещественное число можно сгенерировать алгоритмом.
Доказательство - тот же диагональный аргумент, только мы сопоставляем алгоритмы (которые мапятся на натуральные числа) с вещественными и конструируем вещественное число, для которого нет алгоритма.