Полнота

В математической логике — свойство, близкое к понятию максимального элемента в частично упорядоченном множестве. Термин "П." в математич. логике употребляется в контекстах вида: полное исчисление, полная теория (или полное множество аксиом), w-полная теория, полная в смысле Поста система аксиом, полное вложение одной модели в другую, полная формула полной теории и др. Одним из наиболее важных в гносеологич. отношении является понятие П. исчисления относительно данной семантики. Исчисление наз. полным, если всякая верная в семантич. смысле формула этого исчисления выводима в нем. При этом понятие выводимости должно быть эффективным, т. е. имеются набор правил и инструкция их применения, позволяющая строить выводы, причем есть алгоритм, отличающий выводы от невыводов. Понятие семантически верной формулы, наоборот, формулируется, как правило, с использованием неэффективных понятий, с помощью кванторов всеобщности по бесконечным и даже несчетным совокупностям. В теоремах о полноте классического и интуиционистского исчислений предикатов П. понимается в указанном смысле. В случае классич. исчисления семантически верными считаются те формулы языка узкого исчисления предикатов (УИП), к-рые истинны во всех моделях для рассматриваемого языка. В интуиционистском случае семантически верными считаются формулы, истинные во всех Крипке моделях. Понятие истинной в данной модели формулы также использует кванторы по бесконечным областям (если модель бесконечна) как в классическом, так и в интуиционистском случаях. Иногда рассматривают исчисления, не удовлетворяющие требованию эффективности. С понятием П. исчисления тесно связано понятие полной теории. Теорией (точнее, элементарной теорией) наз. произвольное множество Тзамкнутых формул языка УИП. Непротиворечивая теория Тназ. полной, если множество всех следствий из Тв клас-сич. исчислении предикатов является максимальным непротиворечивым множеством, т. е. добавление к Тлюбой замкнутой невыводимой из Тформулы позволяет вывести любую формулу. В этом определении не предполагается, что множество Тзадано эффективно, так что понятие вывода становится тоже неэффективным. П. теории Тэквивалентна следующему условию: для всякой замкнутой формулы j имеет место в точности одно из двух утверждений — либо j выводима ив Т, либо выводима из Т. Если дана какая-то модель Мязыка УИП, то возникает семантич. понятие формулы, истинной в модели М. Теория Тназ. полной относительно М, если в классич. исчислении предикатов, пополненном формулами из Т, выводимы в точности все истинные в Мформулы. Между понятиями П. теории и П. относительно Мимеется следующая связь. Теория Тполна тогда и только тогда, когда существует модель М, относительно к-рой она полна. Модель Мназ. моделью теории Т, если все формулы из Тистинны в М. Достаточный признак П. теории: если все модели нек-рой мощности теории Тизоморфны, то теория Тполна. Обратное не всегда верно. Понятие П. теории находит применение в вопросах разрешимости теорий из-за следующего свойства полных теорий: если теория Тполна и множество Тконечно или даже рекурсивно перечислимо, то существует алгоритм, распознающий по любой формуле j выводима она или нет. Если не требовать эффективного задания множества Т, то всякую теорию можно пополнить, т. е. расширить добавлением новых аксиом до полной. При наличии требования эффективности дело обстоит не так, как показывает теорема Гёделя о неполноте арифметич. исчислений. Теория Т' наз. расширением теории Т, если всякая формула, выводимая из Т, будет выводима из Т'. Пусть Т — непротиворечивая рекурсивно перечислимая теория. Теория Тназ. эффективно неисполнимой, если по всякому рекурсивно перечислимому непротиворечивому расширению Т' теории Тможно эффективно найти формулу j, формально неразрешимую в Т', т. е. такую, что ни j, ни не выводимы из Т'. Теорема Гёделя о неполноте утверждает, что нек-рая конкретная арифметич. теория Q, имеющая конечное число аксиом, эффективно не пополнима. Из этой теоремы вытекает неполнота относительно стандартной модели натуральных чисел любого арифметич. исчисления, удовлетворяющего требованию эффективности. Арифметич. теория Тназ. w-полной, если из того, что в Твыводимы все формулы вида (*) следует выводимость в Тформулы . Из доказательства теоремы Гёделя о неполноте следует, что существуют теории, не являющиеся w-полными, и даже такие, в к-рых выводима бесконечная серия формул (*), а также формула , и тем не менее противоречия вывести нельзя. Такая теория наз. w -противоречивой. Непротиворечивая система аксиом наз. полной в смысле Поста, если добавление к ней любой схемы аксиом либо не расширяет запаса выводимых формул, либо превращает систему в противоречивую. Напр., аксиоматика классич. исчисления высказываний полна в смысле Поста, а интуиционистского исчисления высказываний не полна. Лит.:[1] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; [2] Кейслер Г., Чэн Ч. Ч., Теория моделей, пер. с англ., М., 1977; [3] Шенфилд Д ж.. Математическая логика, пер. с англ., М., 1975; [4] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [5] Фейс Р., Модальная логика, пер. с англ., М., 1974 (Дополнения). В. Н. Гришин.