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

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

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

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

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

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

См. также

Примечания

Ершов, 1987, с. 139.

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_ea4147cbe902ae28-1] Ершов, 1987, с. 139.