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

Утверждение о полноте классического исчисления предикатов: всякая предикатная формула, истинная на всех моделях, выводима (по формальным правилам классич. исчисления предикатов). Г. т. о п. показывает, что множество выводимых формул этого исчисления в определенном смысле максимально: оно содержит все чисто логические законы теоретико-множественной математики. Доказательство К. Гёделя [1] дает способ построения контрмодели (т. е. модели для отрицания) всякой формулы А, невыводимой в Генцена формальной системе без сечения. Имеются также доказательства, основанные на расширениях систем формул до максимальных, а также доказательства, использующие ал-гебраич. методы. Теорема вместе с доказательством обобщается на исчисление с равенством. Другое направление — обобщение на произвольные множества формул: каждое непротиворечивое множество формул обладает моделью (множество Мнепротиворечиво, если для любых невыводимо ). Гёделевское доказательство дает для непротиворечивого множества формул модель, элементами к-рой являются термы. Такие модели составляют исходный пункт во многих исследованиях по метаматематике теории множеств. Другое приложение моделей из термов — теорема Лёвенхейма — Сколема: если счетное множество формул имеет какую-то модель, то оно имеет счетную модель. Само гёделевское доказательство проводится средствами теории множеств без аксиомы бесконечности, т. е. средствами арифметики. Отсюда получается конструктивная форма Г. т. о п. (лемма Бернайса): для каждой предикатной формулы Аможно указать такую подстановку арифметич. предикатов вместо предикатных переменных, что выводима в формальной арифметике; здесь — арифметич. формула, выражающая, что Авыводима. Таким образом, для выводимости Адостаточна ее истинность на той модели, к-рую задает подстановка Лемма Бернайса применяется для построения моделей формальной системы в системе , если в доказана непротиворечивость . Из Г. т. о п. можно извлечь также теорему об устранимости сечения (см. Генцена формальная система).и различные теоремы отделения, напр.: если формула, не содержащая знака равенства, выводима средствами исчисления предикатов с равенством, то она выводима в чистом исчислении предикатов; если предикатная формула выводима в арифметике со свободными предикатными переменными, то она выводима в исчислении предикатов. Г. т. о п. допускает (при соответствующем обобщении понятия модели) обобщение на неклассич. исчисления: интуиционистские, модальные и т. п. Лит.:[1] Godе1 К., "Monatshefte fur Math, und Phys.", 1930, Bd 37, S. 349-60; [2] Hовиков П. С., Элементы математической логики, М., 1959; [3] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957. Г. Е. Минц.

Источник: Математическая энциклопедия на Gufo.me