ЛОГИКА ПРЕДИКАТОВ ВЫСШИХ СТУПЕНЕЙ

— комплекс направлений в логике математической и основаниях математики, исследующий языки высших ступеней и логические исчисления высших ступеней. В основном, в такие языки, кроме индивидных переменных, входят предикатные переменные (одной или нескольких «ступеней» или «типов»). Их разрешается связывать кванторами, а также подставлять на места аргументов других предикатных переменных при выполнении определенных условий, налагаемых на типы переменных. Такие языки и связанные с ними исчисления возникли в связи с теоретико-типовым подходом к основаниям математики, предпринятым англ. учеными Б. Расселом (1872—1971), А. Уайтхедом (1861—1947) с целью построения основ математики, свободных от теоретико-множественных и логических парадоксов.

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

какое-нибудь мн-во, а —семейство мн-в, такое, что мн-во всех подмножеств декартова произведения Элементы мн-ва отношениями типа на А. (Всякое, напр., двухместное отношение R — отношение в обиходном матем. смысле — между элементами мн-ва А взаимоопределимо с мн-вом таким, что равносильно Отсюда ясно, что сформулированное выше определение понятия «отношение» уточняет обиходный матем. смысл термина «отношение». Отношения типа 0 на А — это элементы А; отношения типа (00) — двухместные отношения на А; отношения типа наборы подмножеств А, и т. п.

Формальный язык содержит символы логич. операторов (логич. связки и кванторы), равенство и для каждого типа т — последовательность переменных типа т. Выражения ВИДОВ атомарными ф-лами. Исходя из понятия атомарной ф-лы, определяют (обычным образом) понятия ф-лы и предложения. Ступенью наивысшая из ступеней входящих в нее переменных, увеличенная на единицу. Через обозначается фрагмент языка располагающий переменными лишь таких типов , что Этот фрагмент наз. языком ступени.

Пусть такое семейство мн-в, что для всякого типа Понятие выполнимости формулы на определяется по Тарскому, переменные типа интерпретируются как элементы Формула наз. истинной на если она выполняется на при всех значениях свободных переменных (принадлежащих соответствующим мн-вам ). По аналогии с исчислениями предикатов ступени строятся исчисления предикатов высших ступеней. Семейство правильным для данного исчисления, если на нем истинны все аксиомы этого исчисления, а каждое правило вывода сохраняет на нем истинность. Амер. логик Л. Генкин доказал, что всякая ф-ла исчисления предикатов высших ступеней, истинная на всех правильных (для этого исчисления) семействах, доказуема в этом исчислении.

Среди различных видов интерпретаций языков высших ступеней особый интерес представляют интерпретации, стандартные в следующем смысле. Говорят, что данная ф-ла стандартно выполняется на мн-ве А, если она выполняется на семействе где Формула стандартно истинна на А, если она истинна на Формула наз. стандартно выполнимой (общезначимой), если она стандартно выполнима (истинна) на некотором (всяком) непустом мн-ве (см. Тождественно истинная формула). Изучение вопросов, связанных со стандартными интерпретациями, предполагает достаточно содержательную теоретико-множественную базу. Является ли какая-либо ф-ла стандартно общезначимой, вообще зависит от положенной в основу множеств теории. Напр., свойство мн-ва быть вполне упорядочиваемым выразимо формулой ступени. Является ли эта ф-ла стандартно общезначимой, зависит от того, имеет ли место в этой теории множеств аксиома выбора. Формулы стандартно эквивалентными, если а. Р есть стандартно общезначимая формула. Говорят, что ф-ла Р логически, или стандартно, следует из если стандартно общезначима. Для исчисления предикатов ступени понятия логич. и дедуктивного следования совпадают в силу полноты этого исчисления. Из Гёделя теоремы о неполноте следует, что для исчислений высших ступеней понятие дедуктивного следования — более сильное: множество гёделевых номеров всевозможных кортежей этого исчисления таких, что Р логически следует из не только не является рекурсивно перечислимым, но не появляется ни в каком разумном расширении иерархия Клини — Мостовского (так что, в частности, исчисления предикатов высших ступеней не полны относительно общезначимости при стандартных интерпретациях, т. е. для стандартных интерпретаций упомянутая выше теорема Генкина не имеет места). Поэтому в исследованиях, относящихся к стандартным интерпретациям, приходится использовать преимущественно теоретико-множественные средства. Излагаемые ниже результаты относятся к стандартным интерпретациям и доказуемы в рамках теории мн-в Цермело — Френкеля. Для всякой ф-лы можно эффективно построить стандартно эквивалентную ей регулярную ф-лу той же ступени, т. е. такую ф-лу в предваренной форме, в которой нет квантора по переменной большей ступени, следующего за квантором по переменной меньшей ступени. Класс регулярных ф-л будет обозначаться через из монади-ческой, если типы связанных переменных в ней принадлежат мн-ву Для монадических предложений ступени проблемы выполнимости, общезначимости и проблема спектра (состоящая в отыскании характеризации классов мощностей всех мн-в, на которых предложения истинны) решаются эффективно. Положение меняется для ф-л высших ступеней: для всякой ступени можно эффективно построить стандартно эквивалентную ей монадическую формулу ступени; если то можно эффективно построить стандартно эквивалентную на бесконечных мн-вах монадическую ступени. Следовательно, применительно к бесконечным мн-вам выразительные возможности языка ступени те же, что и для его монадического фрагмента

Особое место класса ступени выявляется следующей теоремой: является классом сведения по выполнимости для т. е. существует эффективная процедура, переводящая всякую ф-лу в ф-лу из одновременно с нею выполнимую или невыполнимую.

Пусть наименьший из таких кардиналов что всякая выполнимая формула из выполняется на мн-ве мощности, не большей . В силу теоремы Лёвенгейма—Сколема Для кардипальтип равны и «необозримо» велики: они больше многих недостижимых и даже измеримых кардиналов (если таковые имеются). Это иоказывает, что уже проблемы семантики языка ступени вызывают необходимость рассмотрения очень больших кардиналов.

Моделью формулы всякая пара где А — непустое мн-во, ф-ция, определвнная на переменных свободно входящих в такая, что 1) выполняется при интерпретации каждой свободной переменной как а связанных переменных как всевозможных элементов Из приведенных результатов следует, что изучать общие свойства классов моделей для ступени (и даже, как можно показать, для ф-л вида (а), где а не содержит связанных предикатных, т. е. неиндивидных, переменных), так же трудно, как изучать свойства классов моделей для ф-л сколь угодно высоких ступеней. Отсюда ясна безнадежность поисков на традиционных путях сильных и общих теорем, относящихся к языку и подобных известным теоретикомодельным теоремам. В связи с этим приобретает интерес изучение семантики языков, промежуточных между языками ступеней, и некоторыхих модификаций, в частности, языков ступени с одноместными предикатными переменными, интерпретируемыми как конечные подмножества индивидов, языков, содержащих переменные, интерпретируемые как конечные последовательности индивидов, и языков, содержащих лишь индивидные переменные, но допускающих счетные конъюнкции и дизъюнкции. Один из таких промежуточных языков применяют в автоматов теории (см. Язык логический для задания автоматов).

Стандартно выполнимая ф-ла а из если для всякой ф-лы Р из общезначимо или из если из а. логически следует Стандартно выполнимая категоричной, если все ее модели (интерпретации) изоморфны. В предположении гёделевской аксиомы конструктивности для всякой стандартно выполнимой ф-лы из существует ее "-пополнение, являющееся категоричной ф-лой значит, для всякой ф-лы из ее -полнота равносильна категоричности). Эта теорема в некотором смысле двойственна гёделевской теореме неполноты, устанавливающей, в частности, что существует выполнимая ступени, не имеющая -пополнения. Вместе с тем, природа этих теорем одна и та же: достаточно богатые выразительные возможности языков (еще более усиливаемые аксиомой конструктивности), влекущие (в силу теоремы Тарского) неопределимость понятия истины для этих языков средствами самих этих языков. Вскрывая ограниченность (в этом «метасмысле») выразительных возможностей таких языков, теорема Тарского вскрывает и ограниченность дедуктивных возможностей связанных с ними исчислений, проявляющуюся как существование дедуктивно непополнимых формул.

Лит.: Бочвар Д. А. Об одном трехзначном исчислении и его применении к анализу парадоксов классического расширенного функционального исчисления. «Математический сборник. Новая серия», 1938, т. 4, в. 2; Бочвар Д. А. К вопросу о парадоксах математической логики и теории множеств. «Математический сборник. Новая серия», 1944, т. 15, в. 3; 3ыков А. А. Проблемы спектра в расширенном исчислении предикатов. «Известия АН СССР. Серия математическая», 1953, т. 17, № 1; Когаловский С. Р. К семантике теории типов. «Известия высших учебных заведений. Математика», 1966, № 1; Тагski A. Der Wahrheitsbegriff in den formalisierten Sprachen. «Studia Philosophica», 1936, y. 1;H ob inson A. Non-standard analysis. «Proceedings of the Royal Academy of Sciences». 1961, ser. A, v. 64; Аддисон Дж. Теория иерархий. В кн.: Математическая логика и ее применения. Пер. с англ. М., 1965; Fгаеnkе1 A. A., BarHillel Y. Foundations of set treory. Amsterdam, 1958.

С. P. Иогаловский.