|
Алгебра и логика, 1972, том 11, номер 3, страницы 326–358
(Mi al1342)
|
|
|
|
Эта публикация цитируется в 10 научных статьях (всего в 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}$ равномерно вычислимы.
Поступило: 23.02.1972
Образец цитирования:
A. H. Lachlan, “Recursively enumerable many-one degrees”, Алгебра и логика, 11:3 (1972), 326–358
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al1342 https://www.mathnet.ru/rus/al/v11/i3/p326
|
Статистика просмотров: |
Страница аннотации: | 74 | PDF полного текста: | 67 |
|