Неконструктивность континуума
Sep. 6th, 2011 12:54 pmПо мотивам возникшего на пустом месте обсуждения, возможно, стоит написать чуть подробнее, почему именно континуум и мощности выше счетных бесконечных множеств не существуют в конструктивной математике. Разъяснить этот факт можно разными способами. Я же выберу, может быть, не самый корректный, но зато простой с точки зрения теории вычислимости, имея в виду аудиторию, знакомую с «computer science».
Итак, оттолкнемся от определения множества вещественных чисел на отрезке [0, 1], скажем, по «Теории функций вещественной переменной» Натансона: это множество всех бесконечных последовательностей из нулей и единиц. То есть от 0,000… = 0 до 0,111… = 1 в бинарной системе исчисления. Вскоре после определения идут хитрые выкладки, показывающие в конечном итоге, что мощность обозначенного множества больше, чем у множества натуральных чисел. Сама выкладка, конечно, корректна и вполне могла бы иметь место в конструктивной математике, если бы только сам объект [0, 1] был построен, а не просто назван. Поэтому опустим известные из стандартного курса теории множеств далеко идущие следствия гипотезы о существовании континуума: арифметику кардинальных чисел, континуум-гипотезу, противоречия в классическом варианте теории и непротиворечивые системы аксиом.
Вместо этого, попробуем составить конструктивное определение [0, 1]. По определению мы видим, что каждый элемент данного множества есть по сути функция из N в {0, 1}, возвращающая i-ый знак после запятой. Согласно самой теории множеств, множество таких функций обладает мощностью континуума. Однако, множество тех функций, которые можно построить конструктивно, ограничено вычислимыми функциями, а их, в свою очередь, счетное множество, а не континуум. На практике это означает, что любое известное трансцендентное число, например π или e, описывается вычислимой функцией. Обычно последняя возвращает не i-ый знак после запятой, а i-ый элемент последовательности рациональных чисел (их счетное множество), сумма которой имеет предел, равный кодируемому числу.
Вещественные числа, которые описываются вычислимыми функциями, называются рекурсивными вещественными числами. Они многократно упоминались ранее, и их, как известно, счетное множество. Таким образом, так как конструктивно построить хотя бы одно вещественное число, которое бы выходило за рамки рекурсивных вещественных чисел, нельзя, континуум и оказывается неконструктивной сущностью.
P. S. Надо же, какой наброс удался, давно так не получалось.
Итак, оттолкнемся от определения множества вещественных чисел на отрезке [0, 1], скажем, по «Теории функций вещественной переменной» Натансона: это множество всех бесконечных последовательностей из нулей и единиц. То есть от 0,000… = 0 до 0,111… = 1 в бинарной системе исчисления. Вскоре после определения идут хитрые выкладки, показывающие в конечном итоге, что мощность обозначенного множества больше, чем у множества натуральных чисел. Сама выкладка, конечно, корректна и вполне могла бы иметь место в конструктивной математике, если бы только сам объект [0, 1] был построен, а не просто назван. Поэтому опустим известные из стандартного курса теории множеств далеко идущие следствия гипотезы о существовании континуума: арифметику кардинальных чисел, континуум-гипотезу, противоречия в классическом варианте теории и непротиворечивые системы аксиом.
Вместо этого, попробуем составить конструктивное определение [0, 1]. По определению мы видим, что каждый элемент данного множества есть по сути функция из N в {0, 1}, возвращающая i-ый знак после запятой. Согласно самой теории множеств, множество таких функций обладает мощностью континуума. Однако, множество тех функций, которые можно построить конструктивно, ограничено вычислимыми функциями, а их, в свою очередь, счетное множество, а не континуум. На практике это означает, что любое известное трансцендентное число, например π или e, описывается вычислимой функцией. Обычно последняя возвращает не i-ый знак после запятой, а i-ый элемент последовательности рациональных чисел (их счетное множество), сумма которой имеет предел, равный кодируемому числу.
Вещественные числа, которые описываются вычислимыми функциями, называются рекурсивными вещественными числами. Они многократно упоминались ранее, и их, как известно, счетное множество. Таким образом, так как конструктивно построить хотя бы одно вещественное число, которое бы выходило за рамки рекурсивных вещественных чисел, нельзя, континуум и оказывается неконструктивной сущностью.
P. S. Надо же, какой наброс удался, давно так не получалось.
