Теорема Геделя о неполноте

[Sycamore]

Поскольку ZF/ZFC включают арифметику Пеано, по меньшей мере предложения Гёделя "я недоказуемо" и соответствующие диофантовы примеры продолжают оставаться невыводимыми в ZF/ZFC; стало быть, "экспертный уровнь доказательства" это скорее (неформальный) уровень обычной практики математиков-профессионалов. В этом и заключается, насколько понимаю, смысл результата Гёделя: иначе бесспорные мат. факты/"истины" остаются за пределами строгой аксиоматизации.

В этом смысле не думаю, что аксиома детерминированности (АД) будет достаточно "бесспорной/очевидной", дабы присобачить к первому классу :) , АД даже с аксиомой выбора (АВ) не совместима.

[warlock66613]

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

А можно взять такую формулировку: "в любой игре без случайности и с полной информацией у одного из игроков есть выигрышная стратегия". Это не относит аксиому детерменированности к первому классу?

Я бы сказал, что относит, но математики не согласны:

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

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

И даже "специалистам в дескриптивной теории множеств" она "интересна" только в каком-то извращённом смысле:

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

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

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

-- 03.01.2019, 22:21 --

Sycamore в сообщении #1365729 писал(а):

Поскольку ZF/ZFC включают арифметику Пеано, по меньшей мере предложения Гёделя "я недоказуемо" и соответствующие диофантовы примеры продолжают оставаться невыводимыми в ZF/ZFC

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

[Sycamore]

именно

[Sycamore]

А начал эту дискуссию вот почему.

Второй класс "аутентичных" неразрешимых предложений можно понять: несмотря на взаимное исключение, обе альтернативы будут логически "равноправными" - видимо потому, что прибавляют существенно нового содержательного смысла к наличным аксиомам и потому остаются с ними совместимыми. Это особо заметно в области больших кардиналов/мощностей, где потолка нет и произвол в выдумывании таковых доходит до бессмысленного как-бы, anything goes.

В заметном отличии, альтернативы невыводимым предложениям первого класса видимо "неравноправны" и даже вполне себе "ошибочны", так сказать: у диофантова уравнения или будет решений, или не будет, третьего не дано; не может быть ни того, ни другого, в точности одна и только одна из двух альтернатив реализуется, может пока не знаем какая из двух. К примеру, ещё до Евклида знали, что простых будет или конечное число, или их бесконечно много, третьего не могло быть, что и подтвердилось: простых оказалось/"доказало Евклидом" бесконечно много.

ЧЕГО "не хватает" арифметике Пеано с её логикой, дабы "предвосхитить" такие случаи и не оставлять дверца открытого для безупречного вывода видимо неправдоподобных/"нестандартных" альтернатив наподобие сверху? Скорее всего, (формально-аксиоматически) недоказуемых предложений нашего первого класса неперечислимо и даже несчётно много и остаётся только удивляться как мозг наш сразу и несомненно узнаёт их для себя как ... доказанными, не замечая даже, что ранг у них скорее постулатов/аксиом, а не выводимых теорем...

[mihaild]

Sycamore в сообщении #1365990 писал(а):

недоказуемых предложений ... [i[несчётно[/i] много

Предложений всего счетно.

Sycamore в сообщении #1365990 писал(а):

мозг наш сразу и несомненно узнаёт их для себя как ... доказанными

Если Ваш мозг сразу и несомненно, только увидев определение, понял, что, например, все последовательности Гудштейна конечные - то мне остается только снять шляпу и попытаться выяснить, как вы это делаете (можете попробовать описать?).
Если же нет - то, скорее всего, вы, как и я, как и многие раньше и позже, придумали или проверили доказательство этого утверждения в ZF. Можно было взять вместо ZF другую теорию и доказать, что существует бесконечная последовательность Гудштейна.
Вся разница только в том, что ZF кажется "интуитивной".

Sycamore в сообщении #1365990 писал(а):

Это особо заметно в области больших кардиналов/мощностей, где потолка нет и произвол в выдумывании таковых доходит до бессмысленного как-бы, anything goes.

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

[Sycamore]

Не был уверен, но естественно ожидать, что такие недоказуемые в арифметике теоремы как Рамсея, Гудстейна и другие (https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 0%BA%D0%B8) можно будет доказать в некоторой подходящим образом аксиоматизированной теории множеств - дело, конечно, не в лёгкости или очевидности, а в убедительности и бесспорности такого доказательства на экспертно-интиутивном уровне. Полагаю, что арифметика не менее интуитивна, чем ZF, просто нарочито "слабее", а ZF уже на грани интуитивности

Для меня остаётся как-бы загадкой то, что даже в ZF продолжают здравствовать, по-видимому, сравнительно тривиальные Гёделевы "я недоказуемо" (в ZF, то бишь), могут, значит, здравствовать и другие подобные (диофантовые уравнения?), для включения которых потребуется ad-hoc расширений ZF и пр.

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

Sycamore в сообщении #1365990 писал(а):

Это особо заметно в области больших кардиналов/мощностей, где потолка нет и произвол в выдумывании таковых доходит до бессмысленного как-бы, anything goes.

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

Не понял про кодировние каких последовательностей идёт речь, но показалось, что - в отличие от минимального и регулярного +1 для "слишком больших" натуральных - генерация больших кардиналов происходит ... чёрт знает как)

[Someone]

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

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

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

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

С арифметикой, на самом деле, то же самое - могут быть какие-то "слишком большие" числа, которые кодируют какие-то странные вещи

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

Sycamore в сообщении #1365586 писал(а):

Сообщение сверху скорее неудачно отражает следующий вопрос о напрашивающемся различии между как-бы двумя классами аксиоматически/формально недоказуемых предложений. С одной стороны, это класс оригинальных Гёделевых предложений "я недоказуемо", арифметических теорем Рамсея (результат Пэриса - Харрингтона, https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 0%BD%D0%B0 ) и Гудстейна, диофантова примера неполноты вслед за Матиясевичем (https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 0%BC%D0%B0 ) и других подобных, видимо "истинных/доказанных" на экспертном, хоть и неформальном, уровне предложений.

У Вас тут какая-то каша.

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

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

Sycamore в сообщении #1365586 писал(а):

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

В этом отношении "второй" класс ничем не отличается от "первого".

Sycamore в сообщении #1366037 писал(а):

Не был уверен, но естественно ожидать, что такие недоказуемые в арифметике теоремы как Рамсея, Гудстейна и другие (https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 0%BA%D0%B8 ) можно будет доказать в некоторой подходящим образом аксиоматизированной теории множеств

Упомянутые Вами теоремы доказуемы в ZF. Поэтому ничего изобретать не надо.

[Sycamore]

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

Удивляет и занимает концептуальное происхождение такого феномена. Я понимаю, что можно строить (непротиворечивые) модели со сколь угодно "неинтуитивными" аксиомами, но каково значение/ценность таких моделей, насколько ими занимаются? Как-то показалось, что некоторые альтернативы (некоторым "железным" предложениям из "первого" класса) не стоят свеч...

[Someone]

Sycamore в сообщении #1366096 писал(а):

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

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

[Sycamore]

Да, и спасибо Вам за зуд - случаем натолкнулся на обучение Вами форумчан кардиналам или чему-то подобному.

Я стараюсь не забывать, что сам не специалист (мягко выражаясь) и стараюсь также учиться у таковых. Давным-давно как-то произвело впечатление, что в выкладках в своей книге о гипотезе континуума Пол Коэн часто ссылался на теорему Гёделя о непротиворечивости, что остроумно и элегантно выводится из теоремы о неполноте. Потому показалось, что феномен неполноты фундаментален и может всплыть неожиданно.

Позже, в своей книжке "Доказуемое и недоказуемое" Ю.И. Манин вроде коротко упомянул, что если учесть (совершенно неконструктивным образом, видимо) некое бесконечное множество предложений арифметики, то она стала бы полной; помню, что плохо понял что это за множество :)