nLab
Boone conjecture

Contents

Contents

Idea

A famous result by G. Higman in group theory says that a finitely generated group can be embedded in a finitely presented group precisely if it has a presentation whose defining relations are a recursively enumerable set of words. It has been conjectured by the group theorist W. Boone that the same result holds more generally for every single-sorted algebraic theory.

While in fact the conjecture is not true for all single-sorted algebraic theories (see below), as was known by Soviet mathematicians, the general question “Which algebraic categories have the Higman property?” is still interesting (and potentially something category-theorists could study).

Statement

From Lawvere 2002:

There is an issue involving recursivity that categorists should settle: How general is Higman’s theorem? In group theory the word problem (whether a given finitely generated group is recursively related) is equivalent to the purely algebraic one of whether the given group can be embedded as a subgroup of a finitely presentable one. For which other algebraic categories is the same statement true? or is it possibly true for the category of single-sorted algebraic theories? The latter problem was posed by Bill Boone, but as far as I know, is not yet resolved.

For the category of first-order theories, a theorem analogous to Higman’s was proved by Craig and Vaught; for that case, they gave a kind of intuitive argument: using a few additional predicates one can express enough of number theory to encode a fragmentary satisfaction relation and any given recursive set of axioms, so that one can then add the one additional axiom that says “all those axioms are true”. Of course, it is non-trivial that this argument actually works.

Partial results and failure of the conjecture for all single-sorted algebraic theories

A category of models of an algebraic theory is said to satisfy the Higman property whenever any recursively presentable model embeds into a finitely presented model. The Higman property has been shown to hold for models of several algebraic theories such as those of rings, semigroups, inverse semigroups and Lie algebras (see Kukin 1989 for rings and references therein for the others).

However, there are single-sorted algebraic theories whose models do not have the Higman property as remarked in the introduction of (Kukin 1989). This is because having the Higman property implies an undecidable word problem under suitable conditions (see connection 2.8. in (Kharlampovich 1995) but for instance (non-associative) commutative algebras over a fixed field have a decidable word-problem (Shirshov 2009).

References

  • W. Craig, R. L. Vaught, Finite axiomatizability using additional predicates , JSL 23 (1958) pp.289-308.

  • M. Hébert, Finitely presentable morphisms in exact sequences , TAC 24 no.9 (2010) pp.209-220.(pdf)

  • G. Higman, Subgroups of finitely presented groups , Proc. Royal. Soc. London Ser. A (1961) pp.455-475.

  • O. G. Kharlampovich, & M. V. Sapir, Algorithmic problems in varieties. International Journal of Algebra and Computation 5(04n05) (1995) pp.379-602.

  • G. Kukin, The variety of all rings has Higman’s property. Third Siberian School: Algebra and Analysis (1989); American Mathematical Society translations. Series 2 v. 163 (1995) pp.91-101.

  • W. F. Lawvere, On the effective topos - message to catlist, January 2002. (link)

  • Shirshov, Anatolii Illarionovich. Some algorithmic problems for ε-algebras. Selected Works of AI Shirshov. Birkhäuser Basel (2009) pp. 119-124.

Last revised on December 23, 2020 at 04:31:19. See the history of this page for a list of all contributions to it.