УДК 517.11:518.5

В. В. Вьюгин

О дискретных классах рекурсивно перечислимых множеств, 243—256.

Как известно, понятие дискретного семейства множеств предполагает наличие некоторого, класса конечных множеств, определенным образом связанного с исходным семейством. Если этот класс предположить строго вычислимым, получим определение эффективно дискретного семейства (финитно разделяющегося по А. И. Мальцеву). Назовем семейство слабо эффективно дискретным, если указанный класс конечных множеств вычислим. В заметке доказывается, что всякий вычислимый слабо эффективно дискретный класс имеет позитивную нумерацию, строится пример вычислимого дискретного, но не слабо эффективно дискретного класса, обладающего позитивной нумерацией. В заключение доказывается, что минимальная нумерация бесконечного дискретного семейства перечислимых множеств эквивалентна нумерации, в которой каждое конечное множество имеет конечное множество номеров.

УДК 517.11:518.5

A. Н. Дёгтев

Наследственные множества и табличная сводимость, 257—269.

Доказано, что каждая тьюрингова степень, содержащая гипериммунное (соответственно, р.п. нерекурсивное) множество, содержит счётное число попарно $tt$-несравнимых (р.п.) множеств. Замечено, что простое негиперпростое множество $tt$-несводимо к р.п. множеству с ретрассируемым дополнением, а точная нижняя грань $tt$-степеней двух р.п. множеств с ретрассируемыми дополнениями различных тьюринговых степеней есть рекурсивная $tt$-степень.

Выяснены также некоторые свойства наследственных множеств. В частности, если $A$ - наследственное множество и $\overline{A}$ - дополнение $A$, то

1) $A$ простое $\Longrightarrow$ $\overline{A}$ интерсводимое;

2) $\overline{A}$ негипергипериммунное;

3) $\overline{A}$ регрессивное $\Longrightarrow$ $A\in\Pi^{0}_{1}\cup \Sigma^{0}_{1}$.

УДК 51.01:518.5

B. В. Козьминых

О представлении частично рекурсивных функций в виде суперпозиций, 270—294.

Рассматривается следующая ситуация: одноместные частично рекурсивные функции строятся из одноместных примитивно рекурсивных функций и их обращений при помощи операции суперпозиции (рассмотрены и некоторые известные классы функций, более узкие, чем класс всех примитивно рекурсивных функций). В частности, доказано одно утверждение о представлении одноместных общерекурсивных функции в виде $AB^{-1}C$, где $B$ - перестановка и $A$ и $C$ фиксированы (перестановками называются функции, взаимно однозначно отображающие множество всех неотрицательных целых чисел на него же; $AB^{-1}C$ - это функция отображающая $x$ в $A(B^{-1}(C(x)))$), доказано, что любая рекурсивная перестановка представима как в виде $A_{0}A_{1}^{-1}A_{2}A_{3}^{-1}A_{4}A_{5}^{-1}$, так и в виде $A_{6}^{-1}A_{7}A_{8}^{-1}A_{9}A_{10}^{-1}A_{11}$, где $A_{n}$, $0\leqslant n\leqslant 11$, - примитивно рекурсивные перестановки (но "суперпозиций длины 5" недостаточно), изучаются классы рекурсивных перестановок, представимых более простыми способами (подробно рассмотрена также ситуация, когда разнозначные одноместные частично рекурсивные функции строятся из разнозначных одноместных примитивно рекурсивных функций и их обращений).

УДК 519.48

В. М. Копытов

Упорядочение алгебр Ли, 295—325.

Алгебра Ли ${\mathfrak L}$ над линейно упорядоченным полем называется частично упорядоченной, если на векторном пространстве алгебры ${\mathfrak L}$ введено отношение порядка, устойчивое относительно сложения, умножения на положительные скаляры поля и преобразований $\alpha(x)$: $a\alpha(x)=a+[a,x]$.

В работе доказывается, что для алгебр Ли справедливы признаки упорядочиваемости и доупорядочиваемости, аналогичные признакам Лоренцена , Фукса, Ониси. Всякая архимедова линейно упорядоченная алгебра Ли над упорядочиваемым полем коммутативна, и поле архимедово (теорема 3.1). Система выпуклых подалгебр линейно упорядоченной алгебры Ли образует центральную систему (теорема 3.4). Свободные алгебры Ли и локально нильпотентные алгебры Ли допускают линейные упорядочения. Свойство упорядочиваемости алгебры Ли сохраняется при расширении основного поля. Линейный порядок упорядочиваемой алгебры Ли продолжается до линейного порядка универсальной обертывающей алгебры (теорема 5.1). Если ряд Кэмпбелла-Хаусдорфа сходится в порядковой топологии для любых двух элементов алгебры Ли ${\mathfrak L}$, то ${\mathfrak L}$ может быть превращена в линейно упорядоченную группу. Найдено необходимое и достаточное условие сходимости формулы Кэмпбелла-Хаусдорфа на алгебре Ли (теорема 5.4).

УДК 517.11:518.5

A. H. Lachlan

Recursively enumerable many-one degrees, 326—358.

В работе получено описание начальных сегментов рекурсивно перечислимых $m$-степеней в терминах прямых пределов вычислимых дистрибутивных решеток. А именно верхняя полурешетка $L$ мощности > 1 изоморфна начальному сегменту рекурсивно перечислимых $m$-степеней тогда и только тогда, когда существует возрастающая последовательность $\{(D_{i},\leqslant_{i})\}$ конечных дистрибутивных решеток с верхним пределом $(D_{\omega},\leqslant_{\omega})$ такая, что ассоциированный частичный порядок $(D_{\omega},\leqslant_{\omega})$ изоморфен $L$, и такая, что выполнены следующие условия:

а) $\{D_{i}\}$ - строго вычислимая последовательность конечных множеств;

б) $x\leqslant_{i}y$ - $\forall\exists$-предикат;

в) операции $\cup$ и $\cap$ в $D_{i}$ равномерно вычислимы.