The number of finitely axiomatizable completions (Q1814398)

The algorithmic complexity of some natural classes of sentences has been examined by various authors. A promising approach to this research area is provided by general methods for constructing finitely axiomatizable theories with given combinations of properties, to the extent that the construction in question is applicable. A great many estimates for the algorithmic complexity of classes of sentences were obtained by \textit{M. G. Peretyat'kin} [Algebra Logika 21, No. 4, 410-441 (1982; Zbl 0567.03014); Tr. Inst. Mat. 2, 88-135 (1982; Zbl 0524.03017)]. In these cases the complexity was measured in terms of the two classical hierarchies -- the arithmetical and analytical hierarchies. In this paper sharp estimates are determined for the complexity of some natural classes of sentences in the ``small'' hierarchy of arithmetical sets, considered by \textit{V. L. Selivanov} [Tr. Inst. Mat. 2, 135-158 (1982; Zbl 0522.03029)], which generalizes the well-known hierarchy of Ershov.