|
Математическая логика, алгебра и теория чисел
Решеточные свойства полурешеток Роджерса вычислимых и обобщенно вычислимых семейств
М. Х. Файзрахманов Kazan (Volga Region) Federal University, 18, Kremlyovskaya str., Kazan, 420008, Russia
Аннотация:
We consider the distributivity property and the property of being a lattice of Rogers semilattices of generalized computable families.
We prove that the Rogers semilattice of any nontrivial $A$-computable family is not a lattice for every non-computable set $A$. It is also proved that if a set $A$ is non-computable then the Rogers semilattice of
any infinite $A$-computable family is not weakly distribuive. Furtermore, we find two infinite computable families with nontrivial distributive and properly weakly distributive nontrivial Rogers semilattices.
Ключевые слова:
computable enumeration, generalized computable enumeration, $A$-computable enumeration, Rogers semilattice.
Поступила 12 августа 2019 г., опубликована 18 декабря 2019 г.
Образец цитирования:
М. Х. Файзрахманов, “Решеточные свойства полурешеток Роджерса вычислимых и обобщенно вычислимых семейств”, Сиб. электрон. матем. изв., 16 (2019), 1927–1936
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1179 https://www.mathnet.ru/rus/semr/v16/p1927
|
Статистика просмотров: |
Страница аннотации: | 223 | PDF полного текста: | 102 | Список литературы: | 17 |
|