|
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.
Received June 29, 2017, published August 18, 2017
Citation:
N. Bazhenov, M. Mustafa, F. Stephan, M. Yamaleev, “Boolean algebras realized by c.e. equivalence relations”, Sib. Èlektron. Mat. Izv., 14 (2017), 848–855
Linking options:
https://www.mathnet.ru/eng/semr827 https://www.mathnet.ru/eng/semr/v14/p848
|
Statistics & downloads: |
Abstract page: | 253 | Full-text PDF : | 57 | References: | 36 |
|