Degrees of autostability for prime Boolean algebras

N. A. Bazhenov ; M. I. Marchuk

Algebra i logika, Tome 57 (2018) no. 2, pp. 149-174

Résumé

We look at the concept of algorithmic complexity of isomorphisms between computable copies of Boolean algebras. Degrees of autostability are found for all prime Boolean algebras. It is shown that for any ordinals $\alpha$ and $\beta$ with the condition $0\le\alpha\le\beta\le\omega$ there is a decidable model for which $\mathbf0^{(\alpha)}$ is a degree of autostability relative to strong constructivizations, while $\mathbf0^{(\beta)}$ is a degree of autostability. It is proved that for any nonzero ordinal $\beta\le\omega$, there is a decidable model for which there is no degree of autostability relative to strong constructivizations, while $\mathbf0^{(\beta)}$ is a degree of autostability.

Détail

Keywords: autostability spectrum, degree of autostability, Boolean algebra, autostability, prime model, computable model, computable categoricity, categoricity spectrum, degree of categoricity, decidable model, autostability relative to strong constructivizations.