Счётное подмножество вещественных чисел

[Lesaje]

Известно, что множество вещественных чисел несчётно. Однако, также известно, что мы можем пронумеровать все возможные программы для компьютера для заданного языка (например, для машины Тьюринга). Более того, мы можем пронумеровать все конечные последовательности символов заданного алфавита, сколь бы длинными они не были. Очевидно, что второе множество включает первое. Второе множество - это множество всех возможных предложений в языке (например если мы нумеруем конечные последовательности символов русского алфавита). Следовательно, оно включает в себя все числа, которые можно описать словами.

Введу немного более строгую формулировку: "Описуемый" объект в некой формальной системе - это такой объект, в записи которого конечное число символов данной формальной системы. Например, в записи числа 0.(3), если мы воспользуемся русским алфавитом, будет 21 символ: "0 целых и 3 в периоде". В записи строки "abababababababababababababababab" находится 17 символов: "повтори ab 16 раз" и так далее. Очевидно, что такие числа, как e, $\pi$, $\sqrt{2}$, $\ln2$ записываются конечным числом символов, то есть являются описуемыми. Также описуемыми является большинство функций, etc.

В таком случае встаёт вопрос: зачем нам нужно несчетное множество вещественных чисел? Ведь они нам нужны были, к примеру, для функций, например, $f(x) = lnx$. Но ведь в нашем счётном множестве чисел будут все точки подобных функций.

Проблема звучит примерно так: если у нас существует описуемая функция, область определения которой состоит из описуемых чисел, а область значений - из неописуемых, то значит нам нужно несчётное множество чисел.
Если же такой функции не существует, то мы можем выкинуть неописуемые объекты из нашей формальной системы, и она останется закрытой относительно любой операции (думаю можно сказать "воздействия одного описуемого объекта на другой").

Конечно хочется сказать что:
"У нас есть описуемая функция, принимающая описуемый аргумент, и возвращающая некое значение. Значит описанием данного значения и будет являться описание функции и описание её аргумента". Но я не уверен что тут нет ошибок в рассуждениях. Если бы удалось доказать, что любая формальная система закрыта относительно описуемых объектов, то это было бы весьма круто - можно было бы избавится от любых множеств мощности алеф_1 и выше.

[mihaild]

Тут нужно уточнять, что в точности понимается под "описанием" вещественного числа, функции и т.д. И окажется, что при любом разумном определении "описания" множество описуемых чисел само неописуемо, потому что к любому разумному определению описания применим диагональный метод. Является ли текст "двоичная последовательность, $n$-й символ которой противоположен $n$-му симмволу двоичный последовательности с описанием номер $n$" описанием?

[Lesaje]

mihaild в сообщении #1546980 писал(а):

Тут нужно уточнять, что в точности понимается под "описанием" вещественного числа, функции и т.д. И окажется, что при любом разумном определении "описания" множество описуемых чисел само неописуемо, потому что к любому разумному определению описания применим диагональный метод. Является ли текст "двоичная последовательность, $n$-й символ которой противоположен $n$-му симмволу двоичный последовательности с описанием номер $n$" описанием?

Как диагональный метод может быть применён к последовательностям конечной длины?

[Anton_Peplov]

Математикам нужны не только конкретные функции, но и общие теоремы. Всякая фундаментальная последовательность имеет предел. Всякая дифференцируемая функция непрерывна. Всякая непрерывная на сегменте функция достигает на этом сегменте своих точных граней. И т.д. и т.п. Как Вы планируете доказывать подобные теоремы на множестве "описуемых" чисел?

[mihaild]

Lesaje в сообщении #1546981 писал(а):

Как диагональный метод может быть применён к последовательностям конечной длины?

Я же привел пример, и вы его процитировали. В любом случае, первый вопрос в таких разговорах - что в точности понимается под описанием.

[Lesaje]

mihaild в сообщении #1546983 писал(а):

Lesaje в сообщении #1546981 писал(а):

В любом случае, первый вопрос в таких разговорах - что в точности понимается под описанием.

Ок, если ограничится лишь языками программирования, то описанием может являтся программы машины Тьюринга. В области вычислимого анализа, я слышал, существуют интегралы, и вообще в целом математика с такими ограничениями не мертва. При этом, множество вычислимых чисел весьма сильно ограничено.
Про диагональный метод я Вас не до конца понимаю. В моём представлении рассуждения звучат так: у нас есть множество последовательностей символов БЕСКОНЕЧНОЙ длины. Предположим что все последовательности пронумерованы. Тогда возьмём первый символ первой последовательности, второй символ второй и т.д., получим последовательность, отличающуюся от любой из имеющихся. Следовательно, они не пронумерованы.
Если у нас последовательности символов ограничены, то как мы не меняем символы, получая новые последовательности, они будут уже пронумерованы.

Anton_Peplov в сообщении #1546982 писал(а):

Как Вы планируете доказывать подобные теоремы на множестве "описуемых" чисел?

При добавлении любых чисел, которые можно описать, ну например, строгим аксиоматическим языком (аксиоматику выбрать можно любую), разве не будет полученного множества достаточно для любых доказательств? Бурбаки вроде могли в определённой аксиоматике описывать пустое множество, числа и так далее.

[mihaild]

Lesaje в сообщении #1546984 писал(а):

Ок, если ограничится лишь языками программирования, то описанием может являтся программы машины Тьюринга.

Хорошо, это стандартный подход. Есть некоторые проблемы, вроде того, как именно МТ должна задавать вещественное число, их можно решать разными способами. В любом случае, проблема будет с тем, что мы не сможем пронумеровать все МТ, задающие вещественные числа. И вообще, из возможности задать пронумеровать множество не будет следовать пронумеровать его даже "разумное" подмножество.

Lesaje в сообщении #1546984 писал(а):

Про диагональный метод я Вас не до конца понимаю.

Диагональный метод в данном случае показывает, что нельзя никак описать список, включающий все описуемые последовательности.

[Mikhail_K]

Lesaje
Короче говоря: если Вы попробуете составить список программ, задающих то или иное число, выписывая просто по порядку всевозможные синтаксически корректные программы, у Вас будет проблема узнать, не "зависает" ли та или иная синтаксически корректная программа, не появляется ли в ней бесконечный цикл, условие выхода из которого никогда не будет выполнено.
А если Вы хотите построить список чисел без повторений - то ещё будет проблема установить, задают ли две разные программы одно и то же число или нет.

[EminentVictorians]

Anton_Peplov в сообщении #1546982 писал(а):

Математикам нужны не только конкретные функции, но и общие теоремы.

Вот кстати очень интересный тезис, давайте обсудим!

Для практики рациональных чисел за глаза, я думаю, с этим никто спорить не будет. Роль вещественных чисел исключительно теоретическая! Забавно, что обычно так говорят о комплексных числах, не замечая, что эта исключительно теоретическая роль появляется на ступеньку ниже. Удивительно, почему об этом не говорится прямым текстом в учебниках по матанализу.

Я как-то пытался размышлять на тему комплексного анализа и причин его успеха. Anton_Peplov, по этому поводу у меня к Вам большая личная благодарность! У Вас был пост про то, что комплексные функции "правильно ограничены в возможностях" (пересказываю от себя, так что извините, если не те слова подберу). Условно говоря, ограничения - это хорошо, потому что они сужают пространство для хаотичного поведения функции. А если нет хаотичного поведения, значит есть шанс создать хорошую теорию вокруг таких функций. Мне эта мысль очень сильно отрезонировала. Интересно то, что ее можно продолжать и дальше, в вещественный анализ. Там же все то же самое: он хорош из-за правильных ограничений на функции: непрерывность, дифференцируемость и т.д. Иными словами, у этих теорий очень большое произведение, первый множитель которого - это "степень ограниченности", а второй - "количество оставшихся после этого функций". Т.е. мы очень сильно ограничиваем теоретические возможности для поведения функций (и получаем благодаря этому нормальную теорию), но при этом особо не теряем никаких функций, которые нам нужны для практики.

[Anton_Peplov]

Более точно эта мысль выражается так. Требование непрерывности или дифференцируемости накладывает на функцию комплексного переменного куда более жёсткие ограничения, чем на функцию действительного переменного. Это видно уже по определению предела по Гейне. В вещественном случае последовательность аргументов можно выбрать только на одной-единственной числовой прямой. А в комплексном - на плоскости; эта последовательность может лечь на любую прямую, или на кривую, или вообще на какое-то странное множество. Требование, чтобы для любой последовательности аргументов последовательность значений сходилась к одной и той же точке, становится очень обременительным. Но зато уж если функция дифференцируема на открытом множестве, то она бесконечно дифференцируема и совпадает с суммой ряда Тейлора. Без этих вещественных уродств: "А может, не все производные есть... А может, они все есть, но ряд Тейлора расходится... А может, он сходится, но НЕ ТУДА!" То есть, поскольку среди комплексных функций большинство очень дикие, у них такой фейс-контроль на входе в клуб дифференцируемых, что его проходят только самые паиньки. Которых, между тем, достаточно много для любых приложений.

Наблюдается ли нечто подобное при переходе от рациональных функций к вещественным? Ну, у множества рациональных чисел даже топологические свойства очень уродливые (взгляните только, что там происходит со связностью).
Да, вполне допускаю, что если пытаться ограничиться только рациональными числами, мы получим такие контрпримеры к тому, что раньше было теоремами, что пляски вокруг ряда Тейлора покажутся нам детским утренником. Более обоснованно ответить не могу, т.к. с преступником Фунтиком, а равно с попытками построения рационального анализа, я не знаком.

Правда, ТС согласен на иррациональные вычислимые числа. За весь анализ не скажу, но при попытке скрестить вычислимость с теорией меры (все эти эффективно измеримые множества по Мартин-Лефу и не только по нему) происходят весьма контринтуитивные вещи. В классической теории фортеля выкидывают только неизмеримые множества; потребовав измеримости, мы гарантируем приличное поведение без этих ваших шаров Банаха-Тарского. А тут и измеримые финтят. В общем, вычислимые меры по-своему интересны, но я бы не пытался строить на них, скажем, математический аппарат физики.

[xagiwo]

(Оффтоп)

Anton_Peplov в сообщении #1547009 писал(а):

За весь анализ не скажу, но при попытке скрестить вычислимость с теорией меры (все эти эффективно измеримые множества по Мартин-Лефу и не только по нему) происходят весьма контринтуитивные вещи

Звучит интересно. Где об этом можно почитать?

(Оффтоп)

Anton_Peplov в сообщении #1547009 писал(а):

В классической теории фортеля выкидывают только неизмеримые множества

Я в первый момент даже заинтересовался, что это за "теория фортеля" и что случится с математикой, если из неё выкинуть неизмеримые множества

[worm2]

Это же конструктивная математика получается. Давно развивается, но имеет проблемы (Anton_Peplov уже указал на некоторые).

[EminentVictorians]

Anton_Peplov в сообщении #1547009 писал(а):

Да, вполне допускаю, что если пытаться ограничиться только рациональными числами, мы получим такие контрпримеры к тому, что раньше было теоремами, что пляски вокруг ряда Тейлора покажутся нам детским утренником.

Я давно не открывал учебник по анализу, но навскидку мне кажется, что в главах про непрерывность и дифференцируемость не сохранится ни одна значимая теорема. В интегрировании может что-то немного сохранится (типа линейности определенного интеграла), но пациент к этому моменту уже будет все.. Там все теоремы идут в плотной связке друг с другом, одно невыполнение теоремы Больцано-Коши ломает половину всего.

Интересно вот что. Тот тезис о непредсказуемости функций, определенных на $\mathbb{Q}$ по всей видимости может быть применим к любому подполю $\mathbb{R}$, отличному от него самого. Ключевое свойство здесь - полнота. Если ее нет, значит нет и теории анализа.

[Anton_Peplov]

xagiwo в сообщении #1547021 писал(а):

Звучит интересно. Где об этом можно почитать?

Верещагин, Успенский, Шень. Колмогоровская сложность и алгоритмическая случайность.

[WaRLoC]

Тема интересная, я задумывался ранее в схожем направлении. Пришел к выводу что мы не можем пользоваться никакими конкретными вещественными числами которые не входят в счетное множество всех аналитических чисел. Просто потому что не можем их описать, мы можем задать интервал между которыми есть континуальное подмножество, в том числе не аналитических (надеюсь правильно называю, уже не помню точно, может алгебраических :)). Но это опять описание только аналитических и некоего условия. Далее между любыми двумя описанными аналитическими цифрами, насколько я понимаю, существует бесконечное счетное подмножество тех же аналитических цифр, тупо дели интервал пополам бесконечное количество раз например. И тогда я еще задумался - а что делать с неаналитическими цифрами, по факту они просто бессмысленны. Все теоремы о гладкости, непрерывности или дифференцируемости проверяются подстановкой только в аналитических числах. Единственное до чего я додумался это о бесконечно малом приращении о(), поначалу думал про дифференциал в первоначальном смысле как его сформулировали, но он перешел в разряд операторов. В принципе бесконечно малое приращение первоначальный смысл дифференциала повторяет, но отвлекся. Итого можно определить бесконечно малое приращение как интервал между двумя ближайшими аналитическими числами между которыми нет других аналитических чисел, но континуальное (а может и нет) количество неаналитических чисел.
Что это дает не знаю, так, забавные рассуждения). Возможно придумал велосипед, компетенция в математике у меня так себе, любительская))