scientific article; zbMATH DE number 1002913
Boolean algebrascountable modelsmodel-theoretical, algebraic, and computability aspects of Boolean and Ershov algebras
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Decidability of theories and sets of sentences (03B25) Computable structure theory, computable model theory (03C57) Model-theoretic algebra (03C60) Theory of numerations, effectively presented structures (03D45) Research exposition (monographs, survey articles) pertaining to ordered structures (06-02) Structure theory of Boolean algebras (06E05)
[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, \textit{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.
- On computable presentations of some functional lattices
- Alternative characterizations of finitary and well-founded Boolean algebras
- Degree spectra and computable dimensions in algebraic structures
- Computable torsion abelian groups
- The existence of strongly computable representations in the class of Boolean algebras
- A note on computable distinguishing colorings
- Punctual dimension of algebraic structures in certain classes
- Computable metrics above the standard real metric
- Categoricity spectra of computable structures
- On bi-embeddable categoricity of algebraic structures
- The theories of superatomic Boolean algebras with distinguished subalgebra which lack countably saturated models
- On the isomorphism problem for measures on Boolean algebras
- Categorical linearly ordered structures
- Boolean algebras realized by c.e. equivalence relations
- Effective categoricity for distributive lattices and Heyting algebras
- Boolean algebras, Tarski invariants, and index sets
- Abelian p-groups and the halting problem
- Prime model with no degree of autostability relative to strong constructivizations
- scientific article; zbMATH DE number 4037810 (Why is no real title available?)
- scientific article; zbMATH DE number 41688 (Why is no real title available?)
- The minimality of certain decidability conditions for Boolean algebras
- scientific article; zbMATH DE number 1303207 (Why is no real title available?)
- On a question of Kalimullin
- Computable topological groups and Pontryagin duality
- scientific article; zbMATH DE number 934728 (Why is no real title available?)
- Definable Subsets of Polynomial-Time Algebraic Structures
- Proper divisibility in computable rings
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- Algebraic structures computable without delay
- Index sets of constructive models that are autostable under strong constructivizations
- Perfect Local Computability of Superatomic Boolean Algebras
- ON THE COMPLEXITY OF CLASSIFYING LEBESGUE SPACES
- Computability of Polish spaces up to homeomorphism
- Algebraic Geometry over Heyting Algebras
- Computable Stone spaces
- Punctually presented structures I: Closure theorems
- Regular bi-interpretability of Chevalley groups over local rings
- COMPUTABLY COMPACT METRIC SPACES
- On the computability of ordered fields
- On the 1-decidability of Boolean algebras with one distinguished ideal
- Computable Boolean algebras and complexity of the Fréchet ideal
- On learning families of ideals in lattices and Boolean algebras
- On learning down-sets in quasi-orders, and ideals in Boolean algebras
- On learning existentially definable subsets in a computable structure
- The existence of primitive recursive structures
- Undecidability of the degree structure of primitive recursive m-reducibility
- A non-computable c.e. closed subset of \([0, 1]\)
- A superatomic Boolean algebra with a distinguished subalgebra whose theory lacks simple models
- The 2-decidability of Boolean algebras with one distinguished ideal
- Elementary equivalence of countable atomless Boolean algebras with distinguished ideal
- On the theory of subalgebra lattices for arbitrary groupoids
- Weihrauch complexity for elementary embeddings into countable saturated models
- On computability-theoretic universality of Boolean-valued models
- Online and feasible presentability: from trees to modal algebras
- On computability of ideal lattices
- What is nominalistic mereology?
- Computably categorical Boolean algebras enriched by ideals and atoms
- Index sets of autostable relative to strong constructivizations constructive models for familiar classes
- Partial automorphism semigroups
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3130249)