Гёдель: Почему предложение неразрешимо?

Этот ответ немного технический, но я думаю, что ОП найдет его интересным.

Позвольте мне сначала напомнить немного об истории теоремы о неполноте (IT). Как обычно утверждается ИТ:

Если PA (или любая рекурсивно аксиоматизируемая теория, расширяющая PA) непротиворечива, то «PA непротиворечива» неразрешима в PA.

Однако это не то , что первоначально доказал Гедель! Доказательство Геделя потребовало дополнительного предположения: что PA достаточно корректна (в частности, что PA $\omega$-непротиворечива ). Это, конечно, неудачная гипотеза; кроме того, что теорема становится слабее, она также привносит, надеюсь, ненужную часть платонизма. (Хорошо, скажем, вас устраивает платонизм; какое вам дело до последовательных, но ложных теорий? Ответ на этот вопрос см. ниже.)

В частности, Гедель мог легко показать, что «PA не доказывает Con(PA)», но демонстрация «PA не опровергает Con(PA)» требовала дополнительного предположения. Итак, строго говоря, первоначальный аргумент Геделя, безусловно, содержал теорему о недоказуемости , но, возможно, не дотягивал до теоремы о полной неразрешимости (т. е. недоказуемости и недоказуемости).

Гёдель оставил открытым вопрос, можно ли отказаться от этого предположения. Это было решено, что привело к обычному утверждению IT, Россером , который показал, как технический прием может улучшить аргумент Геделя. Таким образом, доказательство Геделя превратилось в настоящую теорему о неразрешимости.

Улучшение Россера не просто привело к «более формалистской» версии ИТ; это также имело реальные последствия, относящиеся к вашему вопросу. В частности, он показывает:

Недоказуемость невычислима: не существует алгоритма, который может определить, является ли данное предложение на языке арифметики недоказуемым из PA.

Почему бы и нет? Что ж, предположим, что A был бы таким алгоритмом. Тогда мы могли бы построить непротиворечивое полное рекурсивно аксиоматизируемое расширение PA (противоречащее версии IT Россера!) следующим образом:

• Перечислите предложения арифметики разумным образом как P_1, P_2, P_3, ...

• Определите Q_i индуктивно следующим образом:

  • Q_1="Не P_1", если P_1 недоказуем в PA, и Q_1="P_1" в противном случае.

  • Определив Q_i, мы допускаем Q_{i+1}="Not P_{i+1}", если предложение "(Q_1 и Q_2 и ... и Q_i) подразумевает P_{i+1}" недоказуемо в PA, и Q_{i+1}="P_{i+1}" в противном случае.

Предполагая существование A, последовательность Q_i вычислима. Теперь рассмотрим теорию T=PA+{Q_1, Q_2, Q_3, ...}; эта теория рекурсивно аксиоматизирована, расширяет PA и (по простому аргументу индукции) непротиворечива; упс!

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

Теперь к сути вопроса: некоторые причины неразрешимости.

Вышеприведенный пункт о том, что недоказуемость невычислима, можно изменить на «неразрешимость невычислима» без особых усилий. Интуитивно это говорит о том, что существует множество причин неразрешимости (или недоказуемости) и что у нас никогда не будет полного понимания того, что движет явлением. Интересно, что это противоречит общему факту, упомянутому Джобермарком выше, что почти все известные в настоящее время примеры неразрешимости исходят из проблем самореференции.

Однако есть случаи недоказуемости, которые не происходят из парадоксов и для которых существуют разумные философские доказательства недоказуемости; позвольте мне привести пример одного из них, которому я научился у Асафа Карагилы . Это пример неразрешимости не из PA, а скорее из ZFC (= стандартная теория множеств; это теория первого порядка, несмотря на то, что она касается множеств, и к ней применимы теоремы Геделя ). В частности, соответствующий язык отличается — вместо того, чтобы работать на языке ${+, \times, <, 0, 1}$ (или аналогичном) арифметики, мы работаем на языке ${\in}$ теория множеств.

Недоступный кардинал — это особенно большой бесконечный кардинал. В частности, это кардинал, который больше, чем мощность любого кардинала ниже него, а также удовлетворяет более техническому условию «регулярности» . Интуитивно недоступные кардиналы не могут быть «построены из меньших кардиналов».

Пусть P будет предложением «Есть недостижимый кардинал» (нетрудно, но несколько утомительно выразить это на языке теории множеств), и давайте подумаем о P в теории множеств ZFC. Существует ряд философских аргументов в пользу непротиворечивости ZFC вместе с P; см., например, статью Пенелопы Мэдди «Вера в аксиомы». Итак, давайте на данный момент примем Con(ZFC+P) как должное, то есть, что ZFC не опровергает P. Как мы можем показать, что ZFC также не доказывает P?

Обычное доказательство этого — с помощью теоремы Геделя: покажите, что ZFC+P доказывает Con(ZFC). Однако есть доказательство того, что этого можно избежать! Предположим, что ZFC доказала P. Тогда пусть V будет моделью ZFC. Поскольку V является моделью ZFC, а ZFC доказывает P, в V есть некоторый k, который V считает (i) недостижимым кардиналом и (ii) наименее недостижимым кардиналом (поскольку V удовлетворяет регулярности, для любого определимого свойства существует наименьший кардинал с этим свойством, если любой кардинал с этим свойством существует в первую очередь).

Но теперь рассмотрим V_k, k-й уровень кумулятивной иерархии V. Несложно проверить, что V_k удовлетворяет аксиомам ZFC. Но у В_к не может быть недоступного кардинала! Это связано с тем, что любой недоступный кардинал m в V_k также будет недоступным кардиналом в V (это неочевидно и требует короткого аргумента; в частности, это неверно, если мы заменим «недоступный» более сложным понятием большого кардинального числа !) , и будет меньше k (поскольку каждый кардинал в V_k меньше k); но k по определению был наименее недоступным кардиналом в V. Так что это противоречие.

Обратите внимание, что мы ни разу не вызывали ОНО! Это пример феномена недоказуемости, возникающего по «чисто математическим» (то есть неметаматематическим) причинам. Конечно, это различие очень субъективно, и разумные люди, намного умнее меня, вполне могут не согласиться с утверждением, которое я сделал в предыдущем предложении; но я все еще думаю, что это интересно.

Между прочим, также стоит отметить, что у самой теоремы о неполноте есть доказательство, которое на самом деле не зависит от парадоксов: а именно, Крипке дал доказательство , которое в некоторых отношениях похоже на аргумент о недоступных объектах, который я изложил выше. См. этот мой вопрос на mathoverflow для еще нескольких доказательств неполноты.

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

Например, доказательство Геделя представляет собой сложную и неотвратимую версию критского парадокса. Он выдает предложение, которое гласит: Предложение #[большое число] не входит в список вещей, которые мы когда-либо можем доказать, и, кстати, это предложение #[большое число]. Другими словами: предложения с критской нумерацией никогда не бывают доказуемо истинными, говорит критская нумерация. Но в отличие от оригинального критского, здесь только говорится, что это недоказуемо, а не о том, что это ложь. Таким образом, мы можем избежать абсолютного парадокса, приняв тот факт, что есть вещи, которые верны, но система не может их доказать.

Более простая версия основана на «парадоксе Берри»: «Наименьшее положительное целое число, которое не может быть определено менее чем двенадцатью словами», содержит менее двенадцати слов и, следовательно, не определяет никакого положительного целого числа. Если мы систематически подсчитаем количество доказуемых утверждений, мы сможем, используя систему исчисления, всегда найти эквивалент магического числа двенадцать в исходном парадоксе. Мы можем доказать, что любое доказуемое утверждение о данном числе «по меньшей мере настолько сложно, чтобы его можно было сформулировать», но сформулировать этот факт в утверждении, менее сложном, чем установленный минимум.

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

Мы можем найти новые неразрешимые аспекты любой формальной системы, формализовав принципы, из которых вытекают известные нам парадоксы :

1. Самореференция и отрицание имеют ограниченную совместимость (парадокс Рассела и все его родственники)
2. Бесконечность и порядок имеют ограниченное значимое применение по отношению друг к другу (неожиданная независимость аксиомы выбора и гипотезы континуума).
3. Непрерывность и идентифицируемость имеют ограниченную совместимость (проблемы соритов, причудливые ограничения бесконечно малых величин и парадокс Банаха-Тарского).
4. Возможность узнать, какие обобщения составляют определения, а какие нет, неявно ограничена (важные наборы Геделя-Бернайса-Фон Неймана, которые не могут быть множествами — например, «группа» всех групп по продуктам, которая не может быть группой, потому что ее базовое множество будет содержать наборы любого размера, но будет просто группой с любой нормальной точки зрения.)

Кант уже указал на один случай каждого из этих ограничений в своих «антиномиях» — четыре проблемы, которые, как он чувствовал, он продемонстрировал, были значимыми проблемами, которые люди не могут решить:

• 1 суть его ответа на проблему свободы воли,
• 2 суть его ответа на проблему конца времен,
• 3 суть его ответа на проблему атомов,
• 4 — суть его ответа на проблему необходимого бытия.

Теперь, когда мы понимаем, что формальные системы на самом деле не помогают снять эти ограничения, мы создали формальные системы, которые их обходят или разрешают, или мы пришли к их принятию. Но это не означает, что они являются единственными источниками потенциальных конфликтов. Мы знаем, что это не так.

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

Определение: Утверждение неразрешимо, если нет ни доказательства его истинности, ни доказательства его ложности.

Предложение: Вчера утром я выпил чашку кофе.

Итак, есть ли доказательства этого довольно безобидного предположения? В этом нет ничего сложного или метафизического; его легко понять, он не требует сложной или даже простой математики и доступен повседневному опыту почти каждого; что касается правды... Я могу поручиться за ее истинность.

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

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

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

Что важно в упражнении, которое проделал Гёдель, так это изобретение формальной системы и сопутствующего ей аппарата; например, существует доказательство гильбертовского Nullstellensatz с использованием инструментов, разработанных на основе идей Гёделя.

Таким образом, неразрешимость — это широко распространенный феномен реального мира, и мы вовсе не должны удивляться, обнаружив его отражение в формальных системах, пытающихся объяснить или отразить его, — таких как натуральные числа или геометрия; удивительно, я полагаю, что это может быть показано в такой простой системе, как арифметика; но тогда, как показали такие вопросы, как теорема Ферма или все еще нерешенная гипотеза Римана, они могут быть очень трудными; так что не так уж и удивительно.