dc.description.abstract
Classification problems, in mathematics and beyond, often arise from a chosen notion of sameness between objects. Such a notion determines an equivalence relation, whose equivalence classes are the objects to be identified by the classification. Conversely, every partition of a class of objects is represented by an equivalence relation. From this point of view, studying classification problems amounts to studying equivalence relations and the complexity of their classes or invariants. This thesis studies equivalence relations through a computability-theoretic lens. It explores three fairly independent directions, highlighting the range of applications that equivalence relations have in computability theory. In the first chapter, we give a general introduction to the thesis, highlighting the topics that tie the other chapters together. In the second chapter, we investigate the complexity of isomorphism relations for classes of \emph{finitely generated} and $n$-generated computably enumerable (c.e.) algebras, presented via c.e.\ presentations---that is, as quotients of term algebras over decidable sets of generators by c.e.\ congruences. Our goal is to develop a systematic framework for analysing such isomorphism problems from a computability-theoretic perspective. To compare their complexity, we employ the notion of \emph{computable reducibility}, measuring these relations against canonical benchmarks on c.e.\ sets, such as $\eqce$, $\ezero$, and the ordinal-indexed family $\emin(\alpha)$. A central insight of our work is the interplay between the algebraic structure and the algorithmic complexity: we show that if every algebra in a class satisfies the ascending chain condition on its congruence lattice, then the corresponding isomorphism relation is computably reducible to $\eqce$. We also apply this framework to a range of concrete cases. In particular, we analyse the isomorphism relations for finitely generated commutative semigroups, monoids, and groups, positioning them within the broader landscape of classification problems. In the third chapter, we study learning of c.e.\ sets up to equivalence relations. Learning from positive data models a scenario in which a learner receives longer and longer initial segments of an enumeration of an unknown set and repeatedly outputs a conjecture about it. Classical identification in the limit requires the learner to eventually stabilise to a hypothesis naming the target exactly, while anomalous learning relaxes this requirement by allowing finitely many errors in the final hypothesis. We develop a natural generalisation for computably enumerable (c.e.) sets in which correctness is determined by an arbitrary equivalence relation on their indices that respects equality of the sets they enumerate. We call the resulting framework tolerant learning. Exact learning and finite-anomaly learning arise as special cases. By comparing tolerance relations according to the families they make learnable, we obtain a new degree structure, the tolerant learning hierarchy. We extend the classical methods of locking sequences and tell-tales to this setting and derive a combinatorial characterisation of those tolerance relations that are universal (that is, under which every family of nonempty computably enumerable sets is learnable). We then show that the hierarchy is a bounded lower semilattice but not an upper semilattice, is atomless and coatomless, and contains chains and antichains of size continuum. We also analyse natural benchmark relations, including c.e.-index analogues of standard equivalence relations from descriptive set theory, and establish substantial incomparability among their learning powers. Finally, we separate non-effective from computable tolerant learning by exhibiting a universal relation that is not computably universal. These results show that semantic tolerance gives rise to a genuine degree theory at the interface of algorithmic learning and the theory of equivalence relations. In the fourth chapter, we give complexity bounds for the bi-embeddability relation on scattered linear orders. Stratifying the scattered linear orders by their Hausdorff rank, one obtains, for each countable ordinal $\alpha$, the class $\text{LO}_\alpha$ of linear orders of Hausdorff rank at most $\alpha$ and the bi-embeddability relation ${\approx} \restrict \text{LO}_\alpha$ restricted to this class. We give a $\Sigma_{2\alpha + 2}$-definition of ${\approx} \restrict \text{LO}_\alpha$ in the infinitary logic $\mathcal{L}_{\omega_1,\omega}$. Thus, for countable $\alpha$, ${\approx} \restrict \text{LO}_\alpha$ is $\mathbf{\Sigma}^0_{2\alpha + 2}$ and therefore Borel. Furthermore, we conclude from our proof that, for computable $\alpha$, ${\approx} \restrict \text{LO}_\alpha$ is $\Sigma^0_{2\alpha + 2}$.
en