RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1972, том 11, номер 3, страницы 326–358 (Mi al1342)

Эта публикация цитируется в 10 статьях

Recursively enumerable many-one degrees

A. H. Lachlan


Аннотация: В работе получено описание начальных сегментов рекурсивно перечислимых $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}$ равномерно вычислимы.

УДК: 517.11:518.5

Поступило: 23.02.1972

Язык публикации: английский



Реферативные базы данных:


© МИАН, 2024