|
Математическая логика, алгебра и теория чисел
Boolean algebras realized by c.e. equivalence relations
N. Bazhenovab, M. Mustafac, F. Stephand, M. Yamaleeve a Novosibirsk State University,
2 Pirogova St.,
630090, Novosibirsk, Russia
b Sobolev Institute of Mathematics, 4 Acad. Koptyug Av., 630090, Novosibirsk, Russia
c Department of Mathematics, School of Science and Technology, Nazarbayev University,
53, Kabanbay Batyr Avenue,
Astana, 010000, Republic of Kazakhstan
d Department of Computer Science and Department of Mathematics, National University
of Singapore,
119076, Republic of Singapore
e N.I. Lobachevsky Institute of Mathematics and Mechanics, Kazan Federal University, 18 Kremlevskaya Str., Kazan, 420008, Russia
Аннотация:
Let $E$ be a computably enumerable (c.e.) equivalence relation on the set of natural numbers $\omega$. We consider countable structures where basic functions are computable and respect $E$. If the corresponding quotient structure is a Boolean algebra $B$, then we say that the c.e. relation $E$ realizes $B$. In this paper we study connections between algorithmic properties of $E$ and algebraic properties of Boolean algebras realized by $E$. Also we compare these connections with the corresponding results for linear orders and groups realized by c.e. equivalence relations.
Ключевые слова:
computability theory, Boolean algebras, equivalence relations, computably enumerable structures.
Поступила 29 июня 2017 г., опубликована 18 августа 2017 г.
Образец цитирования:
N. Bazhenov, M. Mustafa, F. Stephan, M. Yamaleev, “Boolean algebras realized by c.e. equivalence relations”, Сиб. электрон. матем. изв., 14 (2017), 848–855
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr827 https://www.mathnet.ru/rus/semr/v14/p848
|
Статистика просмотров: |
Страница аннотации: | 253 | PDF полного текста: | 57 | Список литературы: | 36 |
|