WikiSort.ru - Не сортированное

Теоре́ма Гёделя о полноте́ исчисле́ния предика́тов является одной из фундаментальных теорем математической логики: она устанавливает однозначную связь между логической истинностью высказывания и его выводимостью в логике первого порядка. Впервые эта теорема была доказана Куртом Гёделем в 1929.

Иными словами, если ${\displaystyle \Phi }$ - тождественно истинная формула исчисления предикатов, то ${\displaystyle \Phi }$ доказуема в исчислении предикатов.^[1]

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

Из тождественной истинности ${\displaystyle \Phi }$ получаем, что множество ${\displaystyle \{\neg \Phi \}}$ не имеет модели. Из теоремы о существовании модели следует, что ${\displaystyle \{\neg \Phi \}}$ противоречиво, то есть ${\displaystyle \neg \Phi \vdash }$ - теорема исчисления предикатов. По правилу вывода ${\displaystyle {\frac {\Gamma ,\neg \Phi \vdash }{\Gamma \vdash \Phi }}}$ получаем, что ${\displaystyle \Phi }$ доказуема.^[1]

См. также

• Теоремы Гёделя о неполноте
• Теорема о существовании модели

Примечания

Литература

• Ершов Ю.Л., Палютин Е.А. Математическая логика. — М.: Наука, 1987. — 336 с.

Это заготовка статьи по математической логике. Вы можете помочь проекту, дополнив её.

В другом языковом разделе есть более полная статья Gödel's completeness theorem (англ.). Вы можете помочь проекту, расширив текущую статью с помощью перевода. При этом, для соблюдения правил атрибуции, следует установить шаблон {{переведённая статья}} на страницу обсуждения, либо указать ссылку на статью-источник в комментарии к правке.

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