Существует ли биекция между вычислимыми числами и нат.?

[маткиб]

nikov писал(а):

А дает ли ZFC какие-то применимые в технике (физике, химии, любых прикладных науках) результаты, которые нельзя получить в арифметике второго порядка?

В арифметике второго порядка даже не сформулировать утверждения о функциях $\mathbb{R}\rightarrow\mathbb{R}$, поэтому весь анализ сразу выпадает (а уж функциональный тем более).

Даже если для "прикладных вопросов" анализ принципиально и можно обойти, удобства, которые он дает, нельзя недооценивать.

[nikov]

epros писал(а):

nikov писал(а):

Суть в том, что добавляемая аксиома должна обладать тем же уровнем интуитивной истинности, как и расширяемая теория - как например, схема аксиом, утверждающая состоятельность аксиоматики Пеано.

Я не очень понимаю, что такое "уровень интуитивной истинности". Что касается утверждения о состоятельности арифметики Пеано, то оно, конечно, достаточно убедительно, но, по-моему всё же в меньшей степени, чем сама арифметика. Я уже писал почему: потому что возможна ситуация, когда теория непротиворечива, но расширение её утверждением о её состоятельности противоречиво.

Если теория $T$ непротиворечива, но ее расширение с помощью схемы аксиом, утверждающей ее состоятельность - противоречиво, значит теория $T$ несостоятельна. Так?
Мое мнение, что несостоятельная теория не лучше противоречивой - ее результататам так же нельзя доверять. Я бы даже сказал, что противоречивая теория в некотором смысле лучше, так как ее дефектность более явная и может быть обнаружена легче, путем обнаружения противоречия, после чего мы можем ее отбросить (или скорректировать).
Поэтому, расширив теорию, мы не сделаем ее хуже.

[маткиб]

А ещё возникает соблазн к таким важным прикладным проблемам, как, например, P?=NP - проблема, применить какие-нибудь крутые аксиомы бесконечности, типа существования кардинала Mahlo (и не факт, что для решения этой проблемы хватит ZFC, и уж тем более арифметики второго порядка, хотя сформулировать её можно и на языке обычной арифметики первого порядка).

[nikov]

маткиб писал(а):

nikov писал(а):

А дает ли ZFC какие-то применимые в технике (физике, химии, любых прикладных науках) результаты, которые нельзя получить в арифметике второго порядка?

В арифметике второго порядка даже не сформулировать утверждения о функциях $\mathbb{R}\rightarrow\mathbb{R}$, поэтому весь анализ сразу выпадает (а уж функциональный тем более).

На самом деле можно сформулировать утверждения о непрерывных и кусочно-непрерывных функциях, так как они определяются своими значениями в рациональных точках (Coding mathematics in second-order arithmetic). Есть подозрение, что этого достаточно для физики.

[маткиб]

nikov в сообщении #182024 писал(а):

На самом деле можно сформулировать утверждения о непрерывных и кусочно-непрерывных функциях, так как они определяются своими значениями в рациональных точках (Coding mathematics in second-order arithmetic). Есть подозрение, что этого достаточно для физики.

Ну можно вообще все функции приближать дискретными (с очень маленьким шагом), тогда и первого порядка будет достаточно, но это ужасно неудобно. Математические физики, например, очень любят рассматривать интегрируемые по Лебегу функции (которых гиперконтинуум), даже интегрируемости по Риману им недостаточно, и уж тем более кусочной непрерывности.

[nikov]

маткиб писал(а):

А ещё возникает соблазн к таким важным прикладным проблемам, как, например, P?=NP - проблема, применить какие-нибудь крутые аксиомы бесконечности, типа существования кардинала Mahlo

Интересно, а за ее решение с привлечением дополнительных аксиом миллион дадут?

[маткиб]

nikov в сообщении #182028 писал(а):

Интересно, а за ее решение с привлечением дополнительных аксиом миллион дадут?

Я думаю, что если решение будет положительным и даст конкрентый быстрый алгоритм, который решает NP-полную задачу, то обязательно дадут (а потом догонят и ещё раз дадут)

[epros]

nikov писал(а):

Вы можете предложить что-то другое? Нечто, что могло бы дать достаточный уровень убедительности?

Это то, чему нет разумной альтернативы, как ни ищи. Если к строке вертикальных чёрточек добавить вертикальную чёрточку, то можно, конечно, предположить, что получится нечто, не являющееся строкой вертикальных чёрточек. Но как-то в это не верится. Можете, конечно, называть это "интуицией" или "здравым смыслом", но, по-моему, это просто отсутствие альтернативы (даже воображаемой).

nikov писал(а):

Если теория $T$ непротиворечива, но ее расширение с помощью схемы аксиом, утверждающей ее состоятельность - противоречиво, значит теория $T$ несостоятельна. Так?

Нет. Причём тут несостоятельность? Я же сказал, что состоятельность - это не какое-то "проверяемое" свойство теории, а характеристика, которую мы ей произвольно приписали. Просто потому, что эта теория нам "понравилась" и мы её "приняли".

Как я понимаю, если теория непротиворечива, но ее расширение с помощью схемы аксиом, утверждающей ее состоятельность - противоречиво, значит теория омега-противоречива.

nikov писал(а):

Мое мнение, что несостоятельная теория не лучше противоречивой - ее результататам так же нельзя доверять.

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

[nikov]

epros писал(а):

nikov писал(а):

Вы можете предложить что-то другое? Нечто, что могло бы дать достаточный уровень убедительности?

Это то, чему нет разумной альтернативы, как ни ищи. Если к строке вертикальных чёрточек добавить вертикальную чёрточку, то можно, конечно, предположить, что получится нечто, не являющееся строкой вертикальных чёрточек. Но как-то в это не верится. Можете, конечно, называть это "интуицией" или "здравым смыслом", но, по-моему, это просто отсутствие альтернативы (даже воображаемой).

Ну вот, верится - не верится. От этого никуда не уйти. Откуда, например, математик, который читает математический текст, знает что он правильно понимает смысл всех значков (в том числе слов русского языка) в тексте? Откуда он знает, что не спутал один значок с другим? Откуда он знает, что к концу формулы он правильно помнит, как она начиналась? Он опирается на опыт, интуицию и здравый смысл.

Вспоминается мне одна история. Один мой знакомый, умный человек, но далекий от математики, спросил меня:
- А есть ли самое большое натуральное число?
- Ну, нет конечно же. Подумай, ведь всегда можно еще единичку прибавить и получится число еще больше.
- А, ну да, конечно. (потом после некоторого размышления) Слушай, а вдруг число будет настолько большое, что эта единичка к нему уже прилипать не будет?
- Не переживай, прилипнет.
- (еще размышляет) А вдруг эти сами единички, которые мы прилепляем, кончатся?
-
Так что для пытливого ума всегда есть место для сомнений.

epros писал(а):

nikov писал(а):

Если теория $T$ непротиворечива, но ее расширение с помощью схемы аксиом, утверждающей ее состоятельность - противоречиво, значит теория $T$ несостоятельна. Так?

Нет. Причём тут несостоятельность? Я же сказал, что состоятельность - это не какое-то "проверяемое" свойство теории, а характеристика, которую мы ей произвольно приписали. Просто потому, что эта теория нам "понравилась" и мы её "приняли".

Под несостоятельностью я имел в виду, что для некоторого высказывания $\Phi$, $\neg ((T \vdash \Phi) \rightarrow \Phi)$.

[Nxx]

nikov, вот вам пример: константа Чайнтина. Известны первые цифры ее разложения:

0.00787499699...

но в то же время, известно, что вычислить ее с любой наперед заданной точностью невозможно, это невычислимое число
http://mathworld.wolfram.com/ChaitinsConstant.html

По поводу вашего предложения заменять неразрешимые вопросы аксиомами, могу сказать вот что: неразрешимая проблема - это не та проблема, у которой нет решения, это там проблема, для которой не существует алгоритма решения. Само решение существует в уже имеющейся системе аксиом. Поэтому если вы постулируете какое-то решение, вы рискуете сделать систему аксиом противоречивой.

[epros]

nikov писал(а):

Ну вот, верится - не верится. От этого никуда не уйти.
...
Так что для пытливого ума всегда есть место для сомнений.

Видите ли, я не отрицаю интуицию и здравый смысл. Просто я считаю, что их не нужно включать в рамки математики. У математики где-то есть граница, за которой лежат неформализованные представления, и чтобы избежать неоднозначностей в самой математике, лучше всего постараться эту границу достаточно чётко обозначить. Причём проводить её следует в таком месте, которое не вызовет сомнений ни у кого, включая людей, от математики весьма далёких.

Когда продвинутый математик говорит, что ему "инуитивно очевидна" аксиома выбора, то это чувство с ним не всегда готовы разделить не то чтобы простые люди, а даже и многие другие продвинутые математики. Когда же Вам говорят, что если составить подряд две строки, то тоже получится строка, то с таким уровнем очевидности трудно спорить.

Относительно "пытливого ума", готового усомниться в том, что мы всегда можем добавить единичку к числу: На этот случай конструктивисты упоминают т.н. "абстракцию потенциальной реализуемости" (или "осуществимости"). Т.е. мы изначально договариваемся о том, что мы "как бы" не ограничены в ресурсах. Это значит, что случаи, когда мы не можем реализовать построение (скажем, добавить единичку) по той причине, что сталкиваемся с ограничением ресурсов, заранее исключаются из рассмотрения.

nikov писал(а):

Откуда, например, математик, который читает математический текст, знает что он правильно понимает смысл всех значков (в том числе слов русского языка) в тексте? Откуда он знает, что не спутал один значок с другим? Откуда он знает, что к концу формулы он правильно помнит, как она начиналась?

А на этот случай у конструктивистов есть другая договорённость: "абстракция различимости" (или "отождествления"). Она говорит о том, что строки символов могут быть всегда записаны таким образом, что могут быть однозначно различены (или отождествлены). Случаи, когда это не так, опять же, заранее исключаются из рассмотрения.

См. здесь.

nikov писал(а):

Под несостоятельностью я имел в виду, что для некоторого высказывания $\Phi$, $\neg ((T \vdash \Phi) \rightarrow \Phi)$.

Да, я тоже. Но это не имеет отношения к противоречивости теории (т.е. к её способности доказывать противоположные утверждения). Чтобы теория была признана несостоятельной, нам достаточно отвергнуть хотя бы одно доказанное ей утверждение. А это - вопрос нашего собственного решения и ничего более.

[маткиб]

Математика - наука для избранных

[AD]

Внимание! Следующее сообщение является оффтопиком, и его можно не читать. Я предупредил
_________________

Nxx в сообщении #181245 писал(а):

Но ведь множество возможных последовательностей рациональных чисел счетно! Значит, и множество вещественных чисел счетно?

Nxx в сообщении #182133 писал(а):

nikov, вот вам пример: константа Чайнтина. Известны первые цифры ее разложения:

0.00787499699...

но в то же время, известно, что вычислить ее с любой наперед заданной точностью невозможно, это невычислимое число
http://mathworld.wolfram.com/ChaitinsConstant.html

Ну не верю я, что это один и тот же человек писал с промежутком в несколько дней. Видимо, прав Brukvalub про троллинг.

[Nxx]

Цитата:

Ну не верю я, что это один и тот же человек писал с промежутком в несколько дней.

Я просто излагаю классическую теорию.

На мой взгляд, омеги просто нет.

И вообще, основная ветвь математики должна отражать только то, что можно потенциально вычислить имеющимися техническими средствами.

Хотя это не отрицает возможности "поиграть" с аксиомами, представить, что у нас есть гиперкомпьютер и т.д.

[gris]

Nxx писал(а):

... можно потенциально вычислить имеющимися техническими средствами.

Потенциальная невычислимость это всё же не принципиальная невычислимость. Технические средства развиваются сейчас быстро. Без существенного опережения математика может и не успеть за компьютерами.