Finitely axiomatizable theories and 
	      Lindenbaum algebras of semantic classes
		       Mikhail Peretyat'kin

A numerated Boolean algebra (B,nu) is called a Sigma^0_n-algebra, if its
join, meet and complementation operations are presentable by recursive
functions on nu-indices, while the equality predicate is a
Sigma^0_n-relation under the numeration nu. A numerated Boolean algebra
(B,nu) is called a Sigma^0_n-universal Boolean algebra, if it is a
Sigma^0_n-algebra, and for any Sigma^0_n-algebra (B',nu'), there is an
element a in B such that the numerated Boolean algebras (B',nu') and
(B,nu)[a] are constructively isomorphic, where (B,nu)[a] is the natural
restriction of (B,nu) to the elements below a. Similar definitions apply
to other classes of hierarchies. It is known, that universal Boolean
algebras for different classes of hierarchies exist, and that they are
pairwise non-isomorphic to each other. A numerated Boolean algebra B is
called recursively perfect, if a finite sequence of iterated quotients by
the Frechet ideal consists of atomic Boolean algebras, except for the last
in the sequence, which is a Xi-universal Boolean algebra over some class
Xi of a hierarchy.

A signature sigma is called rich, if it contains at least one predicate or
function of arity greater or equal 2, or two unary functions. Consider
the following semantic classes of models of a fixed finite rich signature
sigma, which in fact are definable by some conditions on the corresponding 
Lindenbaum algebras:
D is the class of all models having a decidable theory,
F is the class of all models with finitely axiomatizable theory, 
N is the class of all models whose theory is not finitely axiomatizable, 
C is the class of all strongly constructivizable models, 
A is the class of all strongly constructivizable models of 
		algorithmic dimension 1. 
Also, we consider the following semantic classes of models of signature sigma: 
M_fin is the class of all finite models, 
P is the class of all prime models, 
S is the class of all countable saturated models, 
W is the class of all models with omega-stable theory.

A result of Hanf [1] states that the Lindenbaum algebra of predicate logic
is a Sigma^0_1-universal Boolean algebra. A result obtained recently
(jointly with S. Lempp and R. Solomon) states that the Lindenbaum algebra
of the theory of the class M_fin is recursively perfect, namely, it is
atomic, while its quotient algebra modulo the Frechet ideal is a
Sigma^0_2-universal Boolean algebra. Earlier, Selivanov had proved a
result which, in another formulation, states that the Lindenbaum algebras
of the two classes F and N are recursively perfect.

Some rough estimates show that the Lindenbaum algebras of the classes of
models generated by the classes D, F, N, C, A, as well as these classes
together with the class P are probably all recursively perfect (estimates
of the algorithmic complexity of theories of some combinations of these
classes are obtained in [2]). It is possible to assume that the various
combinations of the classes D, F, N, C, A together with each of the
classes S and W also yield recursively perfect Lindenbaum algebras. 
Methods for finitely axiomatizable theories appear to be useful here. 
This area is of interest since it reveals some of the deep algorithmic
nature of classical first order predicate logic.

References
1.  W. Hanf, The Boolean algebra of Logic, Bull. AMS 31 (1975), 587 - 589.
2.  M. G. Peretyat'kin, Finitely axiomatizable theories, Plenum, New York, 1997.