Solving the Bergtra–Tucker problem: a c.e. algebra with no finitely presented expansion

A classical result of Bergstra and Tucker states that every finitely generated computable algebra (i.e., a finitely generated algebra with decidable word problem) admits a finite presentation after expanding the signature with finitely many auxiliary computable operations. They also prove that every computably enumerable algebra can be embedded into a finitely presented algebra by adding new operations to the extended algebra. These results led Bergstra and Tucker, and independently Goncharov, to ask in the late 1970s whether every finitely generated computably enumerable algebra (i.e., a finitely generated algebra with computably enumerable word problem) admits a finite presentation by either equations or quasi-equations in an expansion without extending the domain. The equational case of this problem was fully resolved for universal algebras in the 1990s, and for classical structures such as groups, non-associative rings, and semigroups in the middle of the 2010s.

This paper addresses the remaining case of conditional equations, i.e., quasi-equations of the form $\left( {s_1 = t_1} \land \ldots \land {s_n = t_n} \right) \Rightarrow {s = t}$. Unlike equations, conditional equations are not preserved under homomorphisms, a fundamental difference that renders the methods developed for the equational case inapplicable to quasi-equations. We therefore develop a new approach and construct a finitely generated computably enumerable algebra that admits no finite presentation by conditional equations in any expansion. The proof brings together techniques from several areas: universal algebra, through the analysis of almost free algebras and their algorithmic properties; model theory, via quantifier elimination for almost free algebras; and computability theory, using a finite injury priority argument to build a finitely generated computably enumerable algebra whose computable operations are essentially term operations. The interplay of these methods is then applied to show that no expansion of such an algebra can be finitely presented by conditional equations. This provides a complete solution to the Bergstra–Tucker problem and closes the final gap in the theory of finite presentations for computably enumerable finitely generated algebras.

This is a joint work with Jia Yifan and Heer Tern Kooh.