RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2016 Volume 13, Pages 1035–1039 (Mi semr732)

This article is cited in 3 papers

Mathematical logic, algebra and number theory

Atomless Boolean algebras computable in polynomial time

P. E. Alaev

Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

Abstract: We construct an example of atomless Boolean algebra $ {\mathfrak B} $, computable in polynomial time, that has no primitive recursive function $ f : B \to B $ such that $ 0 < f (a) < a $ for $ a \neq 0 $. In addition, we show that if two primitive recursive atomless Boolean algebras $ {\mathfrak B}_{1} $ and $ {\mathfrak B}_{2} $ have such functions, then there is an isomorphism $ g : {\mathfrak B}_{1} \to {\mathfrak B}_{2} $ such that $ g $ and $ g^{-1} $ are primitive recursive functions.

Keywords: computable structure, Boolean algebra, primitive recursive structure, polynomial time computability, primitive recursive isomorphism.

UDC: 510.5, 512, 510.6

MSC: 03C57, 03D15, 06E99

Received October 10, 2016, published November 22, 2016

DOI: 10.17377/semi.2016.13.082



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025