In this talk, we study the classification of isomorphism problems with countably many isomorphism types. Borel reducibility has proven to be a powerful tool for classifying classes of countable structures under isomorphism; however, such problems, when restricted to classes with only countably many isomorphism types, have the same Borel complexity.

To nicely classify such problems, we present a framework defined in a series of papers by Bazhenov, Fokina, Kötzing, and San Mauro which combines ideas from computable structure theory and algorithmic learning theory. Here, given a countable family of structures \(\mathfrak{K}\) a learner receives larger and larger pieces of an isomorphic copy of a structure in \(\mathfrak{K}\) and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if the conjectures eventually stabilize to a correct guess.

Together with Bazhenov and San Mauro, we showed that a countable family of countable structures is learnable if and only if the corresponding isomorphism problem reduces to \(E_0\), the equivalence relation of eventual agreement on infinite binary sequences. Replacing \(E_0\) with other Borel equivalence relations, one obtains a hierarchy to rank such isomorphism problems. This improves the aforementioned framework by providing a way of calibrating the complexity of non-learnable families.

Starting from a result of Bazhenov, Fokina, and San Mauro we give a model-theoretic characterization of the learning power of several equivalence relations (with a focus on Friedman-Stanley jumps of the identity on \(2^\mathbb{N}\) and \(\mathbb{N}\)) and also of other classical learning criteria.

This talk collects joint works with Bazhenov, Jain, Marcone, San Mauro, and Stephan.

A system of linear equations over a ring \(R\) is partition regular if for any finite coloring of \(R\), the system has a monochromatic solution. In 1933, Rado [3] showed that an inhomogeneous system is partition regular over \(\mathbb{Z}\) if and only if it has a constant solution. Following a similar approach, Byszewski and Krawczyk [1] showed that the result holds over any integral domain. In 2018, following a different approach, Leader and Russell [2] generalized this over any commutative ring \(R\). We analyze some of these combinatorial results from a computability-theoretic point of view, starting with a theorem by Straus [4] used in the work of [1] and [2] that generalizes an earlier result by Rado.

Bibliography

1. Byszewski, B., Krawczyk, E.,Rado’s theorem for rings and modules,Journal of Combinatorial Theory Series A,vol. 180 (2021), no. 105402, pp. 28.
2. Leader, I., Russell, P. A.,Inhomogeneous partition regularity,Electronic Journal of Combinatorics,vol. 27 (2020), no. 2, pp. 4.
3. Rado, R.,Studien zur kombinatorik,Mathematische Zeitschrift,vol. 36 (1933), no. 1, pp. 424–470.
4. Straus, E. G.,A combinatorial theorem in group theory,Mathematics of Computation,vol. 29 (1975), pp. 303-309.

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.