RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2017 Volume 14, Pages 848–855 (Mi semr827)

Mathematical logic, algebra and number theory

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

Abstract: 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.

Keywords: computability theory, Boolean algebras, equivalence relations, computably enumerable structures.

UDC: 510.5

MSC: 03D45

Received June 29, 2017, published August 18, 2017

Language: English

DOI: 10.17377/semi.2017.14.071



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024