Полнота

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

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


Значения в других словарях

  1. Полнота — Свойство научной теории, характеризующее достаточность для каких-либо определённых целей её выразительных и (или) дедуктивных средств. Один из аспектов понятия П. — т. н. функциональная П. (ф. Большая советская энциклопедия
  2. полнота — -ы, ж. 1. Свойство по прил. полный (в 1, 4, 5 и 7 знач.). Полнота счастья. Полнота власти. Полнота текста. Полнота коллекции. Полнота исследования. Полнота рук. Малый академический словарь
  3. ПОЛНОТА — ПОЛНОТА — англ. plenitude/completeness; нем. Fulle/Vollstandigkeit. Свойство формальных систем, характеризующее достаточность для к.-л. определенных целей. Социологический словарь
  4. полнота — Полн/от/а́. Морфемно-орфографический словарь
  5. полнота — орф. полнота, -ы Орфографический словарь Лопатина
  6. полнота — • абсолютная ~ • исчерпывающая ~ • максимальная ~ • наибольшая ~ Словарь русской идиоматики
  7. полнота — см. >> избыток, обилие Словарь синонимов Абрамова
  8. полнота — 1. наличие чего-нибудь в достаточной степени, высшая степень насыщенности чем-нибудь; 2. единица измерения внутри одного размера (одежды, обуви). Большой бухгалтерский словарь
  9. полнота — ПОЛНОТА — ПУСТОТА Полнота жизни — пустота жизни. ○ Из летка не пахнет, как прежде, спиртовым, душистым запахом меда и яда, не несет оттуда теплом полноты, а с запахом меда сливается запах пустоты и гнили. Л. Толстой. Война и мир. Словарь антонимов русского языка
  10. полнота — ПОЛНОТА, ы, ж. 1. Наличие чего-н. в достаточной степени, высшая степень насыщенности чем-н. П. власти. Исчерпывающая п. в подборе фактов. От полноты чувств или от полноты души (от избытка чувств, как бы наполняющих всего человека). Толковый словарь Ожегова
  11. полнота — ПОЛНОТ’А, полноты, мн. нет, ·жен. 1. Состояние чего-нибудь наполненного совершенно, до краев (·редк. ). «До полноты не доливай.» Даль. 2. Полная мера, полный состав, предельное потребное количество, исчерпывающая достаточность. Толковый словарь Ушакова
  12. полнота — ПОЛНОТА -ы; ж. 1. Наличие чего-л. в достаточной степени, высшая степень проявления чего-л., насыщенности чем-л. П. власти, ответственности, прав. П. жизни, счастья, чувств, сил. П. ответа, текста, коллекции, исследования. Толковый словарь Кузнецова
  13. ПОЛНОТА — ПОЛНОТА — в логике и математике — достаточность выразительных или дедуктивных средств какой-либо научной теории или исчисления для описания (характеристики, предсказания, вывода) всех реальных свойств и отношений предполагаемой модели этой теории или исчисления. Большой энциклопедический словарь
  14. полнота — полнота ж. 1. Наполненность, достаточное наличие чего-либо. 2. Полная мера, полный состав, предельное количество. || Исчерпанность, обстоятельность. || Насыщенность, содержательность. 3. перен. Высшая степень чего-либо. 4. Тучность, толщина тела. Толковый словарь Ефремовой
  15. полнота — См. полный Толковый словарь Даля