ЭЛЕМЕНТАРНЫЕ ТЕОРИИ.

Э. т. класса К алгебраических систем сигнатуры наз. совокупность всех замкнутых формул логики предикатов первой ступени сигнатуры Q, истинных на всех системах из класса К. Если класс К состоит из одной системы 21, Э. т. класса К наз. Э. т. системы 21. Две алгебр. системы одной сигнатуры наз. элементарно эквивалентными, если их Э. т. одинаковые. Э. т. класса К наз. полной, если цюбые две -системы элементарно эквивалентны. Под Э. т. сигнатуры Q понимается Э. т. какого-то класса алгебр, систем сигнатуры Q. Равносильное определение: Э. т. сигнатуры Q — это непротиворечивая совокупность замкнутых формул сигнатуры Q логики предикатов первой ступени, замкнутая относительно следствий. Э. т. Т сигнатуры рекурсивно (конечно) аксиоматизируемой, если существует такая рекурсивная (конечная) совокупность , что Т есть множество всех следствий из которые являются формулами логики предикатов первой ступени сигнатуры Если 2 — совокупность замкнутых формул логики предикатов первой ступени сигнатуры Q, через обозначается класс всех моделей для S, т. е. всех алгебр, систем сигнатуры Q, на которых истинны все формулы из 2. Класс К алгебр, систем сигнатуры аксиоматизируемым, если существует такая совокупность S замкнутых формул сигнатуры Q, что . В этом случае совокупностью аксиом для К. Класс К тогда и только тогда аксиоматизируем, когда . Э.т. сигнатуры разрешимой, если существует алгоритм, который по произвольной замкнутой формуле логики предикатов первой ступени сигнатуры Q определяет, принадлежит эта формула теории Т или нет. Напр., класс плотно линейно

упорядоченных множеств без наименьшего и наибольшего элементов аксиоматизируем, его Э. т. разрешима, любые две системы из этого класса элементарно эквивалентны, значит, Э. т. этого класса полна; кроме этого, Э. т. рассматриваемого класса конечно аксиоматизируема. Класс конечных циклических групп не является аксиоматизируемым, однако его Э. т. разрешима и, значит, рекурсивно аксиоматизируема. Имеются примеры конечно аксиоматизируемых неразрешимых Э. т. Такими являются Э. т. групп, колец, полей и др. Однако полная рекурсивно аксиоматизируемая теория обязательно разрешима. Поэтому для доказательства разрешимости рекурсивно аксиоматизируемой теории достаточно доказать, что эта теория полна. Известно несколько методов доказательства полноты.

Метод категоричности сводится к замечанию, что Э. т., категоричная в некоторой бесконечной мощности и не имеющая конечных моделей, обязательно полна. Теория наз. категоричной в мощности а, если все ее модели мощности а изоморфны. Напр., Э. т. алгебр, замкнутых полей фиксированной характеристики рекурсивно аксиоматизируема и категорична в каждой несчетной мощности, а конечных моделей не имеет. Поэтому эта теория полна в разрешима. В частности, разрешима Э. т. поля комплексных чисел. Были получены необходимые и достаточные условия для того, чтобы полная теория, имеющая бесконечную модель, была категорична в счетной мощности. Говорят, что две формулы той же сигнатуры, что и сигнатура теории Т, эквивалентны в теории Т, если эти формулы имеют одинаковые свободные переменные и для любой модели 91 теории Т и любого способа приписывания в качестве значепвй этих свободных переменных элементов модели 91, либо обе формулы одновременно истинны при этих значениях неизвестных, либо обе они ложны. Условия счетной категоричности: для каждого существует конечное число формул с свободными переменными такое, что каждая формула соответствующей сигнатуры со свободными переменными эквивалентна в теории Т одной из этих формул. Но наиболее впечатляющий результат, полученный до сих пор при изучении категоричных теорий, — это следующая теорема: полная теория конечной или счетной сигнатуры, категоричная в одной несчетной мощности, категорична и во всякой другой несчетной мощности. Итак, метод категоричности для доказательства разрешимости сводится к доказательству категоричности рассматриваемой теории.

Из более глубоких соображений используют метод модельной полноты. Система сигнатуры элементарной подсистемой системы той же сигнатуры, если является подсистемой системы и для всякой формулы логики предикатов первой ступени сигнатуры Q (ее свободными переменными и всяких из из истинности в следует истинность модельно полной, если для любых из того, что является подсистемой , следует, что является элементарной подсистемой . Оказывается, что модельно полная теория, имеющая минимальную модель, является полной. Минимальной наз. такая модель Э. т., которая изоморфно вкладывается в любую другую модель этой Э. т. Полной является и такая модельно полная теория, все модели которой универсально эквивалентны. Универсально эквивалентными наз. такие алгебр. системы сигнатуры Q, на которых истинны одни и те же универсальные формулы, а универсальной наз. формула в предваренной форме, не содержащая кванторов существования. Используя технику модельной полноты, можно доказать полноту и разрешимость теории вещественно замкнутых полей, в частности поля действительных чисел и некоторых других Э. т. Однако до 1965 почти не было найдено др. примеров разрешимых Э. т. классов полей, кроме отмеченных выше. В 1965 были открыты серии классов полей с разрешимой Э. т., в частности, была доказана разрешимость Э. т. поля -адических чисел. Важным является также результат о разрешимости Э. т. конечных полей и полей вычетов. Среди результатов, не относящихся к полям, следует упомянуть теорему о разрешимости Э. т. упорядоченных абелевых групп и теорему о разрешимости Э. т. абелевых групп.

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

Теорию неразрешимых Э. т. разработал амер. матем. А. Тарский в 40-х годах, хотя неразрешимость логики предикатов первой ступени и неразрешимость арифметики натуральных чисел были доказаны несколько раньше. Осн. инструмент в теории Тарского — метод интерпретаций. Э. т. Т наз. существенно неразрешимой, если каждая теория Т той же сигнатуры неразрешима. Теория Т сигнатуры относительно элементарно определимой или относительно интерпретируемой в теории сигнатуры Q, если существуют такие формулы сигнатуры Q, что для каждой или соответственно для некоторой модели 91 теории Т можно найти такую

модель теории которая обладает следующим свойством. Можно найти такие , что множество истинно в вместе с так определенным на А предикатом Р, что истинно тогда и только тогда, когда истинно в , образует алгебр, систему, изоморфную системе . Это определение распространяется и на теории Т произвольной конечной сигнатуры. Оказывается, что если существенно неразрешимая конечно аксиоматизируемая теория Т относительно интерпретируема в теории то тоже неразрешима. Возможность эффективного применения этой теоремы Тарского связана с существованием конечно аксиоматизируемой существенно неразрешимой подтеории арифметики натуральных чисел. Этим методом доказана неразрешимость Э. т. многих классов колец, поля рациональных чисел и др. классов полей.

Большой интерес вызвали теории классов конечных систем. Первый результат — неразрешимость Э. т. класса конечных моделей. Важен результат сов. математика А. И. Мальцева (1909—67) о неразрешимости Э. т. конечных групп. Для изучения Э. т. классов конечных систем и в некоторых других случаях теорема Тарского едва ли может быть полезна. Был предложен новый метод. Скажем, что теория Т сигнатуры Q неотделима, если не существует рекурсивного множества формул сигнатуры Q, содержащего все тождественные истинные замкнутые формулы сигнатуры Q и содержащегося в Т. Оказывается, что если неотделимая теория Т относительно элементарно определима в теории то теория тоже неотделима. Это замечание позволило доказать неотделимость многих теорий. В качестве Т при этом удобно брать Э. т. всех конечных бинарных предикатов, Э. т. конечных симметричных бинарных предикатов и подобные Э. т.

Лит.: Ершов Ю. Л. [и др.]. Элементарные теории. «Успехи математических наук», 1965, т. 20, № 4. М. А. Тайцлин.