Теоре́ма Гёделя о полноте́ исчисле́ния предика́тов является одной из фундаментальных теорем математической логики: она устанавливает однозначную связь между логической истинностью высказывания и его выводимостью в логике первого порядка. Впервые эта теорема была доказана Куртом Гёделем в 1929.
Формула является выводимой в исчислении предикатов первого порядка тогда и только тогда, когда она общезначима (истинна в любой интерпретации при любой подстановке).
Иными словами, если — тождественно истинная формула исчисления предикатов, то доказуема в исчислении предикатов.
Доказательство
Из тождественной истинности получаем, что множество не имеет модели. Из теоремы о существовании модели следует, что противоречиво, то есть - теорема исчисления предикатов. По правилу вывода получаем, что доказуема.
См. также Теоремы Гёделя о неполноте Теорема о существовании модели
Примечания
Литература
Категория:Математическая логика Гёделя о полноте Категория:Появились в 1929 году Гёделя о неполноте Категория:Теория доказательств Гёделя