Sib. Èlektron. Mat. Izv., 2017, Volume 14, Pages 848–855
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
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.
|Russian Foundation for Basic Research
|Ministry of Education and Science of the Russian Federation
|N. Bazhenov was supported by RFBR, according to the research project No. 16-31-60058 mol_a_dk. M. Yamaleev was supported by RFBR project 15-41-02507, by the subsidy allocated to Kazan Federal University for the state assignment in the sphere of scientific activities 1.1515.2017, and by the research grant of Kazan Federal University.
PDF file (154 kB)
Received June 29, 2017, published August 18, 2017
N. Bazhenov, M. Mustafa, F. Stephan, M. Yamaleev, “Boolean algebras realized by c.e. equivalence relations”, Sib. Èlektron. Mat. Izv., 14 (2017), 848–855
Citation in format AMSBIB
\by N.~Bazhenov, M.~Mustafa, F.~Stephan, M.~Yamaleev
\paper Boolean algebras realized by c.e. equivalence relations
\jour Sib. \`Elektron. Mat. Izv.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|