RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2017, том 14, страницы 848–855 (Mi semr827)

Математическая логика, алгебра и теория чисел

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.

УДК: 510.5

MSC: 03D45

Поступила 29 июня 2017 г., опубликована 18 августа 2017 г.

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

DOI: 10.17377/semi.2017.14.071



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


© МИАН, 2024