Теорема Гёдельса о полноте - Википедия - Gödels completeness theorem

Формула (∀Икс. р(Икс,Икс)) → (∀Икс∃у. р(Икс,у)) выполняется во всех структуры (слева показаны только самые простые 8). По результату Гёделя о полноте он должен иметь естественный вычет доказательство (показано справа).

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

Впервые это было доказано Курт Гёдель в 1929 году. Затем он был упрощен в 1947 году, когда Леон Хенкин заметил в его Кандидат наук. Тезис что сложная часть доказательства может быть представлена ​​как модельная теорема существования (опубликована в 1949 г.). Доказательство Хенкина было упрощено Гисберт Хазенджегер в 1953 г.

Предварительные мероприятия

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

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

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

Заявление

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

Оригинальная формулировка Гёделя

Теорема о полноте говорит, что если формула логически верна, то существует конечный вывод (формальное доказательство) формулы.

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

Более общая форма

В более общем виде теорема может быть выражена в терминах логическое следствие. Мы говорим, что предложение s это синтаксическое следствие теории Т, обозначенный ${ displaystyle T vdash s}$, если s можно доказать из Т в нашей дедуктивной системе. Мы говорим что s это семантическое следствие из Т, обозначенный ${ displaystyle T models s}$, если s держится в каждом модель из Т. Теорема о полноте говорит, что для любой теории первого порядка Т с хорошо заказываемый язык и любое предложение s на языке Т,

если ${ displaystyle T models s}$, тогда ${ displaystyle T vdash s}$.

Поскольку верно и обратное (правильность), отсюда следует, что ${ displaystyle T models s}$ если только ${ displaystyle T vdash s}$, и, таким образом, это синтаксическое и семантическое следствие эквивалентно для логики первого порядка.

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

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

Теорема существования модели

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

если ${ displaystyle T}$ синтаксически непротиворечиво, то ${ displaystyle T}$ есть модель.

Другая версия, с подключениями к Теорема Левенгейма – Сколема, говорит:

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

Учитывая теорему Хенкина, теорему о полноте можно доказать следующим образом: если ${ displaystyle T models s}$, тогда ${ Displaystyle Т чашка lnot s}$ нет моделей. По контрасту теоремы Хенкина, тогда ${ Displaystyle Т чашка lnot s}$ синтаксически несогласован. Итак, противоречие (${ displaystyle bot}$) доказуемо из ${ Displaystyle Т чашка lnot s}$ в дедуктивной системе. Следовательно ${ Displaystyle (Т чашка lnot s) vdash bot}$, а затем по свойствам дедуктивной системы ${ displaystyle T vdash s}$.

Как теорема арифметики

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

Последствия

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

Это контрастирует с прямым значением понятия семантического следствия, которое дает количественную оценку по всем структурам на конкретном языке, что явно не является рекурсивным определением.

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

Связь со второй теоремой о неполноте

Вторая теорема Гёделя о неполноте (см. Теоремы Гёделя о неполноте ), еще один знаменитый результат, показывает, что существуют определенные ограничения в том, что может быть достигнуто с помощью формальных доказательств в математике. Название теоремы о неполноте относится к другому значению полный (видеть теория моделей - Использование теорем компактности и полноты ): Теория Т является полным (или разрешимым), если для каждой формулы ж на языке Т либо ${ displaystyle T vdash f}$ или же ${ displaystyle T vdash neg f}$.

Вторая теорема Гёделя о неполноте утверждает, что в любом последовательный эффективный теория Т содержащий Арифметика Пеано (PA) формула C_Т подобно C_Т${ displaystyle = neg (0 = 1)}$ выражая последовательность Т не может быть доказано в Т.

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

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

Также, нет рекурсивной нестандартной модели ПА.

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

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

Теорема компактности утверждает, что если формула φ является логическим следствием (возможно, бесконечного) множества формул Γ, то она является логическим следствием конечного подмножества Γ. Это является непосредственным следствием теоремы о полноте, потому что только конечное число аксиом из Γ может быть упомянуто при формальном выводе φ, и из правильности дедуктивной системы тогда следует, что φ является логическим следствием этого конечного множества. Это доказательство теоремы компактности первоначально принадлежит Гёделю.

И наоборот, для многих дедуктивных систем можно доказать теорему о полноте как эффективное следствие теоремы о компактности.

Неэффективность теоремы о полноте можно измерить по формуле обратная математика. При рассмотрении над счетным языком теоремы о полноте и компактности эквивалентны друг другу и эквивалентны слабой форме выбора, известной как слабая лемма Кёнига, с эквивалентностью доказуемой в RCA₀ (вариант второго порядка Арифметика Пеано индукцией по Σ⁰₁ формулы). Лемма Слабого Кенига доказуема в ZF, системе Теория множеств Цермело – Френкеля без аксиомы выбора, и, таким образом, теоремы о полноте и компактности для счетных языков доказуемы в ZF. Однако ситуация иная, когда язык имеет произвольно большую мощность, с тех пор, хотя теоремы о полноте и компактности остаются доказуемо эквивалентными друг другу в ZF, они также доказуемо эквивалентны слабой форме аксиома выбора известный как лемма об ультрафильтрации. В частности, никакая теория, расширяющая ZF, не может доказать теоремы о полноте или компактности над произвольными (возможно, несчетными) языками без доказательства леммы об ультрафильтре на множестве той же мощности.

Полнота в другой логике

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

Теорема Линдстрема утверждает, что логика первого порядка является самой сильной (с учетом определенных ограничений) логикой, удовлетворяющей как компактности, так и полноте.

Теорема полноты может быть доказана для модальная логика или же интуиционистская логика относительно Семантика Крипке.

Доказательства

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

В современных текстах по логике теорема Гёделя о полноте обычно доказывается с помощью Хенкин доказательства, а не с оригинальным доказательством Гёделя. Доказательство Хенкина непосредственно строит термин модель для любой непротиворечивой теории первого порядка. Джеймс Маргетсон (2004) разработал компьютеризированное формальное доказательство, используя Изабель средство доказательства теорем.^[1] Известны и другие доказательства.

Смотрите также

• Теоремы Гёделя о неполноте
• Оригинальное доказательство теоремы Гёделя о полноте

дальнейшее чтение

• Гёдель, К (1929). "Über die Vollständigkeit des Logikkalküls". Докторская диссертация. Венский университет. Цитировать журнал требует | журнал = (помощь) Первое доказательство теоремы о полноте.
• Гёдель, К (1930). "Die Vollständigkeit der Axiome des logischen Funktionenkalküls". Monatshefte für Mathematik (на немецком). 37 (1): 349–360. Дои:10.1007 / BF01696781. JFM  56.0046.04. S2CID  123343522. Тот же материал, что и диссертация, за исключением более коротких доказательств, более сжатых объяснений и исключения длинного введения.

внешняя ссылка

• Стэнфордская энциклопедия философии: "Курт Гёдель "-к Джульетта Кеннеди.
• Биография MacTutor: Курт Гёдель.
• Детловс, Вилнис, Подниекс, Карлис "Введение в математическую логику. "