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

[ewert]

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

Потому что невычислимо вычислить нельзя.

Это неверная логика. Ничего вообще в этом мире до конца вычислить нельзя. Всё, что реально требуется -- это найти интересующий объект с гарантированной степенью точности. А сам объект задаётся вовсе не какими-то там конструктивными построениями, но своими свойствами, наблюдаемыми на практике. Т.е. с сугубо математической точки зрения, попросту говоря -- аксиомами.

[nikov]

nikov писал(а):

Nxx писал(а):

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

Вы можете привести пример хотя бы одного алгоритма, для которого невозможно определить, остановится он или нет?

Хочу обратить внимание, что из отрицания существования доказательства, что некоторый алгоритм A останавливается, следует, что алгоритм A не останавливается.

Потому что если бы он останавливался, то можно было бы выписать все его шаги вплоть до остановки, и это было бы доказательством того, что он останавливается.

[epros]

nikov писал(а):

Nxx писал(а):

Алгоритм, завязанный на какую-нибудь неразрешимую проблему в математике. Например, подбор решений диофантового уравнения.

Что значит "завязанный на"? Приведите конкретный пример алгоритма, для которого невозможно определить, остановится он или нет.

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

nikov писал(а):

Если мы считаем аксиоматику Пеано содержательно истинной, то очевидно, что добавление схемы аксиом "каждое утверждение, доказуемое в аксиоматике Пеано - истинно" даст по прежнему содержательно истинную, а значит, непротиворечивую теорию.
Или Вам нужно еще какое-то свидетельство непротиворечивости?

Я не могу понять одного: С какой стати добавление этот схемы аксиом является "свидетельством" чего-либо, в частности - непротиворечивости?

nikov писал(а):

Я не нашел там ни одного утверждения, про которое доказано, что его истинность никогда не будет ни доказана, ни опровергнута.

Про гипотезу континуума доказано, что она "никогда не будет ни доказана, ни опровергнута" в ZFC. Если Вас это не устраивает и Вы хотите говорить о доказуемости не в рамках конкретной аксиоматики, а "вообще", то я просто не понимаю о чём идёт речь: что это за "вообще"?

ewert писал(а):

Это неверная логика. Ничего вообще в этом мире до конца вычислить нельзя.

Вопрос в том, как Вы определяете "конец". Если "концом" считать получение строки, которая однозначно представляет собой данный объект, то кое-что можно "вычислить до конца". Например, задача "вычисления 7-ого простого числа" может быть решена "до конца": Этим "концом" будет строка "17".

[MaximKat]

epros
"нерешенная"$\neq$"неразрешимая

[ewert]

epros в сообщении #181911 писал(а):

Вопрос в том, как Вы определяете "конец". Если "концом" считать получение строки, которая однозначно представляет собой данный объект, то кое-что можно "вычислить до конца". Например, задача "вычисления 7-ого простого числа" может быть решена "до конца": Этим "концом" будет строка "17".

Угу, и ещё вот дважды два тоже можно (маленько поднапрягшись) сосчитать до конца.

А вот почти любая задача анализа за конечное время численно неразрешима. С другой стороны -- и нет необходимости считать её "до конца". Достаточно предложить модель, в рамках которой решение гарантированно а) корректно и б) может быть определено с любой точностью. И здесь вполне достаточно аксиоматического подхода, конструктивизм не нужен.

[nikov]

epros писал(а):

nikov писал(а):

Nxx писал(а):

Алгоритм, завязанный на какую-нибудь неразрешимую проблему в математике. Например, подбор решений диофантового уравнения.

Что значит "завязанный на"? Приведите конкретный пример алгоритма, для которого невозможно определить, остановится он или нет.

nikov, мне непонятно, что Вы имеете против?

Я не понял, что значит "завязанный на".

epros писал(а):

Вы отрицаете факт существования нерешённых математических проблем?

Нет, но я не уверен, что есть принципиально неразрешимые проблемы.

epros писал(а):

Nxx привёл пример диофантового уравнения,

Я так и не увидел, о каком именно диофантовом уравнении идет речь. Было заявлено, что есть алгоритмы, для которых невозможно определить, остановятся они или нет. Мне было бы интересно взглянуть на такой алгоритм.

epros писал(а):

а я могу Вам привести мой любимый пример нечётного совершенного числа: Берёте алгоритм, который перебирает подряд все натуральные числа и останавливается, как только обнаружит нечётное совершенное число. Имеет этот алгоритм точку останова? Никто не знает.

Но ведь это не значит, что никто никогда этого не узнает?

epros писал(а):

nikov писал(а):

Если мы считаем аксиоматику Пеано содержательно истинной, то очевидно, что добавление схемы аксиом "каждое утверждение, доказуемое в аксиоматике Пеано - истинно" даст по прежнему содержательно истинную, а значит, непротиворечивую теорию.
Или Вам нужно еще какое-то свидетельство непротиворечивости?

Я не могу понять одного: С какой стати добавление этот схемы аксиом является "свидетельством" чего-либо, в частности - непротиворечивости?

Потому что
1) эта схема аксиом является выражением наших интуитивных представлений о предметной области
2) непротиворечивость исходной теории становится доказуемой в новой расширенной теории

epros писал(а):

nikov писал(а):

Я не нашел там ни одного утверждения, про которое доказано, что его истинность никогда не будет ни доказана, ни опровергнута.

Про гипотезу континуума доказано, что она "никогда не будет ни доказана, ни опровергнута" в ZFC. Если Вас это не устраивает и Вы хотите говорить о доказуемости не в рамках конкретной аксиоматики, а "вообще", то я просто не понимаю о чём идёт речь: что это за "вообще"?

На самом деле утверждение "ни континуум-гипотеза, ни ее отрицание не доказуемы в ZFC" не доказано в ZFC. Оно доказано в теории ZFC + "ZFC непротиворечива".
В общем-то, из Вашего же утверждения о доказанности видно, что доверие к этой расширенной теории у Вас не меньше, чем к ZFC. Но доказуема ли континуум-гипотеза или ее отрицание в этой расширенной теории? Мы пока не знаем. Вот я и предлагаю расширять теорию интуитивно верными аксиомами в надежде, что мы рано или поздно получим доказательства или опровержения интересующих нас гипотез. Я например, представляю, как неограниченно строить все новые и новые аксиомы, сохраняя их интуитивную истинность.

[juna]

Вставлю свои пять копеек

Профессор Снейп писал(а):

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

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

ewert писал(а):

Это неверная логика. Ничего вообще в этом мире до конца вычислить нельзя. Всё, что реально требуется -- это найти интересующий объект с гарантированной степенью точности. А сам объект задаётся вовсе не какими-то там конструктивными построениями, но своими свойствами, наблюдаемыми на практике. Т.е. с сугубо математической точки зрения, попросту говоря -- аксиомами.

Вот и дайте определение - что значит наблюдать?

[nikov]

epros писал(а):

nikov писал(а):

Если мы считаем аксиоматику Пеано содержательно истинной, то очевидно, что добавление схемы аксиом "каждое утверждение, доказуемое в аксиоматике Пеано - истинно" даст по прежнему содержательно истинную, а значит, непротиворечивую теорию.
Или Вам нужно еще какое-то свидетельство непротиворечивости?

Я не могу понять одного: С какой стати добавление этот схемы аксиом является "свидетельством" чего-либо, в частности - непротиворечивости?

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

[epros]

MaximKat писал(а):

epros
"нерешенная"$\neq$"неразрешимая

Я знаю.

ewert писал(а):

А вот почти любая задача анализа за конечное время численно неразрешима.

Задачи конструктивного анализа, которые решены, - разрешимы.

ewert писал(а):

С другой стороны -- и нет необходимости считать её "до конца".

Правильно. То, что у числа пи есть $10^{10^{10}}$-тая цифра в десятичной записи, не нужно демонстрировать непосредственным расчётом. Для этого есть конструктивное доказательство, которое означает, что если бы мы не были ограничены в ресурсах, то могли бы продемонстрировать это непосредственным расчётом.

ewert писал(а):

И здесь вполне достаточно аксиоматического подхода, конструктивизм не нужен.

Конструктивизм не противоречит аксиоматическому подходу. Он просто требует, чтобы прежде, чем принять аксиому, мы её проверили на соответствующем типе конструктивных объектов. А иначе на все вопросы можно получить любые желательные нам ответы, достаточно только подобрать соответствующие аксиомы. Наример, зачем мучиться вопросом, существует ли нечётное совершенное число? Примем это в качестве аксиомы и успокоимся (до тех пор, пока не получим противоречия).

nikov писал(а):

Нет, но я не уверен, что есть принципиально неразрешимые проблемы.

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

nikov писал(а):

Но ведь это не значит, что никто никогда этого не узнает?

Не значит, но это не исключено.

nikov писал(а):

Потому что
1) эта схема аксиом является выражением наших интуитивных представлений о предметной области
2) непротиворечивость исходной теории становится доказуемой в новой расширенной теории

1) Эта схема аксиом всего лишь эквивалентна мета-теоретическому утверждению о состоятельности теории: "Теория доказывает только истинные утверждения". А это ни о чём не свидетельствует, кроме нашей ни на чём не основанной вере в теорию.
2) В противоречивой мета-теории будет доказуемо любое утверждение. В том числе - утверждение о непротиворечивости любой теории.

nikov писал(а):

На самом деле утверждение "ни континуум-гипотеза, ни ее отрицание не доказуемы в ZFC" не доказано в ZFC. Оно доказано в теории ZFC + "ZFC непротиворечива".

ОК, поправку принимаю.

nikov писал(а):

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

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

nikov писал(а):

добавление в явном виде схемы аксиом $(T \vdash \Phi) \to \Phi$ теории ничуть не повредит, и более того, сделает ее сильнее

"Сильнее" (в смысле - "содержательнее") - не значит "лучше" или "достовернее". Наоборот, такая теория может оказаться противоречивой, не смотря на непротиворечивость исходной теории.

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

[nikov]

epros писал(а):

nikov писал(а):

Нет, но я не уверен, что есть принципиально неразрешимые проблемы.

Я тоже не уверен, но это не исключено.

nikov писал(а):

Но ведь это не значит, что никто никогда этого не узнает?

Не значит, но это не исключено.

А я и не утверждал, что это исключено. Но у меня есть оптимистичная надежда, что любую интересную гипотезу можно будет доказать или опровергнуть исходя из интуитивно истинных аксиом.

epros писал(а):

nikov писал(а):

Потому что
1) эта схема аксиом является выражением наших интуитивных представлений о предметной области
2) непротиворечивость исходной теории становится доказуемой в новой расширенной теории

1) Эта схема аксиом всего лишь эквивалентна мета-теоретическому утверждению о состоятельности теории: "Теория доказывает только истинные утверждения". А это ни о чём не свидетельствует, кроме нашей ни на чём не основанной вере в теорию.

Почему же ни на чём? Убеждение в правдивости, состоятельности (soundness) теории может быть основано на опыте, интуиции и здравом смысле. К сожалению, я не знаю каких-либо более надежных источников.
Благодаря тому, что эта схема аксиом "всего лишь" эквивалентна утвержданию о состоятельности теории, она усиливает ее доказательные способности, не вводя никаких существенно новых предположений.

epros писал(а):

2) В противоречивой мета-теории будет доказуемо любое утверждение. В том числе - утверждение о непротиворечивости любой теории.

По мне, несостоятельная теория не лучше противоречивой. Она тоже доказывает ложные утверждения. А шансы у расширенной теории оказаться противоречивой такие же, как у исходной - оказаться несостоятельной. Или у Вас есть волшебный способ, который может гарантировать состоятельность теории?

epros писал(а):

nikov писал(а):

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

Так можно очень далеко зайти. Вопрос в том, что Вы полагаете "интуитивно верным". Например, для меня уже аксиоматика ZFC далеко не является "интуитивно верной".

Да, мне аксиоматика ZFC тоже не кажется интуитивно верной. Например, для меня совершенно не очевидна справедливость аксиомы о существовании множества всех подмножеств, когда она применяется к бесконечным множествам. Гораздо более очевидна справедливость аксиоматики Пеано. Давайте ее расширять. Или арифметику второго порядка.

epros писал(а):

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

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

[ewert]

epros в сообщении #181963 писал(а):

Для этого есть конструктивное доказательство, которое означает, что если бы мы не были ограничены в ресурсах, то могли бы продемонстрировать это непосредственным расчётом.

Ну вот пример. Берём задачу Коши для дифуравнения 1-го порядка $y'=f(x,y)$ со всего лишь непрерывной правой частью. Она разрешима. Однако разрешимость доказывается ссылкой на соображения компактности, т.е. неконструктивно. Значит ли это, утверждение о разрешимости не имеет смысла?

[epros]

nikov писал(а):

Убеждение в правдивости, состоятельности (soundness) теории может быть основано на опыте, интуиции и здравом смысле. К сожалению, я не знаю каких-либо более надежных источников.

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

nikov писал(а):

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

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

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

nikov писал(а):

По мне, несостоятельная теория не лучше противоречивой. Она тоже доказывает ложные утверждения. А шансы у расширенной теории оказаться противоречивой такие же, как у исходной - оказаться несостоятельной. Или у Вас есть волшебный способ, который может гарантировать состоятельность теории?

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

nikov писал(а):

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

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

ewert, я пока не готов ответить на Ваш вопрос. Для этого нужно поискать конструктивное доказательство существования решения задачи Коши.

[nikov]

epros писал(а):

nikov писал(а):

Убеждение в правдивости, состоятельности (soundness) теории может быть основано на опыте, интуиции и здравом смысле. К сожалению, я не знаю каких-либо более надежных источников.

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

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

[маткиб]

Пока конструктивисты тормозят и ищут основания, которые бы их окончательно убедили, мы (нормальные математики) будем пользоваться ZFC, разными аксиомами существования недостижимых кардиналов и т.п., наполучаем новых результатов, на их основе построим более совершенную технику и будем осваивать космос.

Так что вступайте в нашу секту

[nikov]

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

Пока конструктивисты тормозят и ищут основания, которые бы их окончательно убедили, мы (нормальные математики) будем пользоваться ZFC, разными аксиомами существования недостижимых кардиналов и т.п., наполучаем новых результатов, на их основе построим более совершенную технику и будем осваивать космос.

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