Countable Boolean algebras and decidability. (Schetnye bulevy algebry i razreshimost’.) (Russian) Zbl 0902.03021

Sibirskaya Shkola Algebry i Logiki. Novosibirsk: Nauchnaya Kniga. xii, 362 p. (1996).
The book under review is an extended version of the author’s book [Countable Boolean algebras (Russian) (1988; Zbl 0667.03024)]. Algebraic properties of Boolean algebras are considered in the first chapter of the book. The author gives some basic definitions and discusses Boolean rings and lattices, and their connections with Boolean algebras. The second chapter deals with FrĂ©chet ideals, Ershov algebras (relatively complemented distributive lattices), Stone’s theorem on isomorphy of Boolean algebras to algebras of subsets, Vaught’s isomorphism theorem and its variants, generating sets of Boolean algebras (linearly ordered, trees), elementary classification of Boolean algebras and definable relations on them. The author gives some basic notions of model theory and recursion-theoretic model theory. Ershov-Tarski ideals and elementary characteristics (= invariants) are discussed. It is proven that two Boolean algebras are elementarily equivalent if and only if they have the same characteristic \((n,m,k)\); the triples \((n,m,k)\) that are characteristics of the complete theories of Boolean algebras are presented. Countable dense Boolean algebras (which are exactly the saturated models of the corresponding theories) are constructed. A criterion is given for elementarily equivalent countable homogeneous Boolean algebras to be isomorphic; it uses some additional characteristics. A model complete definable expansion of the theory of all Boolean algebras is constructed. Restricted theories of Boolean algebras and definable formulas are analyzed as well.
The algorithmic complexity of relations defined on Boolean algebras is considered in the third chapter of the book. The author studies numberings of Boolean algebras and considers the algorithmic complexity of the set of numbers of elements appearing in a relation under consideration. Some basic definitions of recursion theory and the theory of numberings are given. Constructive (= recursive) Boolean algebras, strongly constructive (= decidable) Boolean algebras, autostable (= recursively categorical) Boolean algebras are analyzed. Given an effectively presented linear order with a minimal element, a Boolean algebra is constructed that inherits some algorithmic properties of the order; the construction is used for presenting constructive Boolean algebras with beforehand recursion-theoretic properties. Generating tree sets are used for proving that a Boolean algebra is constructivizable if and only if so is the corresponding Boolean ring (Boolean lattice). The Goncharov-Peretyat’kin criterion for a countable homogeneous model to be decidable, the Morley criterion for a countable saturated model of a decidable theory to be decidable, and the Goncharov-Harrington criterion for a prime model of a decidable theory to be decidable are given in the general situation, not only for Boolean algebras. They are used for finding decidable Boolean algebras with beforehand model-theoretic properties; e.g., a countable saturated model and countable prime model of a complete theory of Boolean algebras are proven to be decidable. Theorems on constructive saturation and on strongly constructive extensions are proven. Connections between decidability of all elementary properties of a constructive Boolean algebras and that of all atomic properties are discussed; e.g., given a Boolean algebra \(\mathfrak{A}\) with characteristic \((1,1,0)\) (or \((1,0,1)\)), if the set of atoms in the first case (or the sets of atoms, of atomic elements, and of atomless elements in the second case) is (are) recursive, then \(\mathfrak{A}\) is decidable (there is a decidable Boolean algebra \(\mathfrak{B}\) isomorphic to \(\mathfrak{A}\)). Questions on algorithmic dimensions of Boolean algebras are discussed; a constructivizable Boolean algebra is autostable if and only if the set of its atoms is finite; therefore, the algorithmic dimension of a Boolean algebra is equal to 0, 1, or \(\omega\). Effective subalgebras and ideals of recursive Boolean algebras are also under consideration. Finally, the automorphism groups of Boolean algebras are analyzed.
The book is written by a working specialist in the field, the topics covered are up-to-date and oriented toward future research. It is useful both for specialists and for all mathematicians interested in studying Boolean algebras. An English translation appeared in the meantime (Plenum Press, 1997).


03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
06-02 Research exposition (monographs, survey articles) pertaining to ordered structures
06E05 Structure theory of Boolean algebras


Zbl 0667.03024