Geodesic
Atomless Boolean algebras computable in polynomial time
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 1035-1039 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@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
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/

[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