Geodesic
Atomless Boolean algebras computable in polynomial time
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 1035-1039

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
P. E. Alaev. Atomless Boolean algebras computable in polynomial time. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 1035-1039. http://geodesic.mathdoc.fr/item/SEMR_2016_13_a30/
@article{SEMR_2016_13_a30,
     author = {P. E. Alaev},
     title = {Atomless {Boolean} algebras computable in polynomial time},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1035--1039},
     year = {2016},
     volume = {13},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2016_13_a30/}
}
TY  - JOUR
AU  - P. E. Alaev
TI  - Atomless Boolean algebras computable in polynomial time
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2016
SP  - 1035
EP  - 1039
VL  - 13
UR  - http://geodesic.mathdoc.fr/item/SEMR_2016_13_a30/
LA  - ru
ID  - SEMR_2016_13_a30
ER  - 
%0 Journal Article
%A P. E. Alaev
%T Atomless Boolean algebras computable in polynomial time
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2016
%P 1035-1039
%V 13
%U http://geodesic.mathdoc.fr/item/SEMR_2016_13_a30/
%G ru
%F SEMR_2016_13_a30

[1] Cenzer D., Remmel J., “Polynomial time versus recursive models”, Annals of Pure and Applied Logic, 54 (1991), 17–58 | DOI | MR | Zbl

[2] Goncharov S. S., Countable Boolean algebras and decidability, Siberian School of Algebra and Logic, Plenum, New York, NY, 1997, xii+330 pp. | MR | Zbl

[3] Remmel J. B., “Polynomial time categoricity and linear orderings”, Progr. Comput. Sci. Appl. Logic, 12 (1993), 713–746 | MR | Zbl

[4] Alaev P. E., “Existence and uniqueness of structures computable in polynomial time”, Algebra and logic, 55:1 (2016), 72–76 | DOI | MR | Zbl

[5] Remmel J. B., “Recursive isomorphism types of recursive Boolean algebras”, The Journal of Symbolic Logic, 46:3 (1981), 572–594 | DOI | MR | Zbl

[6] Goncharov S. S., Dzgoev V. D., “Autostability of models”, Algebra and Logic, 19:1 (1980), 28–37 | DOI | MR | Zbl

[7] Cenzer D., Remmel J. B., Complexity Theoretic Model Theory and Algebra, v. 1, Handbook of Recursive Mathematics, 1998 | MR | Zbl