Boolean algebras realized by c.e. equivalence relations

Nikolay Bazhenov, Manat Mustafa, Frank Stephan, Mars Yamaleev

Research output: Contribution to journalArticle

Abstract

Let E be a computably enumerable (c.e.) equivalence relation on the set of natural numbers ω. 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.

Original languageEnglish
Pages (from-to)848-855
Number of pages8
JournalSiberian Electronic Mathematical Reports
Volume14
DOIs
Publication statusPublished - Jan 1 2017

Keywords

  • Boolean algebras
  • Computability theory
  • Computably enumerable structures
  • Equivalence relations

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Boolean algebras realized by c.e. equivalence relations'. Together they form a unique fingerprint.

  • Cite this