zbMATH — the first resource for mathematics

Countable Boolean algebras and decidability. Transl. from the Russian. (English) Zbl 0912.03019
Siberian School of Algebra and Logic. New York, NY: Plenum. xii, 318 p. (1997).
[For a review of the Russian original (Novosibirsk, 1996) see Zbl 0902.03021.]
This is a book concerned with model-theoretical, algebraic, and computability aspects of Boolean and Ershov algebras. It is divided into three more or less self-contained chapters.
The first chapter develops basic algebraic theory of Boolean algebras, looking at countable superatomic algebras, Fréchet sequences, representations, such as the Stone theorem, and Boolean algebras as generated by trees. It also covers Ershov algebras, which are mild generalizations of the notion of a Boolean algebra. It lifts several results to Ershov algebras, and classifies the isomorphism types of countable Ershov algebras.
The second chapter is devoted to model theory of countable models and uses a topological approach. The author introduces some invariants called the elementary characteristic, based on special ideals, which completely characterize the theory of a Boolean algebra, and from which it follows that the theory of any Boolean algebra is decidable. Other model-theoretical aspects such as saturation, homogeneity, model-completeness and the like are discussed.
The most substantial part of the book is the third chapter which looks at computability aspects of Boolean algebras. Computability aspects of many of the earlier representations are examined. For instance, the effective content of Stone’s theorem is examined. Much of this early work is well known (see for instance, J. B. Remmel’s article “Recursive Boolean algebras” in the Handbook of Boolean algebras, Vol. 3, 1097-1165 (1989; Zbl 0671.06001)).
The real guts of this chapter and the book in general is the wealth of results of the author exposited in this chapter. First, the author proves some basic results about omitting types in decidable models, then characterizes homogeneous models with a decidable presentation. He also looks at links between primeness, saturation and decidability issues, as well as other algorithmic aspects guaranteeing decidability. Goncharov gives a complete proof that the algorithmic dimension of a Boolean algebra is either 0, 1, or \(\infty\). Other results, some previously known and some original, are proven about the lattice of computably enumerable subalgebras, and automorphism groups of computable algebras are presented.
In summary, this is an interesting and somewhat idiosyncratic book about countable Boolean algebras written for logicians whose interests lie with decidability or computability issues. It is written in the Russian style, and to my western eyes, it is sometimes a tough read. The attribution of results is a little careless. However, it contains a large number of significant results, many due to the author, and many virtually unobtainable elsewhere. The book is therefore a must for the audience described above.

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