RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2018 Volume 57, Number 2, Pages 149–174 (Mi al841)

Degrees of autostability for prime Boolean algebras

N. A. Bazhenovab, M. I. Marchukab

a Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090 Russia
b Novosibirsk State University, ul. Pirogova 1, Novosibirsk, 630090 Russia

Abstract: 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.

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.

UDC: 510.5+512.563

Received: 11.10.2016
Revised: 25.05.2016

DOI: 10.17377/alglog.2018.57.202


 English version:
Algebra and Logic, 2018, 57:2, 98–114

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024