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

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

Шаблон:Рамка Формула является выводимой в исчислении предикатов первого порядка тогда и только тогда, когда она общезначима (истинна в любой интерпретации при любой подстановке). Шаблон:Конец рамки

Иными словами, если $\mathrm{\Phi }$ — тождественно истинная формула исчисления предикатов, то $\mathrm{\Phi }$ доказуема в исчислении предикатов.Шаблон:Sfn

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

Из тождественной истинности $\mathrm{\Phi }$ получаем, что множество $\{\mathrm{\neg }\mathrm{\Phi }\}$ не имеет модели. Из теоремы о существовании модели следует, что $\{\mathrm{\neg }\mathrm{\Phi }\}$ противоречиво, то есть $\mathrm{\neg }\mathrm{\Phi }⊢$ - теорема исчисления предикатов. По правилу вывода $\frac{\mathrm{\Gamma },\mathrm{\neg }\mathrm{\Phi }⊢}{\mathrm{\Gamma }⊢\mathrm{\Phi }}$ получаем, что $\mathrm{\Phi }$ доказуема.Шаблон:Sfn

См. также

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

Литература

• Шаблон:Книга