УДК 512.532.2

Б. М. Верников

О многообразиях полугрупп, на свободных объектах которых почти все вполне инвариантные конгруэнции слабо перестановочны, 635—649.

Говорят, что многообразие полугрупп имеет индекс, не превосходящий 2, если все нильполугруппы из этого многообразия являются полугруппами с нулевым умножением. Дается описание многообразий полугрупп индекса, не превосходящего 2, на свободных объектах которых любые две вполне инвариантные конгруэнции, содержащиеся в наименьшей полурешеточной конгруэнции, слабо перестановочны, а также многообразий полугрупп индекса, не превосходящего 2, все подмногообразия которых обладают указанным свойством.

Ключевые слова: многообразие полугрупп, нильполугруппа, слабо перестановочные конгруэнции, вполне инвариантная конгруэнция.

Адрес автора: Верников Борис Муневич, матем.-механ. ф-т, Уральский гос. университет, пр. Ленина, 51, г. Екатеринбург, 620083, Россия. e-mail: Boris.Vernikov@usu.ru

УДК 510.53+510.67

С. С. Гончаров, Б. Хусаинов

Сложность теорий вычислимых категоричных моделей, 650—665.

М. Лерман и Дж. Шмерл дали некоторые достаточные условия для существования вычислимых моделей счетно категоричных арифметических теорий. Более точно, они показали: если $T$ — счетно категоричная арифметическая теория, причем множество всех ее предложений, начинающихся с квантора существования и имеющих не более $n+1$ чередующейся группы однотипных кванторов, лежит в классе $\Sigma_{n+1}^0$ для любого $n$, то теория $T$ имеет вычислимую модель. Дж. Найт улучшила этот результат, добавив условие определенной равномерности и опустив требование арифметичности теории $T$. Однако, все известные примеры теорий $\aleph_0$-категоричных вычислимых моделей имеют низкий уровень алгоритмической сложности и было неизвестно, существуют ли теории, которые бы удовлетворяли условиям, установленным М. Лерманом и Дж. Шмерлом, для достаточно больших $n$. В этой работе строятся такие примеры.

Ключевые слова: вычислимая модель, счетно категоричная теория.

Адреса авторов: Гончаров Сергей Савостьянович, Институт математики СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, Россия. Тел.: (383-2) 33-28-94. e-mail: gonchar@math.nsc.ru

Хусаинов Бахадыр, Department of Computer Science, University of Auckland, Auckland, New Zealand. Phone: (219)-631-63-55. e-mail:bmk@nd.edu

УДК 510.53

У. Калверт, Д. Камминс, Дж. Ф. Найт, С. Миллер

Сравнение классов конечных структур, 666—701.

Дается сравнение классов структур с помощью понятия вычислимого вложения, которое является частичным порядком на классах структур. Внимание в основном (но не исключительно) сосредоточено на классах конечных структур. Формулируется ряд проблем.

Ключевые слова: вычислимое вложение, конечное простое поле, конечный линейный порядок, конечномерное векторное пространство над полем рациональных чисел, линейный порядок.

Адреса авторов: Calvert, Wesley, Mathematics Department, University of Notre Dame, 255 Hurley, Notre Dame, Indiana 46556, USA. e-mail: calvert.2@nd.edu

Cummins, Desmond, Mathematics Department, University of Illinois at Urbana-Champaign, 273 Altgeld Hall MC-382, 1409 W. Green Street, Urbana, Illinois 61801, USA. e-mail:dcummin2@uiuc.edu

Knight, Julia F., Mathematics Department, University of Notre Dame, 255 Hurley, Notre Dame, Indiana 46556, USA. e-mail: knight.1@nd.edu

Miller, Sara, Mathematics Department, University of Notre Dame, 255 Hurley, Notre Dame, Indiana 46556, USA. e-mail: smiller9@nd.edu

УДК 510.53+512.562

Н. Т. Когабаев, О. В. Кудинов, Р. Миллер

Вычислимая размерность $I$-деревьев бесконечной высоты, 702—730.

Изучаются вычислимые деревья с выделенным начальным поддеревом (кратко, $I$-деревья). Доказывается, что все $I$-деревья бесконечной высоты не являются вычислимо категоричными, и, более того, они имеют эффективно бесконечную вычислимую размерность.

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

Адреса авторов: Когабаев Нурлан Талгатович, Институт математики СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, Россия. Тел.: (383-2) 33-28-94. e-mail: kogabaev@math.nsc.ru

Кудинов Олег Викторович, Институт математики СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, Россия. Тел.: (383-2) 33-31-97. e-mail: kud@math.nsc.ru

Miller, Russell, Department of Mathematics, Cornell University, Ithaca, NY 14853, USA. Phone: (607) 255-48-92. e-mail: russell@math.cornell.edu

УДК 512.57

А. Г. Пинус

Об элементарной эквивалентности производных структур свободных полугрупп, унаров и групп, 731—748.

Рассматриватся отношение элементарной эквивалентности на производных структурах свободных алгебр ряда многообразий.

Ключевые слова: элементарная эквивалентность, свободная алгебра, группа, полугруппа, унар.

Адрес автора: Пинус Александр Георгиевич, ул. Революции, д. 10, кв. 15, г. Новосибирск, 630099, Россия. e-mail: algebra@nstu.nsk.su

УДК 510.5

В. Г. Пузаренко

О теореме Левенгейма–Сколема–Мальцева для $\mathbb{HF}$-структур, 749—758.

Изучается проблема существования элементарных расширений вида $\mathbb{HF}({\mathfrak M})$ у наследственно конечных надстроек. При этом решается проблема существования у теории некоторой наследственно конечной надстройки моделей вида $\mathbb{HF}({\mathfrak M})$ сколь угодно большой мощности. Показывается существование числа Ханфа. В счетном случае дается точная оценка.

Ключевые слова: наследственно конечная надстройка, число Ханфа.

Адрес автора: Пузаренко Вадим Григорьевич, Институт математики СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, Россия. e-mail: vagrig@math.nsc.ru