CSUN Algebra, Number Theory, and Discrete Mathematics Seminar

This talk is about our ongoing work on isomorphism relations on classes of computably enumerable (c.e.) algebras, i.e. algebras that have a c.e. presentation.

We use the notion of presentation in the algebraic sense, i.e. a presentation is a set of generators together with a set of equations on these generators. Many people have studied finite presentations (where generators and equations are both finite) as a very natural restriction. On the other hand, a c.e. presentation is defined as having a decidable (i.e. membership can be decided by an effective procedure) set of generators and a computably enumerable (i.e. members can be enumerated by an effective procedure) set of equations. This restriction turns out to be interesting as well, in particular from the view of computability theory. The reason is that there is a way of identifying c.e. presentations with natural numbers, which are the main object of study in computability theory, such that each natural number is the code for a particular c.e. presentations. This allows us to use tools from the computability-theoretic study of equivalence relations on the natural numbers to study isomorphism relations on different classes of c.e. presentations. In particular, we adopt computable reducibility, which is a method of comparison of equivalence relations. Furthermore, we use well-studied benchmark relations; for example ${=}^{ce}$, where two natural numbers are equivalent if they are codes for the same c.e. set.

As a case study we investigate finitely generated commutative semigroups. Using algebraic properties we show that the isomorphism relations on the classes of $n$-generated commutative semigroups, for natural numbers $n$, form a strictly ascending sequence in the hierarchy of computable reducibility and are all bounded by ${=}^{ce}$. This is joint work with Luca San Mauro.