Logic Colloquium 2024


Martin Ritter

Institute of Discrete Mathematics and Geometry, TU Wien

Talks at this conference:

  Friday, 17:20, J336

Isomorphism relations on classes of c.e. algebras

This talk is about our ongoing work on isomorphism relations on classes of c.e. algebras. In this context a c.e. algebra is an algebra that is given as a quotient of the term algebra by a c.e. congruence relation. An isomorphism relation on such a class of c.e. algebras can, under reasonable conditions, be viewed as an equivalence relation on the natural numbers. This allows us to compare complexities of different isomorphism relations using known methods and results from the computability-theoretic study of equivalence relations. We use computable reducibility, a common method for comparing equivalence relations. Isomorphism relations can then be compared to well-studied equivalence relations on c.e. sets, like \(=^{ce}\), \(E^{ce}_{min}\), \(E^{ce}_0\), etc. In this talk we present a case study on finitely generated commutative semigroups. 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.