Математическая энциклопедия - гёделя теорема о полноте

утверждение о полноте классического исчисления предикатов: всякая предикатная формула, истинная на всех моделях, выводима (по формальным правилам классич. исчисления предикатов). Г. т. о п. показывает, что множество выводимых формул этого исчисления в определенном смысле максимально: оно содержит все чисто логические законы теоретико-множественной математики. Доказательство К. Гёделя [1] дает способ построения контрмодели (т. е. модели для отрицания) всякой формулы А, невыводимой в Генцена формальной системе без сечения. Имеются также доказательства, основанные на расширениях систем формул до максимальных, а также доказательства, использующие ал-гебраич. методы. Теорема вместе с доказательством обобщается на исчисление с равенством. Другое направление обобщение на произвольные множества формул: каждое непротиворечивое множество формул обладает моделью (множество Мнепротиворечиво, если для любых невыводимо ). Гёделевское доказательство дает для непротиворечивого множества формул модель, элементами к-рой являются термы. Такие модели составляют исходный пункт во многих исследованиях по метаматематике теории множеств. Другое приложение моделей из термов теорема Лёвенхейма Сколема: если счетное множество формул имеет какую-то модель, то оно имеет счетную модель. Само гёделевское доказательство проводится средствами теории множеств без аксиомы бесконечности, т. е. средствами арифметики. Отсюда получается конструктивная форма Г. т. о п. (лемма Бернайса): для каждой предикатной формулы Аможно указать такую подстановку арифметич. предикатов вместо предикатных переменных, что выводима в формальной арифметике; здесь арифметич. формула, выражающая, что Авыводима. Таким образом, для выводимости Адостаточна ее истинность на той модели, к-рую задает подстановка Лемма Бернайса применяется для построения моделей формальной системы в системе , если в доказана непротиворечивость .

Из Г. т. о п. можно извлечь также теорему об устранимости сечения (см. Генцена формальная система).и различные теоремы отделения, напр.: если формула, не содержащая знака равенства, выводима средствами исчисления предикатов с равенством, то она выводима в чистом исчислении предикатов; если предикатная формула выводима в арифметике со свободными предикатными переменными, то она выводима в исчислении предикатов.

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

Лит.:[1] Godе1 К., "Monatshefte fur Math, und Phys.", 1930, Bd 37, S. 349-60; [2] Hовиков П. С., Элементы математической логики, М., 1959; [3] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957. Г. Е. Минц.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985