Akademik

свойство формальной системы (исчисления), характеризующее достаточность его дедуктивных средств с т. зр. нек-рых фиксированных критериев (содержательных или формальных). В зависимости от характера выбранного критерия приходят к той или иной модификации понятия П. д. (эти различные модификации обозначают различными терминами, прямо или косвенно указывающими на выбранный критерий, так что эпитет "дедуктивная" при характеристике родового понятия полноты, как правило, опускают, поскольку нет опасности смешения с др. понятиями, в частности с понятием полноты функциональной). Содержательным критериям П. д. может быть придана как положительная, так и отрицательная форма. В первом случае имеется в виду, что система полна, если ее постулаты (правила преобразования) дают все, что нужно для нек-рой цели. Если, напр., задано нек-рое свойство формул рассматриваемой системы (или к.-л. их интерпретация), то система наз. полной по отношению к данному свойству (или и н т е р п р е т а ц и и), если все формулы, обладающие данным свойством (или соответственно выражающие предложения, истинные при данной интерпретации), доказуемы в этой системе. Отрицательные формулировки критериев полноты указывают на нек-рый нежелательный результат, к-рый наступает, если к полной системе формул присоединить недоказуемую в этой системе формулу. Простейшим примером такого нежелательного результата может служить противоречивость расширенной таким путем системы.

Поскольку указанные критерии П. д. связаны с нек-рыми с е м а н т и ч е с к и м и понятиями (истинностью, интерпретациями и т.п.), получающиеся на их основе понятия также носят семантич. характер. Однако в ряде случаев такого рода критериям удается придать чисто с и н т а к с и ч е с к у ю (см. Синтаксис в логике) формулировку и, т.о., перейти от понятия семантич. полноты к т.н. формальной ("синтаксич.") полноте. Примером понятия формальной полноты может служить уже упомянутое свойство формальной системы, заключающееся в том, что присоединение к ней недоказуемой в ней формулы этой системы в качестве аксиомы (или – если первоначальная система строилась с помощью схем аксиом – в качестве схемы аксиом) нарушает ее (простую) непротиворечивость. Это, вообще говоря, более сильное по сравнению со свойством полноты о т н о с и т е л ь н о (тождественной) и с т и н -н о с т и (к-рую часто наз. полнотой в ш и р о к о м с м ы с л е) понятие наз. также полнотой в узком смысле, или абсолютной полнотой. [Если же в этом случае непротиворечивость понимается в смысле определения Э. Поста (1921; тогда же им была установлена П. д. исчисления высказываний), т.е. как недоказуемость ф-лы f (где f – пропозициональная переменная), то приходят к понятию полноты в с м ы с л е П о с т а.]

Понятие П. д. носит существенно различный характер для разных категорий формальных систем. Если, напр., понятие П. д. (в широком смысле) для исчисления высказываний может быть охарактеризовано как синтаксич. понятие в т.н. финитных терминах (см. Метатеория), то для предикатов исчисления соответствующее понятие полноты о т н о с и т е л ь н о п р о и з в о л ь н о й интерпретаци и пред- метной области оказывается уже существенно неконструктивным (не выражаемым в терминах финитизма), так что установление П. д. в широком смысле для исчисления предикатов (К. Гёдель, 1930) выходит за рамки метаматематики в гильбертовском смысле. (В узком смысле исчисление предикатов неполно.)

Для прикладных логико-матем. исчислений [т.е. для систем, содержащих предметные и (или) предикатные константы], напр. для формальной арифметики, вводится понятие т.н. п р о с т о й полноты: система наз. просто полной, если каждая ее замкнутая формула является формально разрешимой (т.е. доказуемой или опровержимой – см. Неразрешимая формула), и просто неполной в противном случае. Если такая система непротиворечива по отношению к к.-н. интерпретации, то ее простая полнота и полнота по отношению к данной интерпретации являются эквивалентными понятиями. Если любое непротиворечивое усиление (расширение) формальной системы (т.е. система с тем же алфавитом и правилами образования формул, в к-рой доказуема всякая формула исходной системы) (просто) неполно, то такая система наз. непополнимо й. Непополнимость аксиоматич. арифметики, доказанная К. Гёделем, – один из принципиальнейших результатов в области оснований математики, установивший пределы возможности как гильбертовской концепции формализации математики, так и метода формализации вообще (о его гносеологич. значении см. Метод аксиоматический, Метатеория, Формализация).

Наряду с упомянутыми понятиями П. д. и их многочисл. модификациями в математической логике большую роль играет понятие т.н. ω - п о л н о т ы (А. Тарский, 1933). Формальная система, среди термов к-рой имеются обозначения для натуральных чисел, наз. ω-полной, если для каждой ее формулы φ(x) со свободной переменной х из доказуемости всех формул φ(0), φ(1), φ(2), ... следует доказуемость формулы ∀хφ(х); в противном случае система наз. ω-неполной. Понятие ω-полноты существенно сильнее понятия (простой) полноты: существуют полные, но ω-неполные системы. Разумеется, присоединение к системе "нефинитного" правила бесконечной индукции в качестве постулированного правила вывода приводит к эквивалентности понятий полноты и ω-полноты.

Понятие формальной полноты для т.н. элементарных теорий, т.е. для теорий, основанных на исчислении предикатов первого порядка с равенством и включающих конечное число аксиом, совпадает с понятием категоричности (см. Категоричность системы аксиом): все модели полной элементарной теории изоморфны (см. Изоморфизм).

Различные варианты понятия полноты определяются также для отд. классов формул, в т.ч. специально для систем постулатов (нелогич. аксиом).

См. также Полнота, Предикатов исчисление.

Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957, § 29, 37, 42, 72 (есть библ.); Чёрч Α., Введение в математическую логику, пер. с англ., т. 1, М., 1960, §18, 32, 54, 55 (есть библ.); Новиков П. С., Элементы математической логики, М., 1959, гл. 2, § 10, гл. 3, § 7, гл. 4, §6, 17, 19; Φренкель Α., Бар-Хиллел И., Основания теории множеств, пер. с англ., М., 1966, гл. 5, § 4 (есть библ.); Гильберт Д., Аккерман В., Основы теоретической логики, пер. с нем., М., 1947, гл. 1, § 13, гл. 3, § 10; Гудстейн Р. Л., Математическая логика, пер. с англ., М., 1961, гл. 1, 2, 4.