Computably enumerable sets and related issues (Q695800)

The paper under review is a survey on computably enumerable sets, mainly on the algebraic descriptions and on the decidability/definability matters of the structures \({\mathbf L}_{\mathbf F}\) and \(\mathbf {L}_m\), where \({\mathbf L}_{\mathbf F}=(\mathbf {CE}\slash\mathbf{F},\subseteq)\) denotes the lattice of the class of the c.e. sets \(\mathbf {CE}\) modulo the ideal of finite sets \(\mathbf {F}\), and \({\mathbf L}_m=(\mathbf {CE}\slash\equiv_m,\leq)\) denotes the upper semilattice of the c.e. many-one degrees. The author deliberately chose not to treat topics like automorphisms, orbits, dynamic properties, c.e. Turing degrees, the latter only occasionally. However, the bibliography contains items for these missing topics. We outline the contents of this survey. The first part of the paper mainly contains the interrelationship between \(\mathbf {L}_{\mathbf F}\) and \(\mathbf {L}_m\) and algebraic descriptions of both \(\mathbf {L}_m\) and \(\mathbf {L}_{\mathbf F}\), in particular the principal filters and the principal ideals of these structures. For example, the principal filters of \(\mathbf {L}_{\mathbf F}\), each of which is generated by the equivalence class of a c.e. set \(A\), are classified and described according to the structural property of the set \(A\): maximal, quasimaximal, hyperhypersyimple, r-maximal, semi-low\(_{1,5}\). While the principal ideals of \(\mathbf {L}_m\) are characterized by the so-called Lachlan semilattices. The second part of the paper deals with definability and decidability questions concerning both \(\mathbf {L}_{\mathbf F}\) and \(\mathbf {L}_m\). For \(\mathbf {L}_{\mathbf F}\), the results are equivalently formulated relatively to the structure \(\mathbf {L}=(\mathbf{CE},\subseteq)\). Here we find the definability in \(\mathbf {L}\) of structural properties of c.e. sets (simplicity, maximality, r-maximality, hyperhypersimplicity), and the definability in \(\mathbf {L}_m\) of order-theoretic concepts (sup, minimal, cover, atom). For what concerns decidability, the author considers the elementary theories \(\mathrm{Th}(\mathbf {L})\), \(\mathrm{Th}(\mathbf {L}_m)\) and their fragments. The paper ends with a section dedicated to the universal property of sequences of c.e. sets. Reviewer's remark: However, the statement at page 499, lines 12--14 ``That the family \(\mathbf{MAX}\) is rich is evidenced by the following fact: each computably enumerable (i.e., containing a computably enumerable set) \(T\)-degree has infinitely many maximal sets'' is not correct, because a computably enumerable \(T\)-degree \(\mathbf{a}\) contains maximal sets if and only if \(\mathbf{a}\) is \(high_1\).