Самостоятельная ссылка на проблему P / NP иногда подчеркивалась как барьер для ее разрешения, см., Например, статью Скотта Ааронсона, является ли P против NP формально независимой ? Одним из многих возможных решений P / NP будет демонстрация того, что проблема формально не зависит от ZFC или является истинной, но недоказуемой.
Вполне возможно, что самореферентность проблемы может создать более серьезную проблему при доказательстве независимости, например, если утверждения о ее доказуемости сами по себе недоказуемы или иным образом невозможно рассуждать.
Предположим, мы назовем теорему T Godel_0, если она верна, но недоказуема в смысле теоремы Годеля. Вызовите T Godel_1, если утверждение «T is Godel_0» верно, но недоказуемо. Вызовите T Godel_i, если утверждение «T is Godel _ {(i-1)} верно.
Мы знаем, что существуют операторы Godel_0, и было найдено несколько примеров «в дикой природе», которые явно не сконструированы для этой цели, как в этой статье .
У меня вопрос: существуют ли какие-либо утверждения Godel_1 или выше? Являются ли такие утверждения естественным следствием теоремы Годеля?
Как насчет утверждения, о котором мы можем абсолютно ничего не доказать: то есть, для которого для каждого k > 0 T является Godel_k?
Я могу задать аналогичный вопрос для формальной независимости, хотя я подозреваю, что ответ "нет" там.
Чтобы вернуться к вопросу P против NP, позвольте мне спросить, есть ли хотя бы намек на то, что теорема Годеля относится к вопросам отделимости классов. Были ли идентифицированы какие-либо истинные, но недоказуемые утверждения в отношении классов сложности - помимо, конечно, очевидной связи между проблемой остановки и теоремой Годеля?
источник
Ответы:
Как уже отмечали другие, с постановкой вашего вопроса есть определенные технические трудности. Чтобы их исправить, давайте начнем с того, что избегаем использования термина «недоказуемое» без оговорок, и уточним, из какого набора аксиом ваше утверждение T должно быть недоказуемым. Например, предположим, что нас интересуют утверждения T, которые недоказуемы из PA, аксиомы арифметики Пеано первого порядка.
Первое раздражение в том, что «Т истинно» не выражается на языке арифметики первого порядка по теореме Тарского. Мы могли бы обойти это, работая в метатеории, достаточно мощной, чтобы определить истинность арифметического утверждения, но я думаю, что для ваших целей это излишне сложный путь. Я думаю, что вы не так заинтересованы в правде как таковой, но в доказуемости. То есть я подозреваю, что вы будете удовлетворены определением T как Godel_0, если T истинно, но недоказуемо в PA, и определением T как Godel_1, если T недоказуемо в PA, но «T недоказуемо в PA» недоказуемо в PA, и определение T как Godel_2, если T недоказуемо в PA, а «T недоказуемо в PA» недоказуемо в PA, но «T недоказуемо в PA, недоказуемо в PA» недоказуемо в PA и т. д.
Этого достаточно, чтобы уточнить ваш вопрос, но, к сожалению, есть довольно тривиальное решение. Возьмем T = «PA соответствует». Тогда T верно, потому что PA непротиворечиво, а T недоказуемо в PA по 2-й теореме Гёделя о неполноте. Кроме того, «T недоказуемо в PA» также недоказуемо в PA по несколько глупой причине: любое утверждение вида «X недоказуемо в PA» недоказуемо в PA, потому что «X недоказуемо в PA», что тривиально подразумевает, что PA непротиворечиво "(поскольку несовместимые системы доказывают все ). Так что T - это Godel_n для всех n, но я не думаю, что это действительно так.
Мы могли бы попытаться «исправить» ваш вопрос, чтобы избежать таких мелочей, но вместо этого позвольте мне попытаться ответить на то, что я считаю вашим заданным вопросом. Молчаливо, я полагаю, что вы объединяете логическую силу, необходимую для доказательства теоремы с психологической трудностьюдоказать это. Таким образом, вы интерпретируете результат формы «T недоказуем в X» как выражение, что T каким-то образом находится за пределами нашей способности понимать. Существуют эти чудовищные предположения, и мы, маленькие люди, взламываем PA-кнуты или ZFC-кнуты или что-то еще у этих свирепых зверей, пытаясь приручить их. Но я не думаю, что «Т недоказуемо в Х» следует интерпретировать как значение «Т невозможно рассуждать». Скорее, это просто измерение определенного технического свойства T, а именно его логической силы. Поэтому, если вы пытаетесь придумать убер-монстра, я не думаю, что найти что-то, что не только недоказуемо, но чья недоказуемость недоказуема и т. Д., Является правильным направлением.
Наконец, что касается вашего вопроса о том, кажется ли вообще недоказуемость связанной с отделимостью классов сложности, существуют некоторые связи между вычислительной неразрешимостью и недоказуемостью в некоторых системах ограниченной арифметики. Часть этого упоминается в статье Ааронсона, которую вы цитируете; см. также книгу Кука и Нгуена « Логические основы сложности доказательств» .
источник
Я не очень уверен насчет определения Godel_1. Вы можете попытаться формализовать это немного больше?
Как вы можете закодировать формулу "T is Godel_0"? Для этого вам нужно как-то закодировать, что «T семантически верно», не обращаясь к понятию доказательства. Как ты можешь это сделать?
источник
Заявления Godel_n существуют для каждого n. Возможно, вас заинтересует книга «Недоказуемость последовательности» Джорджа Булоса. Он определяет модальную логику, в которой «Box» означает «доказуемо», «Diamond» означает «согласованно», а затем приступает к исследованию поведения предложений типа Годеля. (Он также написал книгу «Логика обеспечения»).
источник