Atomless Boolean algebras computable in polynomial time

P. E. Alaev

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 1035-1039

Résumé

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.

Détail

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