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

редактировать
This is the latest accepted revision, reviewed on 29 September 2021. "Бью" перенаправляется сюда. Для использования в других целях, см Бью (значения).

Неполноты теорема Геделя две теоремы о математической логике, которые имеют отношение к пределам доказуемости в формальных теориях аксиоматических. Эти результаты, опубликованные Куртом Геделем в 1931 году, важны как для математической логики, так и для философии математики. Эти теоремы широко, но не универсально, интерпретируются как показывающие, что программа Гильберта по нахождению полного и непротиворечивого набора аксиом для всей математики невозможна.

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

Используя диагональный аргумент, теоремы Гёделя о неполноте были первой из нескольких тесно связанных теорем об ограничениях формальных систем. За ними последовали теорема Тарского о неопределенности формальной истины, доказательство Черча неразрешимости Entscheidungsproblem Гильберта и теорема Тьюринга о том, что не существует алгоритма для решения проблемы остановки.

СОДЕРЖАНИЕ
  • 1 Формальные системы: полнота, непротиворечивость и эффективная аксиоматизация
    • 1.1 Эффективная аксиоматизация
    • 1.2 Полнота
    • 1.3 Последовательность
    • 1.4 Системы, содержащие арифметику
    • 1.5 Противоречивые цели
  • 2 Первая теорема о неполноте
    • 2.1 Синтаксическая форма предложения Гёделя
    • 2.2 Истина предложения Гёделя
    • 2.3 Отношения с парадоксом лжеца
    • 2.4 Расширение первоначального результата Гёделя
  • 3 Вторая теорема о неполноте
    • 3.1 Выражение последовательности
    • 3.2 Условия Гильберта – Бернейса
    • 3.3 Значение доказательств непротиворечивости
  • 4 Примеры неразрешимых утверждений
    • 4.1 Неразрешаемые утверждения, доказуемые в более крупных системах
  • 5 Связь с вычислимостью
  • 6 Схема доказательства первой теоремы
    • 6.1 Арифметизация синтаксиса
    • 6.2 Построение утверждения о «доказуемости»
    • 6.3 Диагонализация
    • 6.4 Доказательство через парадокс Берри
    • 6.5 Доказательства, подтвержденные компьютером
  • 7 Схема доказательства второй теоремы
  • 8 Обсуждение и последствия
    • 8.1 Последствия для логицизма и вторая проблема Гильберта
    • 8.2 Умы и машины
    • 8.3 паранепротиворечивая логика
    • 8.4 Апелляции к теоремам о неполноте в других областях
  • 9 История
    • 9.1 Объявление
    • 9.2 Обобщение и принятие
    • 9.3 Критика
      • 9.3.1 Финслер
      • 9.3.2 Цермело
      • 9.3.3 Витгенштейн
  • 10 См. Также
  • 11 Источники
    • 11.1 Цитаты
    • 11.2 Статьи Гёделя
    • 11.3 Переводы работы Гёделя на английский язык при его жизни
    • 11.4 Статьи других авторов
    • 11.5 Книги о теоремах
    • 11.6 Разные ссылки
  • 12 Внешние ссылки
Формальные системы: полнота, последовательность и эффективная аксиоматизация

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

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

Эффективная аксиоматизация

Формальная система называется эффективно аксиоматизированной (также называемой эффективно порожденной), если ее набор теорем является рекурсивно перечислимым множеством ( Franzén 2005, p. 112). harv error: no target: CITEREFFranzén2005 ( help )

Это означает, что существует компьютерная программа, которая, в принципе, может перечислить все теоремы системы, не перечисляя никаких утверждений, не являющихся теоремами. Примеры эффективно генерируемых теорий включают арифметику Пеано и теорию множеств Цермело – Френкеля (ZFC).

Теория, известная как истинная арифметика, состоит из всех истинных утверждений о стандартных целых числах на языке арифметики Пеано. Эта теория последовательна, полна и содержит достаточный объем арифметики. Однако он не имеет рекурсивно перечислимого набора аксиом и, следовательно, не удовлетворяет условиям теорем о неполноте.

Полнота

Набор аксиом является ( синтаксически или отрицание -) полным, если для любого утверждения на языке аксиом это утверждение или его отрицание доказуемо с помощью аксиом ( Smith 2007, p. 24). Это понятие относится к первой теореме Гёделя о неполноте. Не следует путать с семантической полнотой, что означает, что набор аксиом доказывает все семантические тавтологии данного языка. В своей теореме о полноте Гёдель доказал, что логика первого порядка семантически полна. Но он не является синтаксически полным, поскольку есть предложения, выражаемые на языке логики первого порядка, которые нельзя ни доказать, ни опровергнуть только с помощью аксиом логики. harv error: no target: CITEREFSmitdiv class="ht"007 ( help )

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

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

Теория арифметики Пеано первого порядка кажется последовательной. Предполагая, что это действительно так, обратите внимание, что он имеет бесконечный, но рекурсивно перечислимый набор аксиом и может кодировать достаточно арифметических действий для гипотез теоремы о неполноте. Таким образом, по первой теореме о неполноте арифметика Пеано не является полной. Теорема дает явный пример арифметического утверждения, которое нельзя ни доказать, ни опровергнуть в арифметике Пеано. Более того, это утверждение верно и в обычной модели. Кроме того, никакое эффективно аксиоматизированное и последовательное расширение арифметики Пеано не может быть полным.

Последовательность

Набор аксиом (просто) непротиворечив, если нет такого утверждения, что и утверждение, и его отрицание доказуемы на основе аксиом, и несовместимы в противном случае.

Арифметика Пеано доказуемо согласована с ZFC, но не внутри себя. Точно так же ZFC не доказуемо непротиворечиво изнутри, но ZFC + «существует недоступный кардинал » доказывает, что ZFC непротиворечив, потому что если κ является наименьшим таким кардиналом, то V κ, находящийся во вселенной фон Неймана, является моделью ZFC, и теория непротиворечива тогда и только тогда, когда у нее есть модель.

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

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

Системы, содержащие арифметику

Теоремы о неполноте применимы только к формальным системам, которые способны доказать достаточный набор фактов о натуральных числах. Одна достаточная коллекция множество теорем Robinson арифметической Q. Некоторые системы, такие как арифметика Пеано, могут напрямую выражать утверждения о натуральных числах. Другие, например теория множеств ZFC, могут интерпретировать утверждения о натуральных числах на своем языке. Любой из этих вариантов подходит для теорем о неполноте.

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

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

Дэн Willard  ( 2001) изучила некоторые слабые семьи арифметических систем, которые позволяют достаточно арифметика как отношения формализовать гёделевскую нумерацию, но не достаточно сильно, чтобы иметь умножение как функция, и поэтому не в состоянии доказать вторую теорему о неполноте; эти системы непротиворечивы и способны доказать свою непротиворечивость (см. теории самопроверки ).

Противоречивые цели

При выборе набора аксиом одна цель состоит в том, чтобы суметь доказать как можно больше правильных результатов без доказательства каких-либо неправильных результатов. Например, мы могли бы представить себе набор истинных аксиом, которые позволят нам доказать каждое истинное арифметическое утверждение о натуральных числах ( Smith 2007, p. 2). В стандартной системе логики первого порядка несовместимый набор аксиом доказывает каждое утверждение на его языке (это иногда называют принципом взрыва ) и, таким образом, автоматически завершается. Множество аксиом является одновременно полным и последовательным, однако, доказывает максимальное множество непредставленных противоречивых теорем ( Хинман 2005, стр. 143). harv error: no target: CITEREFSmitdiv class="ht"007 ( help ) harv error: no target: CITEREFHinman2005 ( help )

Шаблон, проиллюстрированный в предыдущих разделах с арифметикой Пеано, ZFC и ZFC + «существует недоступный кардинал», обычно не может быть нарушен. Здесь ZFC + «существует недоступный кардинал» не может быть доказана непротиворечивостью из самого себя. Это также не является полным, как показано в ZFC + "существует недоступная кардинальная" теория неразрешенной гипотезы континуума.

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

Первая теорема о неполноте
Смотрите также: Набросок доказательства первой теоремы Гёделя о неполноте

Первая теорема Гёделя о неполноте впервые появилась как «Теорема VI» в статье Гёделя 1931 года « О формально неразрешимых предложениях Principia Mathematica и родственных систем I». Вскоре после этого предположения теоремы были улучшены Дж. Баркли Россером ( 1936) с помощью уловки Россера. Результирующая теорема (включающая улучшение Россера) может быть перефразирована на английском языке следующим образом, где «формальная система» включает предположение, что система эффективно сгенерирована.

Первая теорема о неполноте: «Любая непротиворечивая формальная система F, в которой может быть проведена определенная элементарная арифметика, является неполной; т. Е. Есть утверждения языка F, которые нельзя ни доказать, ни опровергнуть в F ». (Раатикайнен 2015)

Недоказуемо оператор G F называется теоремой часто упоминаются как «еделевские предложения» для системы F. Доказательство строит конкретное предложение Гёделя для системы F, но существует бесконечно много утверждений на языке системы, которые разделяют одни и те же свойства, такие как конъюнкция предложения Гёделя и любого логически действительного предложения.

Каждая эффективно сгенерированная система имеет собственное предложение Гёделя. Можно определить более крупную систему F ',  которая содержит все F плюс G F в качестве дополнительной аксиомы. Это не приведет к полной системе, потому что теорема Гёделя также применима к F ', и, следовательно, F' также не может быть полным. В этом случае G F действительно является теоремой из F ', потому что это аксиома. Поскольку G F утверждает только то, что оно не доказуемо в F, его доказуемость внутри F ' не противоречит. Однако, поскольку теорема о неполноте применима к F ', будет новое утверждение Гёделя G F' для F ', показывающее, что F' также является неполным. G F ' будет отличаться от G F в этом G F' будет относиться к Р», а не  F.

Синтаксическая форма предложения Гёделя

Предложение Гёделя косвенно относится к самому себе. Приговор гласит, что, когда конкретная последовательность шагов используется для построения другого предложения, построивший предложение не будет доказуемо в F. Однако последовательность шагов такова, что построенное предложение оказывается G F сам по себе. Таким образом, гёделевское предложение G F косвенно заявляет о своей собственной недоказуемости в пределах F ( Smith 2007, p. 135). harv error: no target: CITEREFSmitdiv class="ht"007 ( help )

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

Таким образом, хотя предложение Гёделя косвенно относится к предложениям системы F, когда оно читается как арифметическое утверждение, предложение Гёделя напрямую относится только к натуральным числам. Он утверждает, что ни одно натуральное число не обладает определенным свойством, причем это свойство задается примитивным рекурсивным отношением ( Smith 2007, p. 141). Таким образом, предложение Гёделя может быть написано на языке арифметики с простой синтаксической формой. В частности, он может быть выражен в виде формулы в языке арифметики, состоящей из ряда ведущих универсальных кванторов с последующими бескванторным телом (эти формулы находятся на уровне от арифметической иерархии ). С помощью теоремы MRDP предложение Гёделя можно переписать как утверждение, что конкретный многочлен от многих переменных с целыми коэффициентами никогда не принимает нулевое значение, когда его переменные подставляются целыми числами ( Franzén 2005, p. 71). harv error: no target: CITEREFSmitdiv class="ht"007 ( help ) Π 1 0 {\displaystyle \Pi _{1}^{0}} harv error: no target: CITEREFFranzén2005 ( help )

Истина предложения Гёделя

Первая неполноте теорема показывает, что Гедель предложение G F соответствующей формальной теории F недоказуемо в F. Поскольку, когда эта недоказуемость интерпретируется как утверждение об арифметике, это именно то, что утверждает предложение (косвенно), предложение Гёделя на самом деле истинно ( Smoryński 1977, p. 825 ; также см. Franzén 2005, pp. 28–33).. По этой причине предложение G F часто называют «истинным, но недоказуемым». ( Раатикайнен 2015). Однако, поскольку предложение Гёделя не может само по себе формально определять предполагаемую интерпретацию, истинность предложения G F может быть достигнута только посредством метаанализа извне системы. В общем, этот метаанализ может быть проведен в рамках слабой формальной системы, известной как примитивно-рекурсивная арифметика, которая доказывает импликацию Con ( F) → G F, где Con ( F) - каноническое предложение, утверждающее непротиворечивость F ( Smoryński 1977, с. 840, Кикучи и Танака, 1994, с. 403). harvnb error: no target: CITEREFSmoryński1977 ( help ) harvnb error: no target: CITEREFFranzén2005 ( help ) harv error: no target: CITEREFRaatikainen2015 ( help ) harvnb error: no target: CITEREFSmoryński1977 ( help ) harvnb error: no target: CITEREFKikuchiTanaka1994 ( help )

Хотя предложение Гёделя непротиворечивой теории истинно как утверждение о предполагаемой интерпретации арифметики, предложение Гёделя будет ложным в некоторых нестандартных моделях арифметики как следствие теоремы Гёделя о полноте ( Franzén 2005, p. 135). Эта теорема показывает, что, когда предложение не зависит от теории, в теории будут модели, в которых предложение истинно, и модели, в которых предложение ложно. Как описано ранее, предложение Гёделя системы F является арифметическим утверждением, которое утверждает, что не существует числа с определенным свойством. Теорема о неполноте показывает, что это утверждение не будет зависеть от системы F, а истинность предложения Гёделя следует из того факта, что ни одно стандартное натуральное число не обладает указанным свойством. Любая модель, в которой предложение Гёделя ложно, должна содержать некоторый элемент, который удовлетворяет свойству в этой модели. Такая модель должна быть «нестандартной» - она ​​должна содержать элементы, не соответствующие ни одному стандартному натуральному числу ( Raatikainen 2015, Franzén 2005, p. 135). harv error: no target: CITEREFFranzén2005 ( help ) harvnb error: no target: CITEREFRaatikainen2015 ( help ) harvnb error: no target: CITEREFFranzén2005 ( help )

Отношения с парадоксом лжеца

Гедель конкретно цитирует парадокс Ричарда и лжец парадокс как семантических аналогов в его синтаксической результате неполноты в вводном разделе « О формально Неразрешимые предложений в Principia Mathematica и родственных систем I ». Лжец парадокс является предложение «Это предложение ложно.» Анализ предложения лжеца показывает, что оно не может быть истинным (поскольку тогда, как оно утверждает, оно ложно), и не может быть ложным (поскольку тогда оно истинно). Предложение Гёделя G для системы F делает такое же утверждение, что и предложение лжеца, но с заменой истины доказуемостью: G говорит: « G недоказуема в системе F ». Анализ истинности и доказуемости G является формализованной версией анализа истинности лживого предложения.

Невозможно заменить «недоказуемое» на «ложное» в предложении Гёделя, потому что предикат «Q - гёделевское число ложной формулы» не может быть представлен как формула арифметики. Этот результат, известный как теорема о неопределенности Тарского, был открыт независимо как Геделем, когда он работал над доказательством теоремы о неполноте, так и однофамильцем теоремы Альфредом Тарским.

Расширения первоначального результата Гёделя

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

Гёдель продемонстрировал неполноту системы Principia Mathematica, особой системы арифметики, но параллельная демонстрация может быть дана для любой эффективной системы определенной выразительности. Гёдель прокомментировал этот факт во введении к своей статье, но для конкретности ограничил доказательство одной системой. В современных формулировках теоремы принято формулировать условия эффективности и выразительности как гипотезы для теоремы о неполноте, так что она не ограничивается какой-либо конкретной формальной системой. Терминология, используемая для обозначения этих условий, еще не была разработана в 1931 году, когда Гедель опубликовал свои результаты.

Исходное утверждение Гёделя и доказательство теоремы о неполноте требуют предположения, что система не только непротиворечива, но и ω-непротиворечива. Система является ω-непротиворечивой, если она не ω-несовместима, и ω-несовместной, если существует такой предикат P, что для каждого конкретного натурального числа m система доказывает ~ P ( m), и, тем не менее, система также доказывает, что существует существует натуральное число n такое, что P ( n). То есть система говорит, что число со свойством P существует, но отрицает, что оно имеет какое-либо конкретное значение. Ω-непротиворечивость системы подразумевает ее непротиворечивость, но непротиворечивость не означает ω-непротиворечивость. Дж. Баркли Россер  ( 1936) усилил теорему о неполноте, найдя вариант доказательства ( трюк Россера ), который требует только согласованности системы, а не ω-согласованности. Это в основном представляет технический интерес, потому что все истинные формальные теории арифметики (теории, аксиомы которых являются истинными утверждениями о натуральных числах) являются ω-согласованными, и, таким образом, теорема Гёделя в том виде, в котором они сформулированы первоначально, применима к ним. Более сильная версия теоремы о неполноте, которая предполагает только непротиворечивость, а не ω-непротиворечивость, теперь широко известна как теорема Гёделя о неполноте и как теорема Гёделя – Россера.

Вторая теорема о неполноте

Для каждой формальной системы F, содержащей основные арифметические, можно канонически определить формулу Cons ( F), экспрессирующие последовательность F. Эта формула выражает свойство, что «не существует натурального числа, кодирующего формальный вывод в системе F, вывод которого является синтаксическим противоречием». Синтаксическое противоречие часто принимается равным «0 = 1», и в этом случае Cons ( F) утверждает, что «не существует натурального числа, которое кодирует вывод« 0 = 1 »из аксиом F ».

Вторая теорема Гёделя о неполноте показывает, что при общих предположениях этой канонической постановка консистенции Cons ( F) не будет доказуема в F. Теорема впервые появилась как «Теорема XI» в статье Гёделя 1931 года « О формально неразрешимых предложениях в Principia Mathematica и родственных системах I ». В следующем утверждении термин «формализованная система» также включает предположение, что F эффективно аксиоматизирована.

Вторая теорема о неполноте: «Предположим, что F - непротиворечивая формализованная система, содержащая элементарную арифметику. Тогда ». ( Раатикайнен 2015) F Cons ( F ) {\displaystyle F\not \vdash {\text{Cons}}(F)} harv error: no target: CITEREFRaatikainen2015 ( help )

Эта теорема сильнее первой теоремы о неполноте, потому что утверждение, построенное в первой теореме о неполноте, не выражает напрямую непротиворечивости системы. Доказательство второй теоремы о неполноте получается путем формализации доказательства первой теоремы о неполноте в системе F сам по себе.

Выражение последовательности

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

Другие формализации утверждения о непротиворечивости F могут быть неэквивалентны в F, а некоторые даже могут быть доказуемы. Например, арифметика Пеано первого порядка (PA) может доказать, что «наибольшее непротиворечивое подмножество PA» непротиворечиво. Но поскольку PA согласован, наибольшее согласованное подмножество PA - это просто PA, так что в этом смысле PA «доказывает, что оно согласовано». Чего PA не доказывает, так это того, что наибольшее согласованное подмножество PA фактически является всей PA. (Термин «наибольшее согласованное подмножество PA» здесь означает наибольший согласованный начальный сегмент аксиом PA при некотором конкретном эффективном перечислении.)

Условия Гильберта – Бернейса.

Стандартное доказательство второй теоремы о неполноте предполагает, что предикат доказуемости Prov A ( P) удовлетворяет условиям доказуемости Гильберта – Бернейса. Пусть # ( P) представляет собой гёделевское число формулы P, условия доказуемости говорят:

  1. Если F доказывает P, то F доказывает Prov A (# ( P)).
  2. F доказывает 1.; то есть F доказывает Prov A (# ( P)) → Prov A (# (Prov A (# (P)))).
  3. F доказывает Prov A (# ( P → Q)) ∧ Prov A (# ( P)) → Prov A (# ( Q)) (аналог modus ponens ).

Существуют системы, такие как арифметика Робинсона, которые достаточно сильны, чтобы удовлетворять условиям первой теоремы о неполноте, но не доказывают условия Гильберта – Бернейса. Однако арифметика Пеано достаточно сильна, чтобы проверить эти условия, как и все теории, более сильные, чем арифметика Пеано.

Последствия для доказательств непротиворечивости

Вторая теорема Гёделя о неполноте также означает, что система F 1, удовлетворяющая техническим условиям, изложенным выше, не может доказать непротиворечивость любой системы F 2, которая доказывает непротиворечивость F 1. Это потому, что такая система F 1 может доказать, что если F 2 доказывает согласованность F 1, то F 1 фактически согласована. Поскольку утверждение, что F 1 непротиворечиво, имеет форму «для всех чисел n, n обладает разрешимым свойством не быть кодом для доказательства противоречия в F 1 ». Если бы F 1 был на самом деле несовместимым, то F 2 доказал бы для некоторого n, что n является кодом противоречия в F 1. Но если бы F 2 также доказал, что F 1 непротиворечиво (то есть, что такого n нет), то оно само было бы несовместимым. Это рассуждение можно формализовать в F 1, чтобы показать, что если F 2 непротиворечиво, то F 1 непротиворечиво. Поскольку по второй теореме о неполноте F 1 не доказывает свою непротиворечивость, она также не может доказать непротиворечивость F 2.

Это следствие второй теоремы о неполноте показывает, что нет никакой надежды на доказательство, например, непротиворечивости арифметики Пеано с использованием любых конечных средств, которые могут быть формализованы в системе, непротиворечивость которой доказуема в арифметике Пеано (PA). Например, система примитивно-рекурсивной арифметики (PRA), которая широко принята как точная формализация финитистической математики, доказуемо согласована в PA. Таким образом, PRA не может доказать непротиворечивость PA. Этот факт обычно подразумевает, что программа Гильберта, которая направлена ​​на оправдание использования «идеальных» (инфинитистических) математических принципов в доказательствах «реальных» (финитистских) математических утверждений, давая финитистическое доказательство того, что идеальные принципы непротиворечивы, не могут быть выполнены ( Franzén 2005, p. 106). harv error: no target: CITEREFFranzén2005 ( help )

Следствие также указывает на эпистемологическую значимость второй теоремы о неполноте. На самом деле это не дало бы никакой интересной информации, если бы система F доказала свою непротиворечивость. Это потому, что противоречивые теории доказывают все, в том числе их непротиворечивость. Таким образом, доказательство непротиворечивости F в F не даст нам подсказки относительно того, действительно ли F непротиворечиво; никакие сомнения в непротиворечивости F не разрешатся с помощью такого доказательства непротиворечивости. Интерес доказательства непротиворечивости заключается в возможности доказать непротиворечивость системы F в некоторой системе F», которая в некотором смысле менее сомнительным, чем F сам, например, слабее, чем F. Для многих естественных теорий F и F ', таких как F = теория множеств Цермело – Френкеля и F' = примитивно рекурсивная арифметика, непротиворечивость F ' доказуема в F, и, таким образом, F' не может доказать непротиворечивость F с помощью приведенного выше Следствие второй теоремы о неполноте.

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

Примеры неразрешимых утверждений
См. Также: Список операторов, независимых от ZFC

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

Из-за двух значений слова «неразрешимый» термин « независимый» иногда используется вместо «неразрешимый» в смысле «ни доказать, ни опровергнуть».

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

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

В 1973 году Сахарон Шелах показал, что проблема Уайтхеда в теории групп неразрешима в первом смысле этого слова в стандартной теории множеств.

Грегори Чейтин произвел неразрешимые утверждения в алгоритмической теории информации и доказал еще одну теорему о неполноте в этом контексте. Теорема Чейтина о неполноте утверждает, что для любой системы, которая может представить достаточно арифметических операций, существует верхняя граница c, такая, что нельзя доказать в этой системе какое-либо конкретное число, имеющее колмогоровскую сложность больше, чем c. В то время как теорема Гёделя связана с парадоксом лжеца, результат Чайтина связан с парадоксом Берри.

Неразрешимые утверждения, доказуемые в более крупных системах

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

В 1977 году Пэрис и Харрингтон доказали, что принцип Париса – Харрингтона, версия бесконечной теоремы Рамсея, неразрешим в арифметике Пеано (первого порядка), но может быть доказан в более сильной системе арифметики второго порядка. Кирби и Пэрис позже показали, что теорема Гудстейна, утверждение о последовательностях натуральных чисел, несколько более простое, чем принцип Пэрис – Харрингтона, также неразрешима в арифметике Пеано.

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

Связь с вычислимостью
Смотрите также: Проблема остановки § теоремы Гёделя о неполноте

Теорема о неполноте тесно связана с несколькими результатами о неразрешимых множествах в теории рекурсии.

Стивен Коул Клини  ( 1943) представил доказательство теоремы Гёделя о неполноте, используя основные результаты теории вычислимости. Один из таких результатов показывает, что проблема остановки неразрешима: нет компьютерной программы, которая могла бы правильно определить, учитывая любую программу P в качестве входных данных, останавливается ли P в конечном итоге при запуске с конкретным заданным входом. Клини показал, что существование полной эффективной системы арифметики с определенными свойствами согласованности сделало бы проблему остановки разрешимой; противоречие. Этот метод доказательства также был представлен Шенфилдом (1967, стр. 132) ; Чарльзуорт (1980) ; и Хопкрофт и Ульман (1979). harvtxt error: no target: CITEREFShoenfield1967 ( help ) harvtxt error: no target: CITEREFCharlesworth1980 ( help ) harvtxt error: no target: CITEREFHopcroftUllman1979 ( help )

Franzén (2005, стр. 73) объясняет, как решение Матиясевича в к 10 - й проблеме Гильберта может быть использовано для получения доказательства теоремы Гёделя о неполноте первой. Матиясевич доказал, что не существует алгоритма, который по многомерному многочлену p (x 1, x 2,..., x k) с целыми коэффициентами определяет, существует ли целочисленное решение уравнения p = 0. Поскольку многочлены с целыми числами коэффициенты и сами целые числа напрямую выражаются на языке арифметики, если многомерное целочисленное полиномиальное уравнение p = 0 действительно имеет решение в целых числах, тогда любая достаточно сильная система арифметики T докажет это. Более того, если система T ω-согласована, то она никогда не докажет, что конкретное полиномиальное уравнение имеет решение, хотя на самом деле нет решения в целых числах. Таким образом, если T были полными и ω-последовательны, то можно было бы определить, имеет алгоритмический ли полиномиальное уравнение решения простого перечисления доказательств Т до тех пор, как « р не имеет решения» или « р не имеет решения» найден, в противоречие с теоремой Матиясевича. Отсюда следует, что T не может быть w -согласованным и полным. Более того, для каждой согласованной эффективно сгенерированной системы T можно эффективно сгенерировать многомерный многочлен p над целыми числами, такой что уравнение p = 0 не имеет решений над целыми числами, но отсутствие решений не может быть доказано в T ( Davis 2006, стр. 416 ; Джонс 1980). harvtxt error: no target: CITEREFFranzén2005 ( help ) harvnb error: no target: CITEREFDavis2006 ( help ) harvnb error: no target: CITEREFJones1980 ( help )

Сморински (1977, с. 842) показывает, как существование рекурсивно неотделимых множеств может быть использовано для доказательства первой теоремы о неполноте. Это доказательство часто расширяется, чтобы показать, что такие системы, как арифметика Пеано, по существу неразрешимы (см. Kleene 1967, p. 274). harvtxt error: no target: CITEREFSmorynski1977 ( help ) harvnb error: no target: CITEREFKleene1967 ( help )

Теорема Чайтина о неполноте дает другой метод создания независимых предложений, основанный на сложности Колмогорова. Подобно упомянутому выше доказательству Клини, теорема Чейтина применима только к теориям с дополнительным свойством, что все их аксиомы верны в стандартной модели натуральных чисел. Теорема Гёделя о неполноте отличается своей применимостью к непротиворечивым теориям, которые, тем не менее, включают утверждения, ложные в стандартной модели; эти теории известны как ω-несовместимые.

Схема доказательства первой теоремы
Основная статья: Набросок доказательства первой теоремы Гёделя о неполноте

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

  1. Утверждения в системе могут быть представлены натуральными числами (известными как числа Гёделя). Значение этого состоит в том, что свойства утверждений, такие как их истинность и ложность, будут эквивалентны определению того, обладают ли их гёделевские числа определенными свойствами, и что свойства утверждений, следовательно, можно продемонстрировать, исследуя их гёделевские числа. Эта часть завершается построением формулы, выражающей идею, что «утверждение S доказуемо в системе» (которое может быть применено к любому утверждению «S» в системе).
  2. В формальной системе можно построить число, утверждение сопоставления которого при интерпретации является самореферентным и, по сути, говорит, что оно (то есть само утверждение) недоказуемо. Это делается с помощью техники, называемой « диагонализацией » (так называемой из-за того, что она возникла как диагональный аргумент Кантора ).
  3. В рамках формальной системы это утверждение позволяет продемонстрировать, что оно не может быть ни доказуемо, ни опровергнуто в системе, и поэтому система на самом деле не может быть ω-согласованной. Следовательно, первоначальное предположение о том, что предлагаемая система удовлетворяет критериям, неверно.

Арифметизация синтаксиса

Основная проблема при конкретизации описанного выше доказательства заключается в том, что сначала кажется, что для построения утверждения p, эквивалентного « p не может быть доказано», p каким-то образом должен содержать ссылку на p, что может легко привести к бесконечный регресс. Гениальный метод Гёделя состоит в том, чтобы показать, что утверждения могут быть сопоставлены с числами (часто называемой арифметизацией синтаксиса ) таким образом, что «доказательство утверждения» может быть заменено «проверкой наличия у числа заданного свойства». Это позволяет строить самореференциальную формулу таким образом, чтобы избежать бесконечного регресса определений. Эту же технику позже использовал Алан Тьюринг в своей работе над проблемой Entscheidungsproblem.

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

  • Слово HELLOпредставлено 72-69-76-76-79 в десятичном формате ASCII, то есть числом 7269767679.
  • Логический оператор x=y =gt; y=xпредставлен 120-061-121-032-061-062-032-121-061-120 с использованием восьмеричного ASCII, то есть числом 120061121032061062032121061120.

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

Построение утверждения о «доказуемости»

Показав, что в принципе система может косвенно делать утверждения о доказуемости, анализируя свойства этих чисел, представляющих утверждения, теперь можно показать, как создать утверждение, которое действительно делает это.

Формула F ( x), содержащая ровно одну свободную переменную x, называется формой оператора или знаком класса. Как только x заменяется определенным числом, форма утверждения превращается в добросовестное утверждение, и тогда оно либо доказуемо в системе, либо нет. Для некоторых формул можно показать, что для любого натурального числа п, истинно тогда и только тогда, когда оно может быть доказано (точное требование первоначального доказательства слабее, но для доказательства эскиз этого будет достаточно). В частности, это верно для каждой конкретной арифметической операции между конечным числом натуральных чисел, например «2  ×  3 = 6». F ( n ) {\displaystyle F(n)}

Формы утверждений сами по себе не являются утверждениями и поэтому не могут быть доказаны или опровергнуты. Но каждой форме утверждения F ( x) можно присвоить гёделевский номер, обозначенный G ( F). Выбор свободной переменной, используемой в форме F ( x), не имеет отношения к присвоению числа Гёделя G ( F).

Само понятие доказуемости также может быть закодировано числами Гёделя следующим образом: поскольку доказательство - это список утверждений, которые подчиняются определенным правилам, можно определить число Гёделя доказательства. Теперь для каждого утверждения p можно спросить, является ли число x гёделевским числом его доказательства. Связь между гёделевским числом p и x, потенциальным гёделевским числом его доказательства, является арифметическим соотношением между двумя числами. Следовательно, существует форма утверждения Bew ( y), которая использует это арифметическое отношение для утверждения, что существует гёделевское число доказательства y:

Bew ( y) = ∃ x ( y - гёделевское число формулы, а x - гёделевское число доказательства формулы, закодированной с помощью y).

Название Bew - сокращение от beweisbar, немецкого слова «доказуемое»; это имя первоначально использовалось Гёделем для обозначения только что описанной формулы доказуемости. Обратите внимание, что «Bew ( y)» - это просто сокращение, которое представляет конкретную очень длинную формулу на исходном языке T ; сама строка "Bew" не является частью этого языка.

Важной особенностью формулы Bew ( y) является то, что если утверждение p доказуемо в системе, то Bew ( G ( p)) также доказуемо. Это потому, что любое доказательство p будет иметь соответствующее число Гёделя, существование которого заставляет Bew ( G ( p)) быть удовлетворенным.

Диагонализация

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

p ↔ F ( G ( p)).

Полагая F отрицанием Bew ( x), получаем теорему

p ↔ ~ Бью ( G ( p))

а р, определяемый этим, грубо заявляет, что его собственное число Гёделя является числом Гёделя недоказуемой формулы.

Утверждение p не буквально равно ~ Bew ( G ( p)); скорее, p утверждает, что если выполняется определенное вычисление, результирующее число Гёделя будет таким же, как и в недоказуемом утверждении. Но когда это вычисление выполняется, результирующее число Гёделя оказывается гёделевским числом самого p. Это похоже на следующее предложение на английском языке:

", если перед самим собой указано в кавычках, недоказуемо.", если перед самим собой указано в кавычках, недоказуемо.

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

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

Если бы p было доказуемо, то Bew ( G ( p)) было бы доказуемо, как утверждалось выше. Но p утверждает отрицание Bew ( G ( p)). Таким образом, система будет непоследовательной, доказывая как утверждение, так и его отрицание. Это противоречие показывает, что p не может быть доказуемо.

Если бы отрицание p было доказуемо, то Bew ( G ( p)) было бы доказуемо (потому что p был построен так, чтобы быть эквивалентным отрицанию Bew ( G ( p))). Тем не менее, для каждого конкретного числа х, й не может быть номером Гедель доказательства р, так как р не выводим (из предыдущего абзаца). Таким образом, с одной стороны, система доказывает, что существует число с определенным свойством (что это число Гёделя в доказательстве p), но с другой стороны, для каждого конкретного числа x мы можем доказать, что оно не имеет этого имущество. Это невозможно в ω-согласованной системе. Таким образом, отрицание p недоказуемо.

Таким образом, утверждение p неразрешимо в нашей аксиоматической системе: оно не может быть ни доказано, ни опровергнуто внутри системы.

Фактически, чтобы показать, что p недоказуемо, требуется только предположение, что система непротиворечива. Требуется более сильное предположение о ω-согласованности, чтобы показать, что отрицание p недоказуемо. Таким образом, если p построен для конкретной системы:

  • Если система ω-согласована, она не может доказать ни p, ни свое отрицание, поэтому p неразрешима.
  • Если система непротиворечива, она может иметь такую ​​же ситуацию или может доказать отрицание p. В последнем случае у нас есть утверждение («не p »), которое ложно, но доказуемо, и система не является ω-согласованной.

Если кто-то пытается «добавить недостающие аксиомы», чтобы избежать неполноты системы, тогда он должен добавить либо p, либо «не p » в качестве аксиом. Но затем определение «быть числом Гёделя доказательства» утверждения меняется. это означает, что формула Bew ( x) теперь другая. Таким образом, когда мы применяем диагональную лемму к этому новому Bew, мы получаем новое утверждение p, отличное от предыдущего, которое будет неразрешимым в новой системе, если оно ω-согласовано.

Доказательство парадокса Берри

Джордж Булос  ( 1989) набрасывает альтернативное доказательство первой теоремы о неполноте, которое использует парадокс Берри, а не парадокс лжеца, для построения истинной, но недоказуемой формулы. Подобный метод доказательства независимо открыл Саул Крипке ( Boolos 1998, стр. 383). Доказательство проводится Boolos путем построения для любого вычислимо перечислимого множества S истинных предложений арифметики, другое предложение, которое является истинным, но не содержатся в S. Это дает первую теорему о неполноте как следствие. Согласно Булосу, это доказательство интересно тем, что оно предоставляет «причину другого рода» для неполноты эффективных, непротиворечивых теорий арифметики ( Boolos 1998, p. 388). harv error: no target: CITEREFBoolos1998 ( help ) harv error: no target: CITEREFBoolos1998 ( help )

Подтвержденные компьютером доказательства

См. Также: Автоматическое доказательство теорем

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

Проверенные компьютером доказательства версий первой теоремы о неполноте были объявлены Натараджаном Шанкаром в 1986 году с использованием Nqthm ( Шанкар, 1994), Расселом О'Коннором в 2003 году с использованием Coq ( О'Коннор, 2005) и Джоном Харрисоном в 2009 году с использованием HOL Light ( Харрисон 2009). Подтвержденное компьютером доказательство обеих теорем о неполноте было объявлено Лоуренсом Полсоном в 2013 году с использованием Изабель ( Paulson 2014). harv error: no target: CITEREFShankar1994 ( help ) harv error: no target: CITEREFO'Connor2005 ( help ) harv error: no target: CITEREFHarrison2009 ( help ) harv error: no target: CITEREFPaulson2014 ( help )

Схема доказательства второй теоремы
См. Также: Условия доказуемости Гильберта – Бернейса.

Основная трудность в доказательстве второй теоремы о неполноте состоит в том, чтобы показать, что различные факты о доказуемости, используемые в доказательстве первой теоремы о неполноте, могут быть формализованы в системе S с использованием формального предиката доказуемости. Как только это будет сделано, вторая теорема о неполноте следует формализуя все доказательство первой теоремы о неполноте в системе S себя.

Пусть р стенд для неразрешимого предложения, построенной выше, и предположим, для целей получения противоречия, что непротиворечивость системы S может быть доказана внутри системы S себя. Это эквивалентно доказательству утверждения «Система S непротиворечива». Теперь рассмотрим утверждение c, где c = «Если система S непротиворечива, то p недоказуемо». Доказательство предложения с может быть формализована в рамках системы S, и, следовательно, утверждение с « р не доказуемо», (или тождественно, «не Р ( р)») может быть доказано в системе S.

Заметим, что если мы можем доказать, что система S непротиворечива (т. Е. Утверждение в гипотезе c), то мы доказали, что p недоказуемо. Но это противоречие, поскольку согласно 1-й теореме о неполноте это предложение (т. Е. То, что подразумевается в предложении c, «« p »недоказуемо») является тем, что мы конструируем как недоказуемое. Обратите внимание, что именно поэтому мы требуем формализации первую Неполноты теорему в S: доказать теорему 2 - й Неполноты, мы получаем противоречие с 1 неполноте теоремы, которые могут сделать только показав, что теорема верна в S. Таким образом, мы не можем доказать, что система S непротиворечива. И следует утверждение 2-й теоремы о неполноте.

Обсуждение и последствия

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

Последствия для логицизма и второй проблемы Гильберта

Иногда считается, что теорема о неполноте имеет серьезные последствия для программы логицизма, предложенной Готтлобом Фреге и Бертраном Расселом, целью которой является определение натуральных чисел в терминах логики ( Hellman 1981, p. 451–468). Боб Хейл и Криспин Райт утверждают, что это не проблема логицизма, потому что теоремы о неполноте в равной степени применимы к логике первого порядка, как и к арифметике. Они утверждают, что с этой проблемой сталкиваются только те, кто считает, что натуральные числа следует определять в терминах логики первого порядка. harv error: no target: CITEREFHellman1981 ( help )

Многие Логики считают, что неполнота теорема Гёделя нанесла смертельный удар Давид Гильберта «s второй задаче, которые просили финитное доказательство непротиворечивости для математики. В частности, вторая теорема о неполноте часто рассматривается как решение, делающее проблему невозможной. Однако не все математики согласны с этим анализом, и статус второй проблемы Гильберта еще не решен (см. « Современные точки зрения на статус проблемы »).

Умы и машины

Основная статья: Механизм (философия) § Гёделевские аргументы

Авторы, включая философа Дж. Р. Лукаса и физика Роджера Пенроуза, обсуждали, что, во всяком случае, подразумевают теоремы Гёделя о неполноте относительно человеческого интеллекта. Большая часть споров сосредоточена на том, эквивалентен ли человеческий разум машине Тьюринга или, согласно тезису Чёрча-Тьюринга, любой конечной машине вообще. Если это так и если машина непротиворечива, то к ней применимы теоремы Гёделя о неполноте.

Хилари Патнэм  ( 1960) предположила, что, хотя теоремы Гёделя не могут быть применены к людям, поскольку они допускают ошибки и, следовательно, непоследовательны, их можно применить к человеческому факультету естественных наук или математики в целом. Если предположить, что она непротиворечива, либо ее непротиворечивость нельзя доказать, либо она не может быть представлена ​​машиной Тьюринга.

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

Дуглас Хофштадтер в своих книгах « Гедель, Эшер, Бах и« Я странная петля » цитирует теоремы Геделя как пример того, что он называет странной петлей, иерархической самореферентной структурой, существующей в аксиоматической формальной системе. Он утверждает, что это такая же структура, которая дает начало сознанию, чувству «я» в человеческом разуме. В то время как самоотнесение в теореме Гёделя происходит от предложения Гёделя, утверждающего его собственную недоказуемость в рамках формальной системы Principia Mathematica, самореференция в человеческом разуме происходит из того, как мозг абстрагирует и классифицирует стимулы в «символы», или группы нейронов, которые реагируют на концепции, в том, что фактически также является формальной системой, что в конечном итоге дает начало символам, моделирующим концепцию самой сущности, осуществляющей восприятие. Хофштадтер утверждает, что странная петля в достаточно сложной формальной системе может привести к «нисходящей» или «перевернутой» причинно-следственной связи, ситуации, в которой нормальная причинно-следственная иерархия переворачивается с ног на голову. Короче говоря, в случае теоремы Гёделя это проявляется в следующем:

«Просто зная значение формулы, можно сделать вывод о ее истинности или ложности, не прилагая никаких усилий, чтобы вывести ее старомодным способом, который требует методического тащения« вверх »от аксиом. Это не просто странно, это поразительно.. Обычно нельзя просто смотреть на то, что говорит математическая гипотеза, и просто апеллировать к содержанию этого утверждения, чтобы сделать вывод, истинно это утверждение или ложно ». ( Я - странная петля.)

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

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

Паранепротиворечивая логика

Хотя теоремы Гёделя обычно изучаются в контексте классической логики, они также играют роль в изучении паранепротиворечивой логики и изначально противоречивых утверждений ( dialetheia ). Грэм Прист  ( 1984, 2006) утверждает, что замена понятия формального доказательства в теореме Гёделя обычным понятием неформального доказательства может использоваться, чтобы показать, что наивная математика непоследовательна, и использует это как доказательство диалетеизма. Причина этого несоответствия - включение предиката истинности для системы в язык системы ( Priest 2006, p. 47). Стюарт Шапиро  ( 2002) дает более неоднозначную оценку применения теорем Гёделя к диалетеизму. harv error: no target: CITEREFPriest2006 ( help )

Апелляции к теоремам о неполноте в других областях

Иногда к теоремам о неполноте прибегают и проводят аналогии в поддержку аргументов, выходящих за рамки математики и логики. Некоторые авторы отрицательно прокомментировали такие расширения и интерпретации, в том числе Торкель Франзен (2005); Пану Раатикайнен (2005 г.) ; Алан Сокал и Жан Брикмон  ( 1999); и Офелия Бенсон и Джереми Стэнгрум  ( 2006). Bricmont amp; Stangroom (2006, стр. 10), например, цитируют комментарии Ребекки Гольдштейн о несоответствии между общепризнанным платонизмом Гёделя и антиреалистическим использованием, которым иногда подвергаются его идеи. Сокаль и Брикмон (1999, с. 187) критикуют обращение Режиса Дебре к теореме в контексте социологии; Дебрей защитил это использование как метафорическое (там же). harvtxt error: no target: CITEREFRaatikainen2005 ( help ) harvtxt error: no target: CITEREFBricmontStangroom2006 ( help ) harvtxt error: no target: CITEREFSokalBricmont1999 ( help )

История

После того, как Гёдель опубликовал свое доказательство теоремы о полноте в качестве докторской диссертации в 1929 году, он обратился ко второй проблеме своей абилитации. Его первоначальной целью было получить положительное решение второй проблемы Гильберта ( Dawson 1997, p. 63). В то время теории натуральных и действительных чисел, подобные арифметике второго порядка, были известны как «анализ», в то время как теории одних только натуральных чисел были известны как «арифметика».

Гёдель был не единственным, кто работал над проблемой согласованности. Аккерман опубликовал для анализа некорректное доказательство непротиворечивости в 1925 году, в котором он попытался использовать метод ε-подстановки, первоначально разработанный Гильбертом. Позже в том же году фон Нейман смог исправить доказательство для системы арифметики без каких-либо аксиом индукции. К 1928 году Аккерман сообщил Бернейсу модифицированное доказательство; это модифицированное доказательство привело Гильберта к заявлению в 1929 г. о своей убежденности в том, что непротиворечивость арифметики была продемонстрирована и что вскоре последует доказательство непротиворечивости анализа. После того, как публикация теорем о неполноте показала, что модифицированное доказательство Аккермана должно быть ошибочным, фон Нейман привел конкретный пример, показывающий, что его основная техника была несостоятельной ( Zach 2007, p. 418; Zach 2003, p. 33).

В ходе своего исследования Гёдель обнаружил, что, хотя предложение, которое утверждает свою собственную ложность, приводит к парадоксу, предложение, которое утверждает свою собственную недоказуемость, этого не делает. В частности, Геделю был известен результат, который теперь называется теоремой Тарского о неопределенности, хотя он никогда его не публиковал. Гедель объявил свою первую теорему о неполноте Карнапу, Фейгелю и Вайсманну 26 августа 1930 года; все четверо посетят Вторую конференцию по эпистемологии точных наук, ключевую конференцию в Кенигсберге на следующей неделе.

Объявление

Кенигсбергская конференция 1930 года была совместным заседанием трех академических обществ, на котором присутствовали многие ведущие логики того времени. Карнап, Гейтинг и фон Нейман выступили с часовыми речами о математической философии логицизма, интуиционизма и формализма соответственно ( Dawson 1996, p. 69). Конференция также включала пенсионный адрес Гильберта, поскольку он покидал свою должность в Геттингенском университете. Гильберт использовал эту речь, чтобы доказать свою веру в то, что все математические проблемы могут быть решены. Он закончил свое выступление словами:

Для математика нет Ignorabimus, и, на мой взгляд, совсем нет для естествознания.... Истинная причина, по которой [никому] не удалось найти неразрешимую проблему, на мой взгляд, заключается в том, что не существует неразрешимой проблемы. В отличие от глупых Игнорабимов, наше кредо утверждает: мы должны знать. Мы узнаем!

Эта речь быстро стала известна как краткое изложение убеждений Гильберта в математике (ее последние шесть слов, « Wir müssen wissen. Wir werden wissen! », Были использованы в качестве эпитафии Гильберта в 1943 году). Хотя Гедель, вероятно, присутствовал на выступлении Гильберта, они никогда не встречались лицом к лицу ( Dawson 1996, p. 72).

Гедель объявил о своей первой теореме о неполноте на заседании круглого стола в третий день конференции. Объявление привлекло мало внимания, кроме сообщения фон Неймана, который отвел Геделя в сторону для разговора. Позже в том же году, работая независимо, зная первую теорему о неполноте, фон Нейман получил доказательство второй теоремы о неполноте, о котором он объявил Гёделю в письме от 20 ноября 1930 г. ( Dawson 1996, p. 70). Гёдель независимо получил вторую теорему о неполноте и включил ее в свою представленную рукопись, которая была получена Monatshefte für Mathematik 17 ноября 1930 года.

Статья Гёделя была опубликована в Monatshefte в 1931 году под заголовком «Uber form unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I» (« О формально неразрешимых предложениях в Principia Mathematica и родственных системах I »). Как следует из названия, Гёдель первоначально планировал опубликовать вторую часть статьи в следующем томе Monatshefte ; быстрое принятие первой статьи было одной из причин, по которой он изменил свои планы ( van Heijenoort 1967, стр. 328, сноска 68a). harv error: no target: CITEREFvan_Heijenoort1967 ( help )

Обобщение и принятие

Гедель прочитал серию лекций по своим теоремам в Принстоне в 1933–1934 годах для аудитории, в которую входили Черч, Клини и Россер. К этому времени Гёдель понял, что ключевое свойство, необходимое для его теорем, состоит в том, что система должна быть эффективной (в то время использовался термин «общерекурсивная»). Россер доказал в 1936 году, что гипотеза ω-согласованности, которая была неотъемлемой частью первоначального доказательства Гёделя, может быть заменена простой согласованностью, если предложение Гёделя было изменено соответствующим образом. Эти разработки оставили теоремы о неполноте по существу в их современной форме.

Генцен опубликовал свое доказательство непротиворечивости арифметики первого порядка в 1936 году. Гильберт принял это доказательство как «конечное», хотя (как уже показала теорема Гёделя) его нельзя формализовать в рамках системы арифметики, которая доказывается непротиворечивостью.

Влияние теорем о неполноте на программу Гильберта было быстро осознано. Бернейс включил полное доказательство теорем о неполноте во второй том Grundlagen der Mathematik ( 1939), наряду с дополнительными результатами Аккермана по методу ε-подстановки и доказательством непротиворечивости арифметики Генценом. Это было первое полностью опубликованное доказательство второй теоремы о неполноте.

Критика

Финслер

Пол Финслер  ( 1926) использовал версию парадокса Ричарда, чтобы построить выражение, которое было ложным, но недоказуемым в определенной, неформальной структуре, которую он разработал. Гёдель не знал об этой статье, когда доказывал теоремы о неполноте (Сборник работ, том IV, стр. 9). Финслер написал Гёделю в 1931 году, чтобы проинформировать его об этой статье, которая, по мнению Финслера, имела приоритет для теоремы о неполноте. Методы Финслера не основывались на формализованной доказуемости и имели лишь внешнее сходство с работами Гёделя ( van Heijenoort 1967, p. 328). Гёдель прочитал статью, но обнаружил в ней глубокие изъяны, а его ответ Финслеру выразил обеспокоенность по поводу отсутствия формализации ( Доусон, стр. 89). Финслер продолжал отстаивать свою философию математики, которая избегала формализации, до конца своей карьеры. harv error: no target: CITEREFvan_Heijenoort1967 ( help ) harvnb error: no target: CITEREFDawson ( help )

Цермело

В сентябре 1931 года Эрнст Цермело написал Гёделю, чтобы объявить о том, что он назвал «существенным пробелом» в аргументации Гёделя ( Dawson, p. 76). В октябре Гедель ответил 10-страничным письмом ( Dawson, p. 76, Grattan-Guinness, pp. 512–513), где он указал, что Цермело ошибочно предположил, что понятие истины в системе определимо в этой системе. (что в общем случае неверно по теореме Тарского о неопределенности ). Но Цермело не смягчился и опубликовал свою критику в печати с «довольно резким абзацем о своем молодом конкуренте» ( Grattan-Guinness, стр. 513). Гедель решил, что дальнейшее обсуждение этого вопроса бессмысленно, и Карнап согласился ( Доусон, стр. 77). Большая часть последующей работы Цермело была связана с логикой, более сильной, чем логика первого порядка, с помощью которой он надеялся показать как последовательность, так и категоричность математических теорий. harvnb error: no target: CITEREFDawson ( help ) harvnb error: no target: CITEREFDawson ( help ) harvnb error: no target: CITEREFGrattan-Guinness ( help ) harvnb error: no target: CITEREFGrattan-Guinness ( help ) harvnb error: no target: CITEREFDawson ( help )

Витгенштейн

Людвиг Витгенштейн написал несколько отрывков о теоремах о неполноте, которые были опубликованы посмертно в его « Замечаниях об основах математики» 1953 года, в частности, в одном разделе, который иногда называют «пресловутым параграфом», где он, кажется, путает понятия «истинный» и «доказуемый». Система Рассела. Гёдель был членом Венского кружка в тот период, когда в его мышлении доминировали ранняя идеальная языковая философия Витгенштейна и Tractatus Logico-Philosophicus. Были некоторые разногласия по поводу того, неправильно ли Витгенштейн понял теорему о неполноте или просто выразился нечетко. Писания в Nachlass Гёделя выражают уверенность в том, что Витгенштейн неверно истолковал свои идеи.

Многие комментаторы считали Витгенштейна неверным пониманием Гёделя ( Rodych 2003), хотя Джульет Флойд и Хилари Патнэм  ( 2000), а также Грэм Прист  ( 2004) предоставили текстовые чтения, утверждая, что большинство комментариев неправильно понимают Витгенштейна. После освобождения Бернейс, Даммет и Крайзель написали отдельные отзывы о замечаниях Витгенштейна, и все они были крайне негативными ( Berto 2009, p. 208). Единодушие в этой критике привело к тому, что замечания Витгенштейна о теоремах о неполноте мало повлияли на логическое сообщество. В 1972 году Гёдель заявил: «Витгенштейн сошёл с ума? Серьёзно ли он? Он намеренно произносит тривиально бессмысленные заявления» ( Wang 1996, p. 179), и написал Карлу Менгеру, что комментарии Витгенштейна демонстрируют неправильное понимание теорем о неполноте. пишу: harv error: no target: CITEREFRodycdiv class="ht"003 ( help ) harv error: no target: CITEREFBerto2009 ( help ) harv error: no target: CITEREFWang1996 ( help )

Из приведенных вами отрывков ясно, что Витгенштейн не понимал [первую теорему о неполноте] (или делал вид, что не понимает ее). Он интерпретировал это как своего рода логический парадокс, хотя на самом деле это прямо противоположное, а именно математическую теорему в рамках абсолютно бесспорной части математики (теории конечных чисел или комбинаторики). ( Ван, 1996, с. 179). harv error: no target: CITEREFWang1996 ( help )

С момента публикации « Нахласса» Витгенштейна в 2000 году в ряде философских статей была предпринята попытка оценить, была ли оправдана первоначальная критика замечаний Витгенштейна. Флойд и Патнэм (2000) утверждают, что Витгенштейн имел более полное понимание теоремы о неполноте, чем предполагалось ранее. Они особенно озабочены интерпретацией предложения Гёделя для ω-несовместимой системы как фактически говорящего «Я недоказуемо», поскольку в системе нет моделей, в которых предикат доказуемости соответствует фактической доказуемости. Родич (2003) утверждает, что их интерпретация Витгенштейна не является исторически оправданной, в то время как Бэйс (2004) выступает против философского анализа предиката доказуемости Флойда и Патнэма. Берто (2009) исследует взаимосвязь между написанием Витгенштейна и теориями паранепротиворечивой логики. harvtxt error: no target: CITEREFRodycdiv class="ht"003 ( help ) harvtxt error: no target: CITEREFBays2004 ( help ) harvtxt error: no target: CITEREFBerto2009 ( help )

Смотрите также
использованная литература

Цитаты

Статьи Гёделя

  • Курт Гёдель, 1931, "Über form unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme, I", Monatshefte für Mathematik und Physik, v. 38 n. 1. С. 173–198. DOI : 10.1007 / BF01700692
  • -, 1931, "Uber form unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme, I", в Соломоне Фефермане, изд., 1986. Курт Гёдель Собрание сочинений, Vol. Я. Oxford University Press, стр. 144–195. ISBN   978-0195147209. Оригинал на немецком языке с английским переводом, которому предшествует вступительное слово Стивена Коула Клини.
  • -, 1951, "Некоторые основные теоремы об основах математики и их следствия", в Соломоне Фефермане, изд., 1995. Курт Гёдель Собрание сочинений, Vol. III, Oxford University Press, стр. 304–323. ISBN   978-0195147223.

Прижизненные переводы работы Гёделя на английский язык

Ни одно из следующего не согласуется со всеми переведенными словами и типографикой. Типографика - серьезное дело, потому что Гёдель прямо хотел подчеркнуть «те метаматематические понятия, которые были определены в их обычном смысле раньше...». ( ван Хейеноорт 1967, стр. 595). Существуют три перевода. О первом Джон Доусон заявляет, что: «Перевод Мельцера был серьезно несовершенным и получил разрушительную рецензию в Journal of Symbolic Logic» ; Гедель также жаловался на комментарий Брейтуэйта ( Dawson 1997, p. 216). «К счастью, перевод Мельцера вскоре был заменен лучшим переводом, подготовленным Эллиоттом Мендельсоном для антологии Мартина Дэвиса« Неразрешимое »... он нашел перевод« не совсем так хорош », как он ожидал... [но из-за нехватки времени он ] согласился на его публикацию »(там же). (В сноске Доусон заявляет, что «он будет сожалеть о своем согласии, поскольку опубликованный том был испорчен неряшливой типографикой и многочисленными опечатками» (там же)). Доусон утверждает, что «Гёдель предпочел перевод, сделанный Жаном ван Хейенуртом» (там же). Для серьезного студента существует другая версия в виде набора лекционных заметок, записанных Стивеном Клини и Дж. Б. Россером «во время лекций, прочитанных Геделем в Институте перспективных исследований весной 1934 года» (см. Комментарий Дэвиса 1965, стр. 39 и начало на стр.41); эта версия называется «О неразрешимых предложениях формальных математических систем». В порядке публикации: harv error: no target: CITEREFvan_Heijenoort1967 ( help ) harvnb error: no target: CITEREFDavis1965 ( help )

  • Б. Мельцер (перевод) и Р. Б. Брейтуэйт (Введение), 1962. О формально неразрешимых предложениях Principia Mathematica и родственных систем, Dover Publications, New York (Dover edition 1992), ISBN   0-486-66980-7 (pbk.) содержит полезный перевод немецких сокращений Гёделя на стр. 33–34. Как отмечалось выше, типографика, перевод и комментарии вызывают подозрение. К сожалению, этот перевод со всем подозрительным содержанием перепечатал
  • Редактор Стивена Хокинга, 2005 г. Бог создал целые числа: математические открытия, изменившие историю, Running Press, Филадельфия, ISBN   0-7624-1922-9. Статья Гёделя начинается со стр. 1097, с комментарием Хокинга, начинающимся со стр. 1089.
  • Редактор Мартина Дэвиса, 1965. Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых задачах и вычислимых функциях, Raven Press, Нью-Йорк, без ISBN. Статья Гёделя начинается на странице 5, ей предшествует одна страница комментария.
  • Редактор Жана ван Хейеноорта, 1967, 3-е издание, 1967. От Фреге до Гёделя: Справочник по математической логике, 1879-1931, Издательство Гарвардского университета, Кембридж, Массачусетс, ISBN   0-674-32449-8 (pbk). Ван Хейеноорт сделал перевод. Он заявляет, что «профессор Гёдель одобрил перевод, который во многих местах соответствовал его пожеланиям». (стр. 595). Статья Гёделя начинается на стр. 595; Комментарий ван Хейенурта начинается на стр. 592.
  • Редактор Мартина Дэвиса, 1965, там же. «О неразрешимых предложениях формальных математических систем». Копия с исправлениями Гёделя и добавленными примечаниями Гёделя начинается на странице 41, ей предшествуют две страницы комментария Дэвиса. Пока Дэвис не включил это в свой том, эта лекция существовала только в виде мимеографических заметок.

Статьи других авторов

Книги о теоремах

Разные ссылки

внешние ссылки
Последняя правка сделана 2023-03-19 04:40:36
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте