Для каждой непротиворечивой формальной теории T, имеющей требуемый небольшой объем теории чисел, соответствующее гёделевское предложение G утверждает: «G не может быть доказано в рамках теории T». Эта интерпретация G приводит к следующему неформальному анализу. Если бы G была доказуема в соответствии с аксиомами и правилами вывода T, то T имела бы теорему G, которая эффективно противоречит самой себе, и, таким образом, теория T была бы несовместимой. Это означает, что если теория T непротиворечива, то G не может быть доказана в ней, и поэтому теория T неполна. Более того, утверждение G о собственной недоказуемости верно. В этом смысле G не только недоказуема, но и истинна, а доказуемость-в-теории-T не то же самое, что истина. Этот неформальный анализ можно формализовать для строгого доказательства теоремы о неполноте, как описано в разделе "Набросок доказательства первой теоремы ниже. Формальное доказательство выявляет именно те гипотезы, которые необходимы для теории Т, чтобы внутренне противоречивая природа G приводила к подлинному противоречию.
Я нашел этот текст о первой теореме Гёделя о неполноте в википедии . Я не понимаю утверждения, в котором говорится: «Если G доказуема, то G противоречит сама себе». Кто-нибудь может уточнить?
PS: я новичок в обсуждении философии. Так что прошу прощения за возможные ошибки.
Мы должны напомнить утверждение теоремы:
Первая теорема о неполноте (Гёделя) . Любая ω-согласованная формальная система S , внутри которой может быть выполнено «некоторое количество» элементарной арифметики, неполна по отношению к утверждениям элементарной арифметики: т. е. существуют такие утверждения, которые нельзя ни доказать, ни опровергнуть в S.
Аргумент первой теоремы Гёделя о неполноте немного сложен.
Кроме того, условие ω-непротиворечивости несколько «запутано»; таким образом, исходя из изложения Вики , мы разовьем «простой» аргумент, предполагая надежность системы S [т. е. система S не доказывает ложных предложений; кстати, добротность подразумевает постоянство ].
Мы должны начать с:
1) Арифметизация синтаксиса : основная проблема [состоит] в построении утверждения p , которое эквивалентно « p не может быть доказано» [...] Гениальный метод Гёделя состоит в том, чтобы показать, что утверждения могут быть сопоставлены с числами (часто называемое арифметизацией синтаксиса таким образом, чтобы «доказательство утверждения» можно было заменить «проверкой того, обладает ли число данным свойством» [здесь нам нужно, чтобы свойство системы S включало «некоторое количество» арифметики: система S должна иметь достаточно возможностей, чтобы «выразить» синтаксические отношения и свойства самой системы].
2) Построение утверждения о «доказуемости» . Показав, что в принципе система может косвенно делать утверждения о доказуемости, анализируя свойства тех чисел, которые представляют утверждения, теперь можно показать, как создать утверждение, которое на самом деле делает это.
Следовательно, существует форма утверждения Bew(y) , в которой используется это арифметическое отношение, чтобы утверждать, что число Гёделя доказательства y существует:
Bew(y) = ∃ x ( y — число Гёделя формулы, а x — число Гёделя доказательства [в S ] формулы, закодированной y ).
Последний шаг:
Диагонализация : Следующим шагом в доказательстве является получение утверждения, которое утверждает, что оно недоказуемо. Хотя Гёдель построил это утверждение напрямую, существование по крайней мере одного такого утверждения следует из диагональной леммы, которая говорит, что для любой достаточно сильной формальной системы и любой формы высказывания F существует утверждение p такое, что система [ S ] доказывает:
р ↔ F(G(p)) .
Полагая F отрицанием Bew(x) , мы получаем теорему
р ↔ ~Bew(G(p)) ,
и определяемое этим p грубо утверждает, что его собственное число Гёделя является числом Гёделя недоказуемой формулы.
Утверждение p [...] гласит, что если выполнить определенный расчет, результирующее число Гёделя будет числом недоказуемого утверждения. Но когда это вычисление выполняется, результирующее число Гёделя оказывается числом Гёделя самого p .
Теперь мы можем собрать все ингредиенты вместе.
Рассуждения в доказательстве Гёделя теперь следующие. Во- первых, если p на самом деле является теоремой S , то в S доказуемо , что p является теоремой S [то есть: Bew(G(p)) , формула, которая утверждает, что существует число x , которое является Число Гёделя доказательства в S формулы, закодированной G(p) ].
Причина этого в том, что «быть теоремой S » — это свойство, которое можно проверить, представив доказательство в S , и поскольку быть доказательством в S требуется, чтобы быть вычислимым свойством последовательностей предложений, проверка может быть выполняется внутри самого S [опять же: S включает в себя «некоторое количество» арифметических операций...].
Таким образом, если S доказывает p , т. е. если p является теоремой S , то S также доказывает ~Bew(G(p)) в силу описанной выше эквивалентности [напомним, что p является доказуемой неподвижной точкой свойства не быть теоремой С ]; но это также доказывает Bew(G(p)) , согласно предыдущему аргументу. Итак, у нас есть противоречие.
Теперь рассмотрим случай, когда S доказывает ~p ; путем «построения» p оно доказывает предложения, «говорящие, что » p недоказуемо . Теперь у нас есть две возможности.
(i) доказательство p существует: в этом случае S явно противоречиво ;
в противном случае :
(ii) доказательство p не существует: в этом случае S доказывает ложное предложение , потому что оно доказывает Bew(G(p)) , которые утверждают, что доказательство существует. Таким образом, S должно быть несостоятельным .
Вывод: если предположить, что S «способна» выражать «некоторое количество» арифметических операций, система S не может быть одновременно надежной и полной .
Но мы остаемся при нашем «естественном понимании» правильности арифметики. Таким образом, система, «содержащая» арифметику, должна быть неполной .
Доказав, что гёделевское предложение p недоказуемо в S из-за того, что p можно «прочитать» как утверждение собственной недоказуемости , доказательство Гёделя показывает, что p истинно . Таким образом, помимо доказательства существования недоказуемого предложения, доказательство Гёделя дает нам метод «производства»:
истинное предложение , выражаемое в S , которое не доказуемо в S.
См. Торкель Франзен, Теорема Гёделя. Неполное руководство по ее использованию и злоупотреблениям (2005).
Если вы понимаете, как формальные системы работают в логике и математике, то теоремы Гёделя лучше всего излагаются, если пройтись по модальной логике, называемой логикой доказуемости.
Существует (стандартная) модальная логика, называемая К , по Крипке, которая (стандартно) моделирует необходимость и чьи аксиомы
Если T |- p, то T |- Np
Если задано T |- N(p -> q) , то T |- Np -> Nq
Для всех p имеем T |-Np ->NNp
Первая аксиома говорит, что если p имеет место, то p обязательно имеет место; тогда второй говорит, что если р обязательно подразумевает q , то обязательно тот случай, когда р обязательно подразумевает q .
Заметим также, что если p обязательно имеет место, то p необходимо, необходимо имеет место, или в символах это третья аксиома.
Мы добавляем новую аксиому, мотивация которой проистекает из доказуемости, называемую аксиомой Лобса, и которая гласит:
Лоб: Для каждого p у нас есть N(Np ->p) -> Np
В этой модальной логике мы можем показать, что она удовлетворяет теореме о неподвижной точке, которая гласит, что если задан предикат A(p) , зависящий от пропозициональной переменной p , то существует формула q , в которой p не появляется, и
Thm: |- q <-> A(q)
Теперь оказывается, что предикат доказуемости P в арифметике удовлетворяет аксиомам модальной логики, разработанным выше, как и эта теорема о неподвижной точке.
Наконец, установив A(p):= not Pp , так что p недоказуемо, тогда его фиксированная точка не является P(_|_) , то есть это не доказывает противоречие, и мы имеем от фиксированной точки теорема, предложение:
|- не Р(_|_) <-> не Р(не Р(_|_))
Читая это (слева направо), он говорит, что если мы не можем вывести несоответствие, то мы не можем доказать, что можем вывести несоответствие. Это теорема Гёделя о неполноте, которая утверждает, что непротиворечивая теория имеет предложение, которое является истинным, но недоказуемым — и мы показали, что это утверждение является недоказуемым.
Все это есть в статье SEP о логике доказуемости
Система может доказать свою правоту только тогда, когда она противоречива. В таких случаях система может доказать что угодно, даже свою собственную истинность и непротиворечивость. Итак, если G доказуема, это доказуемо, потому что G противоречива.
G: «G нельзя доказать в рамках теории T».
«Если G доказуема, то G противоречит сама себе».
Итак, предположим, что кто-то сумел доказать, что G истинен в рамках Т-теории.
Но так как G утверждает обратное, т. е. что это не может быть доказано в рамках Т-теории, то, если доказывается, что это правда, это оказывается... ложным. Так что оно противоречиво, так как одновременно истинно и ложно.
Это вариант парадокса Эпименида («Все, что я говорю, ложь...», что верно только в том случае, если не соответствует действительности).
Гёделю удалось построить предложение G, которое выражает «нет доказательства для предложения G». Теперь посмотрите на предложение, которое ставит перед вами проблему: «Если G доказуема, то G противоречит сама себе».
Г делает заявление. Если утверждение, противоположное тому, что делает G, истинно, то очевидно, что G ложно. Каково утверждение Г? «Для приговора G нет доказательств». Что противоречит этому утверждению? «Есть доказательство предложения G». Ранее мы видели: «Если противоположное утверждению, которое делает G, истинно, то G ложно». Итак, «если есть доказательство предложения G, то G ложно».
Мауро АЛЛЕГРАНСА
Мозибур Улла
Мауро АЛЛЕГРАНСА