Decidable Boolean algebras of low level (Q1295398): Difference between revisions

In this paper the author studies the question on decidability for Boolean algebras of low level. The author notes that the decidability problem for classes of algorithmic problems on effectively prescribed systems is one of the main purposes of the theory of constructive models. Studying constructive models, it is important to investigate correlations between the decidability of different algorithmic problems in a constructive model as well as the study of these questions depending on the choice of constructivizations. The author studies interconnections between the decidability of all elementary properties of a constructive Boolean algebra and that of all atomic properties of enrichments of the Boolean algebra. The author notes that to answer the question whether a Boolean algebra is decidable, it is important to study the existence of constructivizations of enrichments of a Boolean algebra \(\mathcal B\) to algebraic systems of the restricted signatures \(\sigma_n, n\in\omega\). In the paper under review the author studies the question concerning the decidability of a Boolean algebra if its characterization is \((1,1,0)\). It is proved that if a Boolean algebra \({\mathcal U}\) admits a constructivization with a recursive set of numbers of atoms and \(\text{ch}({\mathcal U})= (1,1,0)\), then \(\mathcal U\) is decidable. Further, the author analyses a recursive Boolean algebra \(\mathcal U\) with a recursive set of atoms and recursive Ershov-Tarski ideal \(I({\mathcal U})\). Using this investigation, he proves that if a Boolean algebra \(\mathcal U\) admits a constructivization in signature \(\sigma_{4n-1}\) and \(\text{ch}({\mathcal U}) = (n+1,1,0)\), then \(\mathcal U\) is decidable.