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

Fingerprint

Boolean algebra
Equivalence relation
Linear Group
Linear Order
Natural number
Countable
Quotient

Keywords

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

ASJC Scopus subject areas

  • Mathematics(all)

Cite this

Boolean algebras realized by c.e. equivalence relations. / Bazhenov, Nikolay; Mustafa, Manat; Stephan, Frank; Yamaleev, Mars.

In: Siberian Electronic Mathematical Reports, Vol. 14, 01.01.2017, p. 848-855.

Research output: Contribution to journalArticle

Bazhenov, Nikolay ; Mustafa, Manat ; Stephan, Frank ; Yamaleev, Mars. / Boolean algebras realized by c.e. equivalence relations. In: Siberian Electronic Mathematical Reports. 2017 ; Vol. 14. pp. 848-855.
@article{2a11188ade074a4fbeeeeaa224af54e1,
title = "Boolean algebras realized by c.e. equivalence relations",
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.",
keywords = "Boolean algebras, Computability theory, Computably enumerable structures, Equivalence relations",
author = "Nikolay Bazhenov and Manat Mustafa and Frank Stephan and Mars Yamaleev",
year = "2017",
month = "1",
day = "1",
doi = "10.17377/semi.2017.14.071",
language = "English",
volume = "14",
pages = "848--855",
journal = "Siberian Electronic Mathematical Reports",
issn = "1813-3304",
publisher = "Sobolev Institute of Mathematics",

}

TY - JOUR

T1 - Boolean algebras realized by c.e. equivalence relations

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

AU - Stephan, Frank

AU - Yamaleev, Mars

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

KW - Boolean algebras

KW - Computability theory

KW - Computably enumerable structures

KW - Equivalence relations

UR - http://www.scopus.com/inward/record.url?scp=85041614007&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041614007&partnerID=8YFLogxK

U2 - 10.17377/semi.2017.14.071

DO - 10.17377/semi.2017.14.071

M3 - Article

AN - SCOPUS:85041614007

VL - 14

SP - 848

EP - 855

JO - Siberian Electronic Mathematical Reports

JF - Siberian Electronic Mathematical Reports

SN - 1813-3304

ER -