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.
- Boolean algebras
- Computability theory
- Computably enumerable structures
- Equivalence relations
ASJC Scopus subject areas