Неполноты теорема Геделя две теоремы о математической логике , которые имеют отношение к пределам доказуемости в формальных теориях аксиоматических. Эти результаты, опубликованные Куртом Геделем в 1931 году, важны как для математической логики, так и для философии математики . Эти теоремы широко, но не повсеместно интерпретируются как показывающие, что программа Гильберта по нахождению полного и непротиворечивого набора аксиом для всей математики невозможна.
Первые государства теоремы о неполноте , что не соответствует системе из аксиом , чьи теоремы могут быть указаны с помощью эффективной процедуры (то есть, алгоритм ) не способна доказать все истины о арифметике натуральных чисел . Для любой такой непротиворечивой формальной системы всегда будут утверждения о натуральных числах, которые верны, но недоказуемы в рамках системы. Вторая теорема о неполноте, являющаяся расширением первой, показывает, что система не может продемонстрировать собственную непротиворечивость.
Используя диагональный аргумент , теоремы Гёделя о неполноте были первой из нескольких тесно связанных теорем об ограничениях формальных систем. За ними последовали теорема Тарского о неопределенности формальной истины, доказательство Черча неразрешимости Entscheidungsproblem Гильберта и теорема Тьюринга о том, что не существует алгоритма для решения проблемы остановки .
Формальные системы: полнота, последовательность и эффективная аксиоматизация
Теоремы о неполноте применимы к формальным системам , которые достаточно сложны, чтобы выразить основную арифметику натуральных чисел, и которые являются непротиворечивыми и эффективно аксиоматизированными, эти концепции подробно описаны ниже. В частности, в контексте логики первого порядка формальные системы также называют формальными теориями . В общем, формальная система - это дедуктивный аппарат, который состоит из определенного набора аксиом вместе с правилами символического манипулирования (или правилами вывода), которые позволяют выводить новые теоремы из аксиом. Одним из примеров такой системы является арифметика Пеано первого порядка , система, в которой все переменные предназначены для обозначения натуральных чисел. В других системах, таких как теория множеств , только некоторые предложения формальной системы выражают утверждения о натуральных числах. Теоремы о неполноте касаются формальной доказуемости в рамках этих систем, а не «доказуемости» в неформальном смысле.
Формальная система может обладать несколькими свойствами, включая полноту, непротиворечивость и наличие эффективной аксиоматизации. Теоремы о неполноте показывают, что системы, содержащие достаточный объем арифметики, не могут обладать всеми тремя из этих свойств.
Эффективная аксиоматизация
Формальная система называется эффективно аксиоматизированной (также называемой эффективно порожденной ), если ее набор теорем является рекурсивно перечислимым множеством (Franzén 2005, p. 112).
Это означает, что существует компьютерная программа, которая, в принципе, может перечислить все теоремы системы, не перечисляя никаких утверждений, не являющихся теоремами. Примеры эффективно генерируемых теорий включают арифметику Пеано и теорию множеств Цермело – Френкеля (ZFC).
Теория, известная как истинная арифметика, состоит из всех истинных утверждений о стандартных целых числах на языке арифметики Пеано. Эта теория последовательна, полна и содержит достаточный объем арифметики. Однако он не имеет рекурсивно перечислимого набора аксиом и, следовательно, не удовлетворяет условиям теорем о неполноте.
Полнота
Набор аксиом является ( синтаксически или отрицание -) полным, если для любого утверждения на языке аксиом это утверждение или его отрицание доказуемо с помощью аксиом (Smith 2007, p. 24). Это понятие относится к первой теореме Гёделя о неполноте. Его не следует путать с семантической полнотой, что означает, что набор аксиом доказывает все семантические тавтологии данного языка. В своей теореме о полноте Гёдель доказал, что логика первого порядка семантически полна. Но он не является синтаксически полным, поскольку есть предложения, выражаемые на языке логики первого порядка, которые нельзя ни доказать, ни опровергнуть только с помощью аксиом логики.
В простой логической системе было бы абсурдно ожидать синтаксической полноты. [ необходимая цитата ] Но в системе математики такие мыслители, как Гильберт, считали, что найти такую аксиоматизацию, которая позволила бы либо доказать, либо опровергнуть (доказывая ее отрицание), - это всего лишь вопрос времени, каждая математическая формула .
Формальная система может быть синтаксически неполной по замыслу, как это обычно бывает с логикой. Или он может быть неполным просто потому, что не все необходимые аксиомы были обнаружены или включены. Например, евклидова геометрия без постулата параллельности является неполной, потому что некоторые утверждения языка (такие как сам постулат параллельности) не могут быть доказаны с помощью остальных аксиом. Точно так же теория плотных линейных порядков не завершена, но дополняется дополнительной аксиомой, утверждающей, что в порядке нет конечных точек. Гипотеза континуума - это утверждение на языке ZFC , которое невозможно доказать в ZFC, поэтому ZFC не является полным. В этом случае нет очевидного кандидата на новую аксиому, решающую проблему.
Теория арифметики Пеано первого порядка кажется последовательной. Предполагая, что это действительно так, обратите внимание, что он имеет бесконечный, но рекурсивно перечислимый набор аксиом и может кодировать достаточно арифметических действий для гипотез теоремы о неполноте. Таким образом, по первой теореме о неполноте арифметика Пеано не является полной. Теорема дает явный пример арифметического утверждения, которое нельзя ни доказать, ни опровергнуть в арифметике Пеано. Более того, это утверждение верно и в обычной модели . Кроме того, никакое эффективно аксиоматизированное и последовательное расширение арифметики Пеано не может быть полным.
Последовательность
Набор аксиом (просто) непротиворечив, если нет такого утверждения, что и утверждение, и его отрицание доказуемы на основе аксиом, и несовместимы в противном случае.
Арифметика Пеано доказуемо согласована с ZFC, но не внутри себя. Точно так же ZFC не доказуемо согласован внутри себя, но ZFC + «существует недоступный кардинал » доказывает, что ZFC согласован, потому что если κ является наименьшим таким кардиналом, то V κ, находящийся во вселенной фон Неймана, является моделью ZFC, и теория непротиворечива тогда и только тогда, когда у нее есть модель.
Если принять все утверждения на языке арифметики Пеано как аксиомы, то эта теория будет полной, имеет рекурсивно перечислимый набор аксиом и может описывать сложение и умножение. Однако это не соответствует действительности.
Дополнительные примеры противоречивых теорий возникают из парадоксов, которые возникают, когда в теории множеств используется схема аксиом неограниченного понимания .
Системы, содержащие арифметику
Теоремы о неполноте применимы только к формальным системам, которые способны доказать достаточный набор фактов о натуральных числах. Одна достаточная коллекция множество теорем Robinson арифметической Q . Некоторые системы, такие как арифметика Пеано, могут напрямую выражать утверждения о натуральных числах. Другие, например теория множеств ZFC, могут интерпретировать утверждения о натуральных числах на своем языке. Любой из этих вариантов подходит для теорем о неполноте.
Теория алгебраически замкнутых полей данной характеристики является полной, непротиворечивой и имеет бесконечный, но рекурсивно перечислимый набор аксиом. Однако невозможно закодировать целые числа в этой теории, и теория не может описать арифметику целых чисел. Похожий пример - теория вещественных замкнутых полей , которая по существу эквивалентна аксиомам Тарского для евклидовой геометрии . Итак, сама евклидова геометрия (в формулировке Тарского) является примером полной, непротиворечивой, эффективно аксиоматизированной теории.
Система арифметики Пресбургера состоит из набора аксиом для натуральных чисел с помощью только операции сложения (умножение опускается). Арифметика Пресбургера является полной, непротиворечивой и рекурсивно перечислимой и может кодировать сложение, но не умножение натуральных чисел, показывая, что для теорем Гёделя нужна теория, чтобы кодировать не только сложение, но и умножение.
Дэн Уиллард (2001) изучил некоторые слабые семейства арифметических систем, которые допускают достаточно арифметических отношений для формализации нумерации Гёделя, но которые недостаточно сильны, чтобы иметь умножение как функцию, и поэтому не смогли доказать вторую теорему о неполноте; эти системы непротиворечивы и способны доказать свою непротиворечивость (см. теории самопроверки ).
Противоречивые цели
При выборе набора аксиом одна цель состоит в том, чтобы суметь доказать как можно больше правильных результатов без доказательства каких-либо неправильных результатов. Например, мы могли бы представить себе набор истинных аксиом, которые позволят нам доказать каждое истинное арифметическое утверждение о натуральных числах (Смит 2007, стр. 2). В стандартной системе логики первого порядка несовместимый набор аксиом доказывает каждое утверждение на ее языке (это иногда называют принципом взрыва ) и, таким образом, автоматически завершается. Множество аксиом является одновременно полным и последовательным, однако, доказывает максимальное множество непредставленных противоречивых теорем (Хинман 2005, стр. 143).
Шаблон, проиллюстрированный в предыдущих разделах с арифметикой Пеано, 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).
Чтобы доказать первую теорему о неполноте, Гёдель продемонстрировал, что понятие доказуемости внутри системы может быть выражено исключительно в терминах арифметических функций, которые оперируют числами Гёделя предложений системы. Следовательно, система, которая может доказывать определенные факты о числах, может также косвенно доказывать факты о своих собственных утверждениях, при условии, что они эффективно генерируются. Вопросы о доказуемости утверждений внутри системы представлены как вопросы об арифметических свойствах самих чисел, которые были бы решены системой, если бы она была полной.
Таким образом, хотя предложение Гёделя косвенно относится к предложениям системы F , когда оно читается как арифметическое утверждение, предложение Гёделя напрямую относится только к натуральным числам. Он утверждает, что ни одно натуральное число не имеет определенного свойства, причем это свойство задается примитивным рекурсивным отношением (Smith 2007, p. 141). Таким образом, предложение Гёделя может быть написано на языке арифметики с простой синтаксической формой. В частности, это может быть выражено в виде формулы на языке арифметики, состоящей из ряда ведущих универсальных кванторов, за которыми следует бескванторное тело (эти формулы находятся на уровнеиз арифметической иерархии ). С помощью теоремы MRDP предложение Гёделя можно переписать как утверждение, что конкретный многочлен от многих переменных с целыми коэффициентами никогда не принимает нулевое значение, когда его переменные подставляются целыми числами (Franzén 2005, p. 71).
Истина предложения Гёделя
Первая неполноте теорема показывает , что Гедель предложение G F соответствующей формальной теории F недоказуемо в F . Поскольку, когда эта недоказуемость интерпретируется как утверждение об арифметике, это именно то, что утверждает предложение (косвенно), предложение Гёделя на самом деле истинно (Smoryński 1977, с. 825; также см. Franzén 2005, с. 28–33). По этой причине предложение G F часто называют «истинным, но недоказуемым». (Раатикайнен 2015). Однако, поскольку предложение Гёделя не может само по себе формально определять предполагаемую интерпретацию, истинность предложения G F может быть достигнута только посредством метаанализа извне системы. В общем, этот метаанализ может быть проведен в рамках слабой формальной системы, известной как примитивно-рекурсивная арифметика , которая доказывает импликацию Con ( F ) → G F , где Con ( F ) - каноническое предложение, утверждающее непротиворечивость F (Smoryński 1977, с. 840, Кикучи и Танака, 1994, с. 403).
Хотя предложение Гёделя непротиворечивой теории истинно как утверждение о предполагаемой интерпретации арифметики, предложение Гёделя будет ложным в некоторых нестандартных моделях арифметики как следствие теоремы Гёделя о полноте (Franzén 2005, p. 135). Эта теорема показывает, что, когда предложение не зависит от теории, в теории будут модели, в которых предложение истинно, и модели, в которых предложение ложно. Как описано ранее, предложение Гёделя системы F является арифметическим утверждением, которое утверждает, что не существует числа с определенным свойством. Теорема о неполноте показывает, что это утверждение не будет зависеть от системы F , а истинность предложения Гёделя следует из того факта, что ни одно стандартное натуральное число не обладает указанным свойством. Любая модель, в которой предложение Гёделя ложно, должна содержать некоторый элемент, который удовлетворяет свойству в этой модели. Такая модель должна быть «нестандартной» - она должна содержать элементы, не соответствующие ни одному стандартному натуральному числу (Raatikainen 2015, Franzén 2005, p. 135).
Отношения с парадоксом лжеца
Гедель конкретно цитирует парадокс Ричарда и лжец парадокс как семантических аналогов в его синтаксической результате неполноты в вводном разделе « О формально Неразрешимые предложений в 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 сам по себе.
Выражение последовательности
Существует техническая тонкость во второй теореме о неполноте относительно способа выражения консистенции F в виде формулы на языке F . Есть много способов выразить непротиворечивость системы, и не все из них приводят к одинаковому результату. Формула Cons ( F ) из второй теоремы о неполноте является частным выражением непротиворечивости.
Другие формализации утверждения о непротиворечивости F могут быть неэквивалентны в F , а некоторые даже могут быть доказуемы. Например, арифметика Пеано первого порядка (PA) может доказать, что «наибольшее непротиворечивое подмножество PA» непротиворечиво. Но, поскольку PA согласован, наибольшее согласованное подмножество PA - это просто PA, поэтому в этом смысле PA «доказывает, что оно согласовано». Чего PA не доказывает, так это того, что наибольшее согласованное подмножество PA фактически является всей PA. (Термин «наибольшее согласованное подмножество PA» здесь означает наибольший согласованный начальный сегмент аксиом PA при некотором конкретном эффективном перечислении.)
Условия Гильберта – Бернейса.
Стандартное доказательство второй теоремы о неполноте предполагает, что предикат доказуемости Prov A ( P ) удовлетворяет условиям доказуемости Гильберта – Бернейса . Пусть # ( P ) представляет собой гёделевское число формулы P , условия доказуемости говорят:
- Если F доказывает P , то F доказывает Prov A (# ( P )).
- F доказывает 1 .; то есть F доказывает Prov A (# ( P )) → Prov A (# (Prov A (# (P)))).
- 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).
Следствие также указывает на эпистемологическую значимость второй теоремы о неполноте. На самом деле это не дало бы никакой интересной информации, если бы система F доказала свою непротиворечивость. Это потому, что противоречивые теории доказывают все, включая их непротиворечивость. Таким образом, доказательство непротиворечивости F в F не даст нам подсказки относительно того, действительно ли F непротиворечиво; никакие сомнения в непротиворечивости F не разрешатся с помощью такого доказательства непротиворечивости. Интерес доказательства непротиворечивости заключается в возможности доказать непротиворечивость системы F в некоторой системе F» , которая в некотором смысле менее сомнительным , чем F сам, например , слабее , чем F . Для многих естественных теорий F и F ' , таких как F = теория множеств Цермело – Френкеля и F' = примитивная рекурсивная арифметика, непротиворечивость F ' доказуема в F , и, таким образом, F' не может доказать непротиворечивость F с помощью приведенного выше Следствие второй теоремы о неполноте.
Вторая теорема о неполноте не исключает полностью возможности доказательства непротиворечивости некоторой теории T , только делая это в теории, непротиворечивость которой сама T может доказать. Например, Герхард Генцен доказал непротиворечивость арифметики Пеано в другой системе, которая включает аксиому, утверждающую, что ординал, называемый ε 0 , хорошо обоснован ; см . доказательство непротиворечивости Генцена . Теорема Генцена стимулировала развитие порядкового анализа в теории доказательств.
Примеры неразрешимых утверждений
В математике и информатике есть два разных значения слова «неразрешимый». Первый из них - это теоретико-доказательственный смысл, используемый по отношению к теоремам Гёделя, смысл утверждения, который нельзя ни доказать, ни опровергнуть в указанной дедуктивной системе . Второй смысл, который здесь обсуждаться не будет, используется в отношении теории вычислимости и применяется не к утверждениям, а к задачам принятия решений , которые представляют собой счетно бесконечные наборы вопросов, каждый из которых требует ответа «да» или «нет». Такая проблема называется неразрешимой, если нет вычислимой функции, которая правильно отвечает на все вопросы в наборе задач (см. Неразрешимую проблему ).
Из-за двух значений слова «неразрешимый» термин « независимый» иногда используется вместо «неразрешимый» в смысле «ни доказать, ни опровергнуть».
Неразрешимость утверждения в конкретной дедуктивной системе сама по себе не решает вопроса о том, является ли значение истинности утверждения хорошо определенным или его можно определить другими способами. Неразрешимость означает лишь то, что рассматриваемая конкретная дедуктивная система не доказывает истинность или ложность утверждения. Существуют ли так называемые «абсолютно неразрешимые» утверждения, значение истинности которых никогда не может быть известно или плохо определено, является спорным вопросом в философии математики .
Совместная работа Гёделя и Пола Коэна дала два конкретных примера неразрешимых утверждений (в первом смысле этого слова): гипотеза континуума не может быть ни доказана, ни опровергнута в ZFC (стандартная аксиоматизация теории множеств ) и аксиома выбор нельзя ни доказать, ни опровергнуть в ZF (а это все аксиомы ZFC, кроме аксиомы выбора). Эти результаты не требуют теоремы о неполноте. В 1940 году Гёдель доказал, что ни одно из этих утверждений не может быть опровергнуто в теории множеств ZF или ZFC. В 1960-х Коэн доказал, что ни одно из них не может быть доказано с помощью ZF, а гипотеза континуума не может быть доказана с помощью ZFC.
В 1973 году Сахарон Шелах показал, что проблема Уайтхеда в теории групп неразрешима в первом смысле этого слова в стандартной теории множеств.
Грегори Чейтин произвел неразрешимые утверждения в алгоритмической теории информации и доказал еще одну теорему о неполноте в этом контексте. Теорема Чейтина о неполноте утверждает, что для любой системы, которая может представить достаточно арифметических операций, существует верхняя граница c, такая, что нельзя доказать в этой системе какое-либо конкретное число, имеющее колмогоровскую сложность больше, чем c . В то время как теорема Гёделя связана с парадоксом лжеца , результат Чайтина связан с парадоксом Берри .
Неразрешимые утверждения, доказуемые в более крупных системах
Это естественные математические эквиваленты гёделевского «истинного, но неразрешимого» предложения. Они могут быть доказаны в более крупной системе, которая обычно считается допустимой формой рассуждений, но неразрешима в более ограниченной системе, такой как арифметика Пеано.
В 1977 году Пэрис и Харрингтон доказали, что принцип Париса – Харрингтона , версия бесконечной теоремы Рамсея , неразрешим в арифметике Пеано (первого порядка) , но может быть доказан в более сильной системе арифметики второго порядка . Кирби и Пэрис позже показали, что теорема Гудстейна , утверждение о последовательностях натуральных чисел несколько проще, чем принцип Пэрис – Харрингтона, также неразрешима в арифметике Пеано.
Теорема Крускала о дереве , имеющая приложения в информатике, также неразрешима из арифметики Пеано, но доказуема в теории множеств. Фактически теорема Крускала о дереве (или ее конечная форма) неразрешима в гораздо более сильной системе, кодифицирующей приемлемые принципы, основанные на философии математики, называемой предикативизмом . Родственная, но более общая теорема о графах минор (2003) имеет последствия для теории сложности вычислений .
Связь с вычислимостью
Теорема о неполноте тесно связана с несколькими результатами о неразрешимых множествах в теории рекурсии .
Стивен Коул Клини (1943) представил доказательство теоремы Гёделя о неполноте с использованием основных результатов теории вычислимости. Один из таких результатов показывает, что проблема остановки неразрешима: нет компьютерной программы, которая могла бы правильно определить, учитывая любую программу P в качестве входных данных, останавливается ли P в конечном итоге при запуске с конкретным заданным входом. Клини показал, что существование полной эффективной системы арифметики с определенными свойствами согласованности сделало бы проблему остановки разрешимой; противоречие. Этот метод доказательства также был представлен Шенфилдом (1967, стр. 132); Чарльзуорт (1980); и Хопкрофт и Ульман (1979).
Franzén (2005, стр. 73) объясняет , как решение Матиясевича в к 10 - й проблеме Гильберта может быть использовано для получения доказательства теоремы Гёделя о неполноте первой. Матиясевич доказал, что не существует алгоритма, который по многомерному многочлену p (x 1 , x 2 , ..., x k ) с целыми коэффициентами определяет, существует ли целочисленное решение уравнения p = 0. Поскольку многочлены с целыми числами коэффициенты и сами целые числа непосредственно выражаются на языке арифметики, если многомерное целочисленное полиномиальное уравнение p = 0 действительно имеет решение в целых числах, то любая достаточно сильная система арифметики T докажет это. Более того, если система T ω-согласована, то она никогда не докажет, что конкретное полиномиальное уравнение имеет решение, хотя на самом деле нет решения в целых числах. Таким образом, если бы T было полным и ω-непротиворечивым, можно было бы алгоритмически определить, имеет ли полиномиальное уравнение решение, просто перечислив доказательства T до тех пор, пока не будет найдено либо « p имеет решение», либо « p не имеет решения». противоречие с теоремой Матиясевича. Более того, для каждой согласованной эффективно сгенерированной системы T можно эффективно сгенерировать многомерный многочлен p над целыми числами, такой что уравнение p = 0 не имеет решений над целыми числами, но отсутствие решений не может быть доказано в T (Davis 2006 : 416, Джонс 1980).
Сморински (1977, с. 842) показывает, как существование рекурсивно неотделимых множеств может быть использовано для доказательства первой теоремы о неполноте. Это доказательство часто расширяется, чтобы показать, что такие системы, как арифметика Пеано, по существу неразрешимы (см. Kleene 1967, p. 274).
Теорема Чайтина о неполноте дает другой метод создания независимых предложений, основанный на сложности Колмогорова . Подобно упомянутому выше доказательству Клини, теорема Чейтина применима только к теориям с дополнительным свойством, что все их аксиомы верны в стандартной модели натуральных чисел. Теорема Гёделя о неполноте отличается своей применимостью к непротиворечивым теориям, которые, тем не менее, включают утверждения, ложные в стандартной модели; эти теории известны как ω-несовместимые .
Схема доказательства первой теоремы
Доказательство от противного имеет три основные части. Для начала выберите формальную систему, отвечающую предложенным критериям:
- Утверждения в системе могут быть представлены натуральными числами (известными как числа Гёделя). Значение этого состоит в том, что свойства утверждений, такие как их истинность и ложность, будут эквивалентны определению того, обладают ли их гёделевские числа определенными свойствами, и что свойства утверждений, следовательно, можно продемонстрировать, исследуя их гёделевские числа. Эта часть завершается построением формулы, выражающей идею, что «утверждение S доказуемо в системе» (которое может быть применено к любому утверждению «S» в системе).
- В формальной системе можно построить число, утверждение сопоставления которого при интерпретации является самореферентным и, по сути, говорит, что оно (то есть само утверждение) недоказуемо. Это делается с помощью техники, называемой « диагонализацией » (так называемой из-за того, что она возникла как диагональный аргумент Кантора ).
- В рамках формальной системы это утверждение позволяет продемонстрировать, что оно не может быть ни доказуемо, ни опровергнуто в системе, и поэтому система на самом деле не может быть ω-согласованной. Следовательно, первоначальное предположение о том, что предлагаемая система соответствует критериям, неверно.
Арифметизация синтаксиса
Основная проблема при конкретизации описанного выше доказательства заключается в том, что сначала кажется, что для построения утверждения p , эквивалентного « p не может быть доказано», p каким-то образом должен содержать ссылку на p , что может легко привести к бесконечный регресс. Гениальный метод Гёделя состоит в том, чтобы показать, что утверждения могут быть сопоставлены с числами (часто называемой арифметизацией синтаксиса ) таким образом, что «доказательство утверждения» может быть заменено «проверкой наличия у числа заданного свойства» . Это позволяет строить самореференциальную формулу таким образом, чтобы избежать бесконечного регресса определений. Эту же технику позже использовал Алан Тьюринг в своей работе над проблемой Entscheidungsproblem .
Проще говоря, можно разработать метод, чтобы каждая формула или утверждение, которое может быть сформулировано в системе, получало уникальный номер, называемый его числом Гёделя , таким образом, чтобы можно было механически преобразовывать назад и вперед между формулами и Гёделем. числа. Используемые числа действительно могут быть очень длинными (с точки зрения количества цифр), но это не препятствие; все, что имеет значение, - это то, что такие числа могут быть построены. Простым примером является то, как английский язык хранится как последовательность чисел на компьютерах с использованием ASCII или Unicode :
- Слово
HELLO
представлено 72-69-76-76-79 в десятичном формате ASCII , то есть числом 7269767679. - Логический оператор
x=y => y=x
представлен 120-061-121-032-061-062-032-121-061-120 с использованием восьмеричного ASCII , то есть числом 120061121032061062032121061120.
- Слово
В принципе, доказательство того, что утверждение истинно или ложно, может быть эквивалентно доказательству того, что число, соответствующее этому утверждению, имеет или не имеет заданное свойство. Поскольку формальная система достаточно сильна, чтобы поддерживать рассуждения о числах в целом , она может поддерживать рассуждения о числах, которые также представляют формулы и утверждения . Важно отметить, что поскольку система может поддерживать рассуждения о свойствах чисел , результаты эквивалентны рассуждениям о доказуемости их эквивалентных утверждений .
Построение утверждения о «доказуемости»
Показав, что в принципе система может косвенно делать утверждения о доказуемости, анализируя свойства этих чисел, представляющих утверждения, теперь можно показать, как создать утверждение, которое действительно делает это.
Формула F ( x ), содержащая ровно одну свободную переменную x , называется формой оператора или знаком класса . Как только x заменяется определенным числом, форма утверждения превращается в добросовестное утверждение, и тогда оно либо доказуемо в системе, либо нет. Для некоторых формул можно показать , что для любого натурального числа п ,истинно тогда и только тогда, когда его можно доказать (точное требование в исходном доказательстве слабее, но для схемы доказательства этого будет достаточно). В частности, это верно для каждой конкретной арифметической операции между конечным числом натуральных чисел, например «2 × 3 = 6».
Формы утверждений сами по себе не являются утверждениями и поэтому не могут быть доказаны или опровергнуты. Но каждой форме утверждения 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 ↔ ~ Bew ( 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).
Подтвержденные компьютером доказательства
Теоремы о неполноте относятся к относительно небольшому числу нетривиальных теорем, которые были преобразованы в формализованные теоремы, которые могут быть полностью проверены с помощью программного обеспечения помощника по доказательству . Оригинальные доказательства теорем о неполноте Гёделя, как и большинство математических доказательств, были написаны на естественном языке, предназначенном для читателей.
Проверенные компьютером доказательства версий первой теоремы о неполноте были анонсированы Натараджаном Шанкаром в 1986 году с использованием Nqthm (Шанкар, 1994), Расселом О'Коннором в 2003 году с использованием Coq (О'Коннор, 2005) и Джоном Харрисоном в 2009 году с использованием HOL Light ( Харрисон 2009). Подтвержденное компьютером доказательство обеих теорем о неполноте было объявлено Лоуренсом Полсоном в 2013 году с использованием Изабель (Paulson 2014).
Схема доказательства второй теоремы
Основная трудность при доказательстве второй теоремы о неполноте состоит в том, чтобы показать, что различные факты о доказуемости, используемые в доказательстве первой теоремы о неполноте, могут быть формализованы в рамках системы с использованием формального предиката доказуемости. После этого следует вторая теорема о неполноте путем формализации всего доказательства первой теоремы о неполноте внутри самой системы.
Пусть p обозначает неразрешимое предложение, построенное выше, и предположим, что непротиворечивость системы может быть доказана изнутри самой системы. Приведенная выше демонстрация показывает, что если система непротиворечива, то p недоказуемо. Доказательство этой импликации может быть формализовано в системе, и поэтому утверждение « p недоказуемо» или «не P ( p )» может быть доказано в системе.
Но это последнее утверждение эквивалентно самому p (и эта эквивалентность может быть доказана в системе), поэтому p можно доказать в системе. Это противоречие показывает, что система должна быть непоследовательной.
Обсуждение и последствия
Результаты неполноты влияют на философию математики , особенно на версии формализма , которые используют единую систему формальной логики для определения своих принципов.
Последствия для логицизма и вторая проблема Гильберта
Иногда считается, что теорема о неполноте имеет серьезные последствия для программы логицизма, предложенной Готтлобом Фреге и Бертраном Расселом , целью которой является определение натуральных чисел в терминах логики (Hellman 1981, p. 451–468). Боб Хейл и Криспин Райт утверждают, что это не проблема для логицизма, потому что теоремы о неполноте в равной степени применимы к логике первого порядка, как и к арифметике. Они утверждают, что с этой проблемой сталкиваются только те, кто считает, что натуральные числа следует определять в терминах логики первого порядка.
Многие Логики считают , что неполнота теорема Гёделя нанесла смертельный удар Давид Гильберта «s второй задаче , которые просили финитное доказательство непротиворечивости для математики. В частности, вторая теорема о неполноте часто рассматривается как решение, делающее проблему невозможной. Однако не все математики согласны с этим анализом, и статус второй проблемы Гильберта еще не решен (см. « Современные точки зрения на статус проблемы »).
Умы и машины
Авторы, включая философа Дж. Р. Лукаса и физика Роджера Пенроуза , обсуждали, что, во всяком случае, подразумевают теоремы Геделя о неполноте относительно человеческого интеллекта. Большая часть споров сосредоточена на том, эквивалентен ли человеческий разум машине Тьюринга или, согласно тезису Чёрча-Тьюринга , любой конечной машине вообще. Если это так и если машина непротиворечива, то к ней применимы теоремы Гёделя о неполноте.
Хилари Патнэм (1960) предположила, что, хотя теоремы Гёделя не могут быть применены к людям, поскольку они делают ошибки и, следовательно, непоследовательны, они могут быть применены к человеческому факультету естественных наук или математики в целом. Если предположить, что она непротиворечива, либо ее непротиворечивость нельзя доказать, либо она не может быть представлена машиной Тьюринга.
Ави Вигдерсон (2010) предположил, что концепция математической «познаваемости» должна основываться на вычислительной сложности, а не на логической разрешимости. Он пишет, что «когда познаваемость интерпретируется в соответствии с современными стандартами, а именно через вычислительную сложность, явления Гёделя очень важны для нас».
Дуглас Хофштадтер в своих книгах « Гедель, Эшер, Бах и« Я странная петля » цитирует теоремы Геделя как пример того, что он называет странной петлей , иерархической самореферентной структурой, существующей в аксиоматической формальной системе. Он утверждает, что это такая же структура, которая дает начало сознанию, чувству «я» в человеческом разуме. В то время как самоотнесение в теореме Гёделя происходит от предложения Гёделя, утверждающего его собственную недоказуемость в формальной системе Principia Mathematica, самореференция в человеческом разуме происходит из того, как мозг абстрагирует и классифицирует стимулы в «символы», или группы нейронов, которые реагируют на концепции, в том, что фактически также является формальной системой, что в конечном итоге дает начало символам, моделирующим концепцию самой сущности, осуществляющей восприятие. Хофштадтер утверждает, что странная петля в достаточно сложной формальной системе может привести к «нисходящей» или «перевернутой» причинно-следственной связи, ситуации, в которой нормальная причинно-следственная иерархия перевернута с ног на голову. Короче говоря, в случае теоремы Гёделя это проявляется в следующем:
«Просто зная значение формулы, можно сделать вывод о ее истинности или ложности, не прилагая никаких усилий, чтобы вывести ее старомодным способом, который требует методического тащения« вверх »от аксиом. Это не просто странно, это поразительно. . Обычно нельзя просто смотреть на то, что говорит математическая гипотеза, и просто апеллировать к содержанию этого утверждения, чтобы сделать вывод, истинно это утверждение или ложно ». ( Я - странная петля. ) [1]
В случае разума, гораздо более сложной формальной системы, эта «нисходящая причинность» проявляется, с точки зрения Хофштадтера, как невыразимый человеческий инстинкт, согласно которому причинность нашего разума лежит на высоком уровне желаний, концепций, личностей, мыслей и т. Д. идеи, а не о низком уровне взаимодействий между нейронами или даже элементарными частицами, хотя, согласно физике, последние, по-видимому, обладают причинной силой.
"Таким образом, в нашем обычном человеческом способе восприятия мира есть любопытная обратная сторона: мы созданы, чтобы воспринимать" большие вещи ", а не" мелочи ", хотя кажется, что именно в области крошечных движутся настоящие двигатели. реальность проживает ". ( Я - странная петля. ) [1]
Паранепротиворечивая логика
Хотя теоремы Гёделя обычно изучаются в контексте классической логики, они также играют роль в изучении паранепротиворечивой логики и изначально противоречивых утверждений ( dialetheia ). Грэм Прист (1984, 2006) утверждает, что замена понятия формального доказательства в теореме Гёделя обычным понятием неформального доказательства может использоваться, чтобы показать, что наивная математика непоследовательна, и использует это как доказательство диалетеизма . Причина этого несоответствия - включение предиката истинности для системы в язык системы (Priest 2006: 47). Стюарт Шапиро (2002) дает более неоднозначную оценку применения теорем Гёделя к диалетеизму.
Апелляции к теоремам о неполноте в других областях
Иногда к теоремам о неполноте прибегают и проводят аналогии в поддержку аргументов, выходящих за рамки математики и логики. Некоторые авторы отрицательно прокомментировали такие расширения и интерпретации, в том числе Торкель Франзен (2005); Пану Раатикайнен (2005 г.); Алан Сокал и Жан Брикмон (1999); и Офелия Бенсон и Джереми Стэнгрум (2006). Брикмонт и Стангрум (2006, стр. 10), например, цитируют комментарии Ребекки Гольдштейн о несоответствии между общепризнанным платонизмом Гёделя и антиреалистическим использованием его идей. Сокаль и Брикмон (1999, с. 187) критикуют обращение Режиса Дебре к теореме в контексте социологии; Дебрей защитил это использование как метафорическое (там же).
История
После того, как Гёдель опубликовал свое доказательство теоремы о полноте в качестве докторской диссертации в 1929 году, он обратился ко второй проблеме своей абилитации . Его первоначальной целью было получить положительное решение второй проблемы Гильберта (Dawson 1997, p. 63). В то время теории натуральных и действительных чисел, подобные арифметике второго порядка, были известны как «анализ», а теории одних только натуральных чисел были известны как «арифметика».
Гёдель был не единственным, кто работал над проблемой согласованности. Аккерман опубликовал для анализа некорректное доказательство непротиворечивости в 1925 году, в котором он попытался использовать метод ε-подстановки, первоначально разработанный Гильбертом. Позже в том же году фон Нейман смог исправить доказательство для системы арифметики без каких-либо аксиом индукции. К 1928 году Аккерман сообщил Бернейсу модифицированное доказательство; это модифицированное доказательство привело Гильберта к заявлению в 1929 г. о своей убежденности в том, что непротиворечивость арифметики была продемонстрирована и что вскоре последует доказательство непротиворечивости анализа. После того, как публикация теорем о неполноте показала, что модифицированное доказательство Аккермана должно быть ошибочным, фон Нейман привел конкретный пример, показывающий, что его основная техника была несостоятельной (Zach 2006, 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).
Обобщение и принятие
Гёдель прочитал серию лекций по своим теоремам в Принстоне в 1933–1934 годах для аудитории, в которую входили Черч, Клини и Россер. К этому времени Гёдель понял, что ключевое свойство, необходимое для его теорем, состоит в том, что система должна быть эффективной (в то время использовался термин «общерекурсивная»). Россер доказал в 1936 году, что гипотеза ω-согласованности, которая была неотъемлемой частью первоначального доказательства Гёделя, может быть заменена простой согласованностью, если предложение Гёделя было изменено соответствующим образом. Эти разработки оставили теоремы о неполноте по существу в их современной форме.
Генцен опубликовал свое доказательство непротиворечивости арифметики первого порядка в 1936 году. Гильберт принял это доказательство как «конечное», хотя (как уже показала теорема Гёделя) его нельзя формализовать в рамках системы арифметики, которая доказывается непротиворечивостью.
Влияние теорем о неполноте на программу Гильберта было быстро осознано. Бернейс включил полное доказательство теорем о неполноте во второй том Grundlagen der Mathematik (1939), наряду с дополнительными результатами Аккермана по методу ε-подстановки и доказательством непротиворечивости арифметики Генценом. Это было первое полностью опубликованное доказательство второй теоремы о неполноте.
Критика
Финслер
Пол Финслер (1926) использовал версию парадокса Ричарда, чтобы построить выражение, которое было ложным, но недоказуемым в определенной, неформальной структуре, которую он разработал. Гёдель не знал об этой статье, когда доказывал теоремы о неполноте (Сборник работ, том IV, стр. 9). Финслер написал Геделю в 1931 году, чтобы проинформировать его об этой статье, которая, по мнению Финслера, имела приоритет для теоремы о неполноте. Методы Финслера не основывались на формализованной доказуемости и имели лишь внешнее сходство с работами Гёделя (van Heijenoort 1967: 328). Гёдель прочитал статью, но обнаружил в ней серьезные недостатки, и в его ответе Финслеру высказывались опасения по поводу отсутствия формализации (Доусон: 89). Финслер продолжал отстаивать свою философию математики, которая избегала формализации, до конца своей карьеры.
Цермело
В сентябре 1931 года Эрнст Цермело написал Гёделю, чтобы объявить о том, что он назвал «существенным пробелом» в аргументации Гёделя (Dawson: 76). В октябре Гёдель ответил 10-страничным письмом (Dawson: 76, Grattan-Guinness: 512-513), в котором он указал, что Цермело ошибочно предположил, что понятие истины в системе определимо в этой системе (что не верно в общем случае по теореме Тарского о неопределенности ). Но Цермело не смягчился и опубликовал свою критику в печати с «довольно резким абзацем о своем молодом конкуренте» (Grattan-Guinness: 513). Гёдель решил, что дальнейшее обсуждение этого вопроса бессмысленно, и Карнап согласился (Доусон: 77). Большая часть последующей работы Цермело была связана с логикой, более сильной, чем логика первого порядка, с помощью которой он надеялся показать как последовательность, так и категоричность математических теорий.
Витгенштейн
Людвиг Витгенштейн написал несколько отрывков о теоремах о неполноте, которые были опубликованы посмертно в его « Замечаниях об основах математики» 1953 года , в частности, в одном разделе, который иногда называют «пресловутым параграфом», где он, кажется, путает понятия «истинный» и «доказуемый». Система Рассела. Гёдель был членом Венского кружка в тот период, когда в его мышлении доминировали ранняя идеальная языковая философия Витгенштейна и Tractatus Logico-Philosophicus . Были некоторые разногласия по поводу того, неправильно ли Витгенштейн понял теорему о неполноте или просто выразился нечетко. Писания в Nachlass Гёделя выражают уверенность в том, что Витгенштейн неверно истолковал свои идеи.
Многие комментаторы считали Витгенштейна неверным пониманием Гёделя (Rodych 2003), хотя Джульет Флойд и Хилари Патнэм (2000), а также Грэм Прист (2004) предоставили текстовые чтения, утверждая, что большинство комментариев неправильно понимают Витгенштейна. После освобождения Бернейс, Даммет и Крайзель написали отдельные отзывы о замечаниях Витгенштейна, и все они были крайне негативными (Berto 2009: 208). Единодушие в этой критике привело к тому, что замечания Витгенштейна о теоремах о неполноте мало повлияли на логическое сообщество. В 1972 году Гёдель заявил: «Витгенштейн сошёл с ума? Серьёзно ли он? Он намеренно произносит тривиально бессмысленные утверждения» (Wang 1996: 179) и написал Карлу Менгеру, что комментарии Витгенштейна демонстрируют неправильное понимание написания теорем о неполноте:
Из приведенных вами отрывков ясно, что Витгенштейн не понимал [первую теорему о неполноте] (или делал вид, что не понимает ее). Он интерпретировал это как своего рода логический парадокс, хотя на самом деле это прямо противоположное, а именно математическую теорему в рамках абсолютно бесспорной части математики (теории конечных чисел или комбинаторики). (Ван 1996: 179)
С момента публикации « Нахласса» Витгенштейна в 2000 году в ряде философских статей была предпринята попытка оценить, была ли оправдана первоначальная критика замечаний Витгенштейна. Флойд и Патнэм (2000) утверждают, что Витгенштейн имел более полное понимание теоремы о неполноте, чем предполагалось ранее. Они особенно озабочены интерпретацией предложения Гёделя для ω-несовместимой системы как фактически говорящего «Я недоказуемо», поскольку в системе нет моделей, в которых предикат доказуемости соответствует фактической доказуемости. Родич (2003) утверждает, что их интерпретация Витгенштейна не является исторически оправданной, в то время как Бэйс (2004) выступает против философского анализа предиката доказуемости Флойда и Патнэма. Берто (2009) исследует взаимосвязь между написанием Витгенштейна и теориями паранепротиворечивой логики.
Смотрите также
- Машина Гёделя
- Теорема Гёделя о полноте
- Теорема Гёделя об ускорении
- Гёдель, Эшер, Бах
- Теорема Лёба
- Умы, машины и Гёдель
- Трилемма Мюнхгаузена
- Нестандартная модель арифметики
- Теория доказательств
- Логика доказуемости
- Quining
- Теорема Тарского о неопределенности
- Теория всего # Теорема Гёделя о неполноте
- Третий аргумент
- Теория типографских чисел
Рекомендации
Цитаты
- ^ a b Хофштадтер, Дуглас Р. (2007) [2003]. «Глава 12. О нисходящей причинности» . Я странная петля . ISBN 978-0-465-03078-1.
Статьи Гёделя
- Курт Гёдель, 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). Существуют три перевода. О первом Джон Доусон заявляет, что: «Перевод Мельцера был серьезно несовершенным и получил разрушительную рецензию в Журнале символической логики» ; Гедель также жаловался на комментарий Брейтуэйта (Dawson 1997: 216). «К счастью, перевод Мельтцера вскоре был заменен лучшим переводом, подготовленным Эллиоттом Мендельсоном для антологии Мартина Дэвиса« Неразрешимое » ... он нашел перевод« не совсем таким хорошим », как он ожидал ... [но из-за нехватки времени он ] согласился на его публикацию »(там же). (В сноске Доусон заявляет, что «он будет сожалеть о своем согласии, поскольку опубликованный том был испорчен неряшливой типографикой и многочисленными опечатками» (там же)). Доусон утверждает, что «Гёдель предпочел перевод, сделанный Жаном ван Хейенуртом» (там же). Для серьезного студента существует другая версия в виде набора конспектов лекций, записанных Стивеном Клини и Дж. Б. Россером «во время лекций, прочитанных Геделем в Институте перспективных исследований весной 1934 года» (см. Комментарий Дэвиса 1965: 39 и начиная с стр.41); эта версия называется «О неразрешимых предложениях формальных математических систем». В порядке публикации:
- Б. Мельцер (перевод) и Р. Б. Брейтуэйт (Введение), 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 , Harvard University Press, Cambridge Mass., ISBN 0-674-32449-8 ( PBK ). Ван Хейеноорт сделал перевод. Он заявляет, что «профессор Гёдель одобрил перевод, который во многих местах соответствовал его пожеланиям». (стр. 595). Статья Гёделя начинается на стр. 595; Комментарий ван Хейенурта начинается на стр. 592.
- Редактор Мартина Дэвиса, 1965, там же. «О неразрешимых предложениях формальных математических систем». Копия с исправлениями Гёделя и добавленными примечаниями Гёделя начинается на странице 41, ей предшествуют две страницы комментария Дэвиса. Пока Дэвис не включил это в свой том, эта лекция существовала только в виде мимеографических заметок.
Статьи других авторов
- Джордж Булос , 1989, «Новое доказательство теоремы Гёделя о неполноте», Notices of the American Mathematical Society , v, 36, pp. 388–390 и p. 676, перепечатано в Boolos, 1998, Logic, Logic, and Logic , Harvard Univ. Нажмите. ISBN 0-674-53766-1
- Бернд Булдт, 2014 г., « Область действия первой теоремы Гёделя о неполноте », Logica Universalis , т. 8, стр. 499–552. DOI : 10.1007 / s11787-014-0107-3
- Артур Чарльзуорт, 1980, «Доказательство теоремы Гёделя в терминах компьютерных программ», Mathematics Magazine , v. 54 n. 3. С. 109–121. JSTOR 2689794
- Мартин Дэвис , 2006, " Теорема о неполноте ", Уведомления AMS , т. 53, п. 4. С. 414.
- Жан ван Хейеноорт , 1963, «Теорема Гёделя» в Эдвардсе, Пол, изд. Энциклопедия философии, т. 3 . Macmillan, стр. 348–57.
- Джеффри Хеллман , 1981, "Как Геделя и Фреге-Рассела: теоремы Геделя о неполноте и логицизм", Nos , v. 15 n. 4, Специальный выпуск по философии математики, стр. 451–468.
- Дэвид Гильберт , 1900, « Математические проблемы». Английский перевод лекции, прочитанной перед Международным конгрессом математиков в Париже, содержащей формулировку Гильбертом его Второй проблемы.
- Мартин Хирцель, 2000, " О формально неразрешимых предложениях Principia Mathematica и родственных систем I. " Английский перевод статьи Гёделя. Архивировано с оригинала . 16 сентября 2004 г.
- Макото Кикучи и Казаюки Танака, 1994, "О формализации теоретико-модельных доказательств теорем Гёделя", Notre Dame Journal of Formal Logic , v. 5 n. 3. С. 403–412. DOI : 10.1305 / ndjfl / 1040511346 MR1326122
- Стивен Коул Клини , 1943, «Рекурсивные предикаты и кванторы», перепечатано из « Транзакций Американского математического общества» , т. 53, с. 1, стр. 41–73 в Мартине Дэвисе 1965 г., «Неразрешимый» (loc. Cit.), Стр. 255–287.
- Пану Раатикайнен, 2015, « Теоремы Гёделя о неполноте », Стэнфордская философская энциклопедия . По состоянию на 3 апреля 2015 г.
- Пану Раатикайнен, 2005, «О философской значимости теорем Гёделя о неполноте» , Revue Internationale de Philosophie 59 (4): 513-534.
- Джон Баркли Россер , 1936, «Расширения некоторых теорем Гёделя и Черча», перепечатано из Journal of Symbolic Logic , v. 1 (1936) pp. 87–91, в Martin Davis 1965, The Undecidable (loc. Cit.) С. 230–235.
- -, 1939, «Неофициальное изложение доказательств теоремы Гёделя и теоремы Чёрча», перепечатано из Journal of Symbolic Logic , v. 4 (1939), стр. 53–60, в Martin Davis 1965, The Undecidable (loc. Cit. ) стр. 223–230
- К. Сморински, 1982, "Теоремы о неполноте", в издании Джона Барвайса , Справочник по математической логике , Северная Голландия, стр. 821–866. ISBN 978-0-444-86388-1
- Дэн Э. Уиллард, 2001, « Самопроверяющиеся системы аксиом, теорема о неполноте и связанные с ними принципы отражения », Журнал символической логики , т. 66, с. 2. С. 536–596. DOI : 10,2307 / 2695030
- Ричард Зак , 2003. " Практика финитизма: исчисление Эпсилона и доказательства непротиворечивости в программе Гильберта " Synthese , v. 137 n. 1. С. 211–259. DOI : 10,1023 / A: 1026247421383
- -, 2005, " Курт Гёдель, Статья о теоремах о неполноте " в Ivor Grattan-Guinness , ed. Достопримечательности западной математики , Elsevier, стр. 917–925. DOI : 10.1016 / B978-044450871-3 / 50152-2
Книги о теоремах
- Франческо Берто. Есть кое-что о Гёделе: Полное руководство по теореме о неполноте Джон Уайли и сыновья. 2010 г.
- Норберт Домейзен, 1990. Logik der Antinomien . Берн: Питер Ланг. 142 с. 1990. ISBN 3-261-04214-1 . Zbl 0724.03003 .
- Торкель Францен , 2005. Теорема Гёделя: неполное руководство по ее использованию и злоупотреблениям . А.К. Петерс. ISBN 1-56881-238-8 MR2146326
- Дуглас Хофштадтер , 1979. Гедель, Эшер, Бах: вечная золотая коса . Винтажные книги. ISBN 0-465-02685-0 . Переиздание 1999 г .: ISBN 0-465-02656-7 . МИСТЕР530196
- -, 2007. Я - странная петля . Основные книги. ISBN 978-0-465-03078-1 . ISBN 0-465-03078-5 . МИСТЕР2360307
- Стэнли Джаки , OSB, 2005. Драма количества . Реальный просмотр книг.
- Пер Линдстрем , 1997. Аспекты неполноты , конспекты лекций по логике v. 10.
- JR Лукас , FBA, 1970. Свобода воли . Кларендон Пресс, Оксфорд, 1970.
- Эрнест Нагель , Джеймс Рой Ньюман , Дуглас Хофштадтер, 2002 (1958). Доказательство Гёделя , переработанное изд. ISBN 0-8147-5816-9 . МИСТЕР1871678
- Руди Ракер , 1995 (1982). Бесконечность и разум: наука и философия бесконечного . Princeton Univ. Нажмите. МИСТЕР658492
- Питер Смит, 2007. Введение в теоремы Гёделя. Издательство Кембриджского университета. МИСТЕР2384958
- Н. Шанкар, 1994. Метаматематика, машины и доказательство Гёделя , Том 38 Кембриджских трактатов по теоретической информатике. ISBN 0-521-58533-3
- Раймонд Смуллян , 1987. Вечно нерешительный.ISBN 0192801414 - головоломки, основанные на неразрешимости формальных систем
- -, 1991. Теоремы Гёделя о неполноте . Oxford Univ. Нажмите.
- -, 1994. Диагонализация и самореференция . Oxford Univ. Нажмите. МИСТЕР1318913
- -, 2013. Годелевская книга головоломок: головоломки, парадоксы и доказательства . Курьерская корпорация. ISBN 978-0-486-49705-1 .
- Хао Ван , 1997. Логическое путешествие: от Гёделя к философии . MIT Press. ISBN 0-262-23189-1 MR1433803
Разные ссылки
- Франческо Берто, 2009, «Парадокс Гёделя и причины Витгенштейна» Philosophia Mathematica (III) 17.
- Джон У. Доусон-младший , 1997. Логические дилеммы: жизнь и творчество Курта Гёделя , А.К. Петерс , Уэллсли Масса, ISBN 1-56881-256-6 .
- Ребекка Гольдштейн , 2005 г., Неполнота: доказательство и парадокс Курта Гёделя , WW Norton & Company. ISBN 0-393-05169-2
- Джульет Флойд и Хилари Патнэм , 2000, «Заметка о« печально известном параграфе »Витгенштейна о теореме Гёделя», Journal of Philosophy v. 97 n. 11. С. 624–632.
- Джон Харрисон, 2009, "Справочник по практической логике и автоматизированному мышлению", Cambridge University Press, ISBN 0521899575
- Дэвид Гильберт и Пол Бернейс , Grundlagen der Mathematik , Springer-Verlag.
- Джон Хопкрофт и Джеффри Уллман 1979, Введение в теорию автоматов, языки и вычисления , Addison-Wesley, ISBN 0-201-02988-X
- Джеймс П. Джонс, «Неразрешимые диофантовы уравнения» , Бюллетень Американского математического общества , т. 3, стр. 2, 1980, с. 859–862.
- Стивен Коул Клини , 1967, Математическая логика . Перепечатано Dover, 2002. ISBN 0-486-42533-9
- Рассел О'Коннор, 2005, « Существенная неполнота арифметики, подтвержденная Coq », Lecture Notes in Computer Science v. 3603, pp. 245–260.
- Лоуренс Полсон , 2013, «Машинное доказательство теорем Гёделя о неполноте для теории наследственно конечных множеств», Review of Symbolic Logic , v. 7 n. 3, 484–498.
- Грэхем Прист , 1984, «Возвращение к логике парадокса», Journal of Philosophical Logic , т. 13, `n. 2. С. 153–179.
- -, 2004, Замечания Витгенштейна к теореме Гёделя в книге Макса Кёльбеля, изд., Непреходящее значение Витгенштейна , Psychology Press, стр. 207–227.
- -, 2006, В противоречии: исследование трансконсистентного , Oxford University Press, ISBN 0-19-926329-9
- Хилари Патнэм , 1960, « Умы и машины в Сидни Хук» , изд. « Измерения разума: симпозиум» . Издательство Нью-Йоркского университета. Перепечатано в Anderson, AR, ed., 1964. Minds and Machines . Прентис-Холл: 77.
- Вольфганг Раутенберг , 2010, Краткое введение в математическую логику , 3-е. изд., Springer, ISBN 978-1-4419-1220-6
- Виктор Родич, 2003, «Непонимание Гёделя: новые аргументы о Витгенштейне и новые замечания Витгенштейна», Dialectica v. 57 n. 3. С. 279–313. DOI : 10.1111 / j.1746-8361.2003.tb00272.x
- Стюарт Шапиро , 2002, «Неполнота и непоследовательность», Разум , т. 111, стр. 817–32. DOI : 10,1093 / ум / 111.444.817
- Алан Сокал и Жан Брикмонт , 1999, Модная бессмыслица : злоупотребление наукой постмодернистскими интеллектуалами , Picador. ISBN 0-312-20407-8
- Джозеф Р. Шенфилд (1967), Математическая логика . Перепечатано А.К. Петерсом для Ассоциации символической логики , 2001. ISBN 978-1-56881-135-2
- Джереми Стэнгрум и Офелия Бенсон , Почему правда важна , Continuum. ISBN 0-8264-9528-1
- Джордж Турлакис, Лекции по логике и теории множеств, Том 1, Математическая логика , Cambridge University Press, 2003. ISBN 978-0-521-75373-9
- Ави Вигдерсон , 2010 г., « Явления Гёделя в математике: современный взгляд », в книге Курт Гёдель и основы математики: горизонты истины , Cambridge University Press.
- Хао Ван , 1996, Логическое путешествие: от Гёделя к философии , MIT Press, Кембридж, Массачусетс, ISBN 0-262-23189-1 .
- Ричард Зак , 2006, «Программа Гильберта тогда и сейчас» , в Философии логики , Дейл Жакетт (редактор), Справочник по философии науки, т. 5., Elsevier, стр. 411–447.
Внешние ссылки
- Теоремы Гёделя о неполноте в наше время на BBC
- Запись Джульетты Кеннеди «Курт Гёдель» в Стэнфордской энциклопедии философии , 5 июля 2011 года.
- Запись Пану Раатикайнена «Теоремы Гёделя о неполноте» в Стэнфордской энциклопедии философии , 11 ноября 2013 г.
- Параконсистентная логика § Арифметика и теорема Гёделя в Стэнфордской энциклопедии философии .
- Биографии MacTutor:
- Курт Гёдель.
- Герхард Генцен.
- Что такое математика: теорема Геделя и вокруг по Карлис Подниекса . Бесплатная онлайн-книга.
- Кратчайшее в мире объяснение теоремы Гёделя на примере печатной машины.
- Октябрь 2011 года. Эпизод RadioLab о теореме Гёделя о неполноте.
- "Теорема Гёделя о неполноте" , Энциклопедия математики , EMS Press , 2001 [1994]
- Как Proof Работы Гёделя по Натали Wolchover , Quanta Magazine , 14 июля 2020 года.