Strictly Computability of Class of Constructive I-algebras

Nurlan T. Kogabaev

In Construcive model theory the question of existence of computable numeration for the class of constructive models is closely connected with the problem of choice of most “natural” computable numeration. To solve the above mentioned problem the family of all computable numerations of this class is provided with the additional structure consisting of preorder of reducibility. Using given approach it is reasonable to turn to the greatest with respect to this preorder computable numeration. The existence of such a greatest numeration leads to the notions of principal computable numeration and strictly computable class of models [1].

There are a number of results concerning the above area of problems in the case of various particular classes of constructive models. The examples of strictly computable, computable but not strictly computable, and non-computable classes of models can be found in [1, 2].

In the present paper we study Boolean algebras with distinguished ideals. Throughout, these algebras are called I-algebras and are considered in the signature σ = ⟨∨, ∧, C, 0, 1, I_{1}, …, I_{λ}⟩, where I_{1}, …, I_{λ} are unary predicate symbols. A theory T_{λ} of I-algebras contains axioms of Boolean algebras and sentences stating that I_{1}, …, I_{λ} are ideals; λ is a fixed natural number.

In the paper we show that there is a principal computable numeration for the class of all constructive I-algebras. That is, there exists a computable sequence α_{0} of constructive I-algebras such that any other computable sequence α of constructive I-algebras is reducible to α_{0}. Thus, the class of all constructive I-algebras is strictly computable.

[1] V.P.Dobritsa, Computable Classes of Constructive Models, in: Handbook of Recursive Mathematics, Vol.1, 183-233, Elsevier, 1998.

[2] S.S.Goncharov, Countable Boolean algebras and Decidability, Plenum, New York, 1997.

Address: Novosibirsk State University, Pirogova Street 20/1, room 604, Novosibirsk 630090, Russia

E-mail: kogabaev@mail.ru