В качестве доказательства несчетности действительных чисел во всех учебниках по теории множеств приводится так называемый диагональный метод Кантора (подробнее можно ознакомиться в книге «Что такое математика?», авторы Курант, Роббинс, §4. Математический анализ бесконечного. 2. Счетность множества рациональных чисел и несчетность
континуума.). Данный метод доказывает несчетность подмножества действительных чисел, принадлежащих диапазону [0,1]. Однако, если присмотреться к доказательству, становится ясно, что оно не учитывает экспоненциальный рост возможных вариантов с каждым увеличиеним порядкового номера в десятичной дроби.
Кантор рассуждает следующим образом (но только в отношении бесконечных десятичных дробей): расположем десятичные дроби произвольным образом в виде списка, далее пронумеруем их и рассмотрим диагональ. Если к каждой цифре на диагонали прибавить 1, то мы получим число, которого нет в данном списке. Вот как раз таки этот момент на интуитивном уровне вызывает сомнение.
Для того, чтобы понять о чем речь, давайте попробуем рассмотреть идею диагонального метода на следующем примере. Рассмотрим конечные дроби вида: 0,a1a2a3a4a5, сформируем из них список так, чтобы получился квадрат размером 5*5, как это показано на рисунке ниже:
Применим метод Кантора, и действительно, числа 0,22226 нет в данном квадрате. Но, оно есть в прямоугольнике 5*n5, где 5 – количество знаков после запятой, а n – количество цифр в используемой системе исчисления (в данном примере, n=10). Это объясняется тем, что количество комбинаций всех возможных дробей, длина которых составляет 5 знаков после запятой, равно n5.
Устремляя размер квадрата до бесконечности, получаем то, что называется диагональным методом Кантора. Но в бесконечность нужно устремлять не квадрат, а прямоугольник, размером m*nm, где m – количество позиций после запятой, m --> ∞.
Чтобы пронумеровать все действительные числа, принадлежащие диапазону [0, 1], их надо располагать в виде экспоненциально растущего дерева. Рассмотрим десятичные дроби, записанные в двоичной системе. Пусть k – количество знаков после запятой, n – размер алфавита системы счисления. Тогда количество возможных вариантов дробей начиная с k=1 и до ∞ будет функцией от k, это видно на рисунке ниже:
Назовем каждую строку в вышеприведенной таблице – уровнем. Таким образом k – это и номер уровня, и количество знаков после запятой одновременно.
Введем два порядковых номера:
Изобразим все двоичные десятичные дроби в виде в виде двоичного дерева, как в таблице ниже:
Каждая отдельная цифра в позиции десятичного числа располагается в отдельной ячейке. Напротив каждой такой цифры записываем 2 индекса C и L следующим образом: NCL, где N – значение цифры.
Cтановится очевидно, что С и L – это функции от k и цифр самого числа N: С = fC(k; N), L = fL(k; N). Также становится очевидно, что мы можем пронумеровать все числа из диапазона [0,1], т.к. мы последовательно проходим по каждому уровню и последовательно нумеруем все возможные комбинации на данном уровне.
Осталось вывести аналитическую зависимость для счетчиков C = fC(N) и L = fL(k;N).
Для удобства обозначим L(k;N) как Lk.
Будем считать, что L0 — 1 = 0.
Если внимательно изучить таблицу, то вырисовывается следующая закономерность:
Lk = (Lk-1 — 1)*S + N + 1,
где k >= 1, N – текущая цифра в дроби, S = |{0,1}| = 2 – размер алфавита двоичной системы счисления. Запись |A| означает мощность множества A, для конечного множества – это количество элементов в нем.
Очевидно, что C содержит сумму всех комбинаций для всех предыдущих уровней плюс L числа для текущего уровня, т.е. C(N) = Σi∈[1,k-1]2i + L(k; N).
Рассмотрим произвольное число 0,0101. Его порядковый номер C(0,0101) = 21 + 22 + 23 + L4 = 2 + 4 + 8 + 6 = 20.
Расчеты:
L1 = (L0-1)*2 + 0 + 1 = 0*2 + 0 + 1 = 1
L2 = (L1 — 1)*2 + 1 + 1 = (1 — 1)*2 + 1 + 1 = 2
L3 = (L2 — 1)*2 + 0 + 1 = (2 — 1)*2 + 0 + 1 = 3
L4 = (L3 — 1)*2 + 1 + 1 = (3 — 1)*2 + 1 + 1 = 6
Визуализация:
Рассмотрим произвольное число 0,1001. Его порядковый номер C(0,1001) = 21 + 22 + 23 + L4 = 2 + 4 + 8 + 10 = 24.
L1 = (L0 — 1)*2 + 1 + 1 = 0*2 + 1 + 1 = 2
L2 = (L1 — 1)*2 + 0 + 1 = (1 — 1)*2 + 0 + 1 = 3
L3 = (L2 — 1)*2 + 0 + 1 = (2 — 1)*2 + 0 + 1 = 5
L4 = (L3 — 1)*2 + 1 + 1 = (3 — 1)*2 + 1 + 1 = 10
Визуализация:
Таким образом мы получили алгоритм, который последовательно нумерует абсолютно все действительные числа из диапазона [0,1], при этом, если взять произвольную десятичную дробь произвольной длины, то мы можем вычислить ее уникальный прядковый номер.
P.S. Если предложенный мной алгоритм имеет ошибку, которую я, в силу своей невнимательности, не вижу – большая просьба написать об этом в комментариях.
P.P.S Если же ошибки нет – то получается, что |[0,1]| = |N|! Т.е. ВСЕ действительные числа из диапазона [0,1] можно пронумеровать!
континуума.). Данный метод доказывает несчетность подмножества действительных чисел, принадлежащих диапазону [0,1]. Однако, если присмотреться к доказательству, становится ясно, что оно не учитывает экспоненциальный рост возможных вариантов с каждым увеличиеним порядкового номера в десятичной дроби.
Кантор рассуждает следующим образом (но только в отношении бесконечных десятичных дробей): расположем десятичные дроби произвольным образом в виде списка, далее пронумеруем их и рассмотрим диагональ. Если к каждой цифре на диагонали прибавить 1, то мы получим число, которого нет в данном списке. Вот как раз таки этот момент на интуитивном уровне вызывает сомнение.
Недостаток диагонального метода
Для того, чтобы понять о чем речь, давайте попробуем рассмотреть идею диагонального метода на следующем примере. Рассмотрим конечные дроби вида: 0,a1a2a3a4a5, сформируем из них список так, чтобы получился квадрат размером 5*5, как это показано на рисунке ниже:
Применим метод Кантора, и действительно, числа 0,22226 нет в данном квадрате. Но, оно есть в прямоугольнике 5*n5, где 5 – количество знаков после запятой, а n – количество цифр в используемой системе исчисления (в данном примере, n=10). Это объясняется тем, что количество комбинаций всех возможных дробей, длина которых составляет 5 знаков после запятой, равно n5.
Устремляя размер квадрата до бесконечности, получаем то, что называется диагональным методом Кантора. Но в бесконечность нужно устремлять не квадрат, а прямоугольник, размером m*nm, где m – количество позиций после запятой, m --> ∞.
Идея моего подхода
Чтобы пронумеровать все действительные числа, принадлежащие диапазону [0, 1], их надо располагать в виде экспоненциально растущего дерева. Рассмотрим десятичные дроби, записанные в двоичной системе. Пусть k – количество знаков после запятой, n – размер алфавита системы счисления. Тогда количество возможных вариантов дробей начиная с k=1 и до ∞ будет функцией от k, это видно на рисунке ниже:
Назовем каждую строку в вышеприведенной таблице – уровнем. Таким образом k – это и номер уровня, и количество знаков после запятой одновременно.
Введем два порядковых номера:
- общий счетчик (C, Counter), используется для последовательной нумерации всех чисел из диапазона [0,1];
- счетчик уровня (L, per Level counter), используется для нумерации чисел на каждом уровне отделььно, обнуляется при переходе на следующий уровень. Для первого уровня L примет значения 1 и 2, для второго — 1, 2, 3 и 4 и т.д.
Изобразим все двоичные десятичные дроби в виде в виде двоичного дерева, как в таблице ниже:
Каждая отдельная цифра в позиции десятичного числа располагается в отдельной ячейке. Напротив каждой такой цифры записываем 2 индекса C и L следующим образом: NCL, где N – значение цифры.
Cтановится очевидно, что С и L – это функции от k и цифр самого числа N: С = fC(k; N), L = fL(k; N). Также становится очевидно, что мы можем пронумеровать все числа из диапазона [0,1], т.к. мы последовательно проходим по каждому уровню и последовательно нумеруем все возможные комбинации на данном уровне.
Осталось вывести аналитическую зависимость для счетчиков C = fC(N) и L = fL(k;N).
Для удобства обозначим L(k;N) как Lk.
Будем считать, что L0 — 1 = 0.
Если внимательно изучить таблицу, то вырисовывается следующая закономерность:
Lk = (Lk-1 — 1)*S + N + 1,
где k >= 1, N – текущая цифра в дроби, S = |{0,1}| = 2 – размер алфавита двоичной системы счисления. Запись |A| означает мощность множества A, для конечного множества – это количество элементов в нем.
Очевидно, что C содержит сумму всех комбинаций для всех предыдущих уровней плюс L числа для текущего уровня, т.е. C(N) = Σi∈[1,k-1]2i + L(k; N).
Примеры
Рассмотрим произвольное число 0,0101. Его порядковый номер C(0,0101) = 21 + 22 + 23 + L4 = 2 + 4 + 8 + 6 = 20.
Расчеты:
L1 = (L0-1)*2 + 0 + 1 = 0*2 + 0 + 1 = 1
L2 = (L1 — 1)*2 + 1 + 1 = (1 — 1)*2 + 1 + 1 = 2
L3 = (L2 — 1)*2 + 0 + 1 = (2 — 1)*2 + 0 + 1 = 3
L4 = (L3 — 1)*2 + 1 + 1 = (3 — 1)*2 + 1 + 1 = 6
Визуализация:
Рассмотрим произвольное число 0,1001. Его порядковый номер C(0,1001) = 21 + 22 + 23 + L4 = 2 + 4 + 8 + 10 = 24.
L1 = (L0 — 1)*2 + 1 + 1 = 0*2 + 1 + 1 = 2
L2 = (L1 — 1)*2 + 0 + 1 = (1 — 1)*2 + 0 + 1 = 3
L3 = (L2 — 1)*2 + 0 + 1 = (2 — 1)*2 + 0 + 1 = 5
L4 = (L3 — 1)*2 + 1 + 1 = (3 — 1)*2 + 1 + 1 = 10
Визуализация:
Выводы
Таким образом мы получили алгоритм, который последовательно нумерует абсолютно все действительные числа из диапазона [0,1], при этом, если взять произвольную десятичную дробь произвольной длины, то мы можем вычислить ее уникальный прядковый номер.
P.S. Если предложенный мной алгоритм имеет ошибку, которую я, в силу своей невнимательности, не вижу – большая просьба написать об этом в комментариях.
P.P.S Если же ошибки нет – то получается, что |[0,1]| = |N|! Т.е. ВСЕ действительные числа из диапазона [0,1] можно пронумеровать!