Неполнота у Пресбургера

[knizhnik]

Я понял. Сам у себя нашел ошибку. Тема больше не нужна.

[kotenok gav]

Может скажете условие задачи? И где у вас ошибка?

[knizhnik]

nazarov_m в сообщении #1166871 писал(а):

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

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

[Xaositect]

knizhnik в сообщении #1169615 писал(а):

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

Нестандартные модели существуют, но в них истинны одни и те же утверждения арифметики Пресбургера.

[knizhnik]

Xaositect в сообщении #1169641 писал(а):

Нестандартные модели существуют, но в них истинны одни и те же утверждения арифметики Пресбургера.

А почему появляется разница в арифметике Пеано? Подскажите, как написать какое-нибудь суждение в языке Пеано, которое относится к нестандартным числам. Как я понял, его будет нельзя ни доказать, ни опровергнуть. Что это должно быть? Что-то связанное с умножением натуральных чисел?

[Someone]

knizhnik в сообщении #1169808 писал(а):

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

А нету в арифметике Пеано никаких утверждений, "относящихся к нестандартным числам". Арифметика Пеано вообще не имеет никаких средств отличить стандартные числа от нестандартных. Они все удовлетворяют одному и тому же набору аксиом.

Но утверждения, которые в арифметике Пеано нельзя ни доказать, ни опровергнуть, известны. Например, теорема Гудстейна (лучше на английском языке).

[knizhnik]

Someone в сообщении #1169823 писал(а):

А нету в арифметике Пеано никаких утверждений, "относящихся к нестандартным числам". Арифметика Пеано вообще не имеет никаких средств отличить стандартные числа от нестандартных.

В языке арифметики Пеано.

Someone в сообщении #1169823 писал(а):

Они все удовлетворяют одному и тому же набору аксиом.

Надо добавить новое утверждение, которое не является аксиомой и не доказывается через них. Но какое именно добавить? Как оно выглядит?

[Mikhail_K]

--

[Xaositect]

knizhnik в сообщении #1169826 писал(а):

Надо добавить новое утверждение, которое не является аксиомой и не доказывается через них. Но какое именно добавить? Как оно выглядит?

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

Mikhail_K в сообщении #1169827 писал(а):

А почему с умножением?

Потому что арифметика Пеано отличается от арифметики Пресбургера наличием умножения.

[Someone]

knizhnik в сообщении #1169826 писал(а):

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

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

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

[knizhnik]

Someone в сообщении #1169830 писал(а):

Но утверждения, которые в арифметике Пеано нельзя ни доказать, ни опровергнуть, известны. Например, теорема Гудстейна
(лучше на английском языке).

Даже на английском не написано, как формализовать теорему Гудстейна. Вы можете представить ее как замкнутую формулу в арифметике? Я не могу. Не знаю как.

-- 18.11.2016, 00:29 --

Someone в сообщении #1169830 писал(а):

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

Мне только это и нужно. Получить две теории со своими моделями. В одной будет дополнительное утверждение $\varphi$, а в другой $\neg \varphi$ и разница между ними будет очевидна.

[Someone]

knizhnik в сообщении #1169831 писал(а):

Даже на английском не написано, как формализовать теорему Гудстейна.

Скорее всего, в виде одного высказывания это будет выглядеть чудовищно громоздко, и такими вещами обычно не заморочиваются. Нужно сформулировать рекурсивное определение последовательности Гудстейна. Я тоже не соображу, как это сделать, но всё, что можно вычислить, скажем, машиной Тьюринга, можно вычислить рекурсивной функцией, которую можно определить в языке арифметики Пеано.

[knizhnik]

Someone в сообщении #1169840 писал(а):

Скорее всего, в виде одного высказывания это будет выглядеть чудовищно громоздко

А зачем вы предлагаете именно это утверждение? Может есть что-то попроще? Если одна конкретная формула будет предъявлена, я смогу разобраться, почему она не подходит для арифметики Пресбургера.

[Someone]

knizhnik в сообщении #1169841 писал(а):

Если одна конкретная формула будет предъявлена, я смогу разобраться, почему она не подходит для арифметики Пресбургера.

Очевидно, потому, что язык арифметики Пресбургера не содержит символа умножения (и соответствующих аксиом). Другого различия между языками арифметики Пресбургера и арифметики Пеано нет. И для обнаружения этого различия нет нужды предъявлять какие-либо утверждения, недоказуемые и неопровержимые в арифметике Пеано.
А вот вопрос, почему в арифметике Пеано можно определить любую рекурсивную функцию, а в арифметике Пресбургера — не любую, гораздо интереснее. Но ответ придётся искать в специальной литературе.

[knizhnik]

Someone в сообщении #1169843 писал(а):

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

Ну хорошо. Приведите пожалуйста формулу с умножением.

Someone в сообщении #1169843 писал(а):

И для обнаружения этого различия нет нужды предъявлять какие-либо утверждения, недоказуемые и неопровержимые в арифметике Пеано.

Но для построения моделей разница есть. И эти модели подойдут и для Пресбургера. В общем нужна формула. Все общие слова и так уже сказаны.