Computability-theoretic aspects of classification

Abstract

Viele Probleme in der Mathematik sind Klassifizierungsprobleme. Zum Beispiel, eine wichtige Aufgabe in der Algebra ist die Klassifizierung von algebraischen Strukturen (wie z.B. Gruppen) modulo Isomorphismus. Generell beschreibt der Begriff Klassifizierung die Partitionierung einer Menge von Objekten in Klassen. So eine Klassifizierung wird üblicherweise durch eine Äquivalenzrelation dargestellt. Diese Arbeit untersucht Äquivalenzrelationen aus einer berechenbarkeitstheoretischen Perspektive. Es werden drei relativ unabhängige Richtungen untersucht, was die Vielfältigkeit der Anwendungsmöglichkeiten unterstreicht, die Äquivalenzrelationen in der Berechenbarkeitstheorie haben. Das erste Kapitel beinhaltet eine allgemeine Einleitung zu dieser Arbeit. Es werden die Themen hervorgehoben, die einen roten Faden durch die restlichen Kapitel bilden. Im zweiten Kapitel untersuchen wir die Komplexität von Isomorphismusrelationen über Klassen von endlich generierten und $n$-generierten rekursiv aufzählbaren (c.e.) Algebren, präsentiert durch rekursiv aufzählbare Präsentationen. Rekursiv aufzählbare Präsentationen sind Quotienten von Termalgebren über entscheidbare Mengen an Generatoren durch eine rekursiv aufzählbare Äquivalenz\-relation. Unser Ziel ist es, ein systematisches Framework zur Analyse solcher Isomorphismusprobleme aus einer berechenbarkeitstheoretischen Perspektive zu entwickeln. Um Komplexitäten zu vergleichen, verwenden wir die \emph{berechenbare Reduktion} (engl.\ computable reduction). Wir vergleichen die Isomorphismusrelationen mit bekannten Benchmark-Relationen, wie $\eqce$, $\ezero$, und die mit Ordinalzahlen indexierte Familie $\emin(\alpha)$. Eine zentrale Erkenntnis dabei ist der Zusammenhang zwischen der algebraischen Struktur und der algorithmischen Komplexität: wir zeigen, dass wenn für alle Algebren einer Klasse gilt, dass sie keine unendlich aufsteigende Kette in ihrem Kongruenzverband haben, dann ist die korrespondierende Isomorphismusrelation berechenbar reduzierbar auf $\eqce$. Wir wenden dieses Framework auch auf einige konkrete Fälle an. Nämlich analysieren wir die Isomorphismusrelationen auf endlich generierte kommutative Halbgruppen, Monoide, und Gruppen, und ordnen diese in die breitere Landschaft von Klassifizierungsproblemen ein. Im dritten Kapitel untersuchen wir das Lernen rekursiv aufzählbarer (c.e.) Mengen modulo Äquivalenzrelationen. Lernen aus positiven Daten modelliert ein Szenario, in dem ein Lernalgorithmus immer längere Anfangssegmente einer Aufzählung einer unbekannten Menge erhält und wiederholt eine Vermutung über diese Menge ausgibt. Die klassische Identifikation im Grenzwert (engl.\ identification in the limit) verlangt, dass sich der Lernalgorithmus schließlich auf eine Hypothese stabilisiert, welche die Zielmenge exakt beschreibt, während das Lernen mit Anomalien diese Anforderung abschwächt, indem in der endgültigen Hypothese endlich viele Fehler zugelassen werden. Wir entwickeln eine natürliche Verallgemeinerung für rekursiv aufzählbare Mengen, bei der die Korrektheit durch eine beliebige Äquivalenzrelation auf ihren Indizes bestimmt wird, sofern diese die Gleichheit der von ihnen aufgezählten Mengen respektiert. Das daraus entstehende Framework bezeichnen wir als tolerantes Lernen. Exaktes Lernen sowie Lernen mit endlich vielen Anomalien ergeben sich als Spezialfälle. Durch den Vergleich von Toleranzrelationen anhand der von ihnen lernbar gemachten Mengenfamilien erhalten wir eine neue Gradstruktur, die Hierarchie des toleranten Lernens. Wir erweitern die klassischen Methoden der Locking Sequences und Tell-tales auf diesen Rahmen und leiten eine kombinatorische Charakterisierung der universellen Toleranzrelationen her (das sind jene Toleranzrelationen, unter denen jede Familie nichtleerer rekursiv aufzählbarer Mengen lernbar ist). Anschließend zeigen wir, dass diese Hierarchie ein beschränkter unterer Halbverband (engl.\ bounded lower semilattice), jedoch kein oberer Halbverband ist, weder Atome noch Coatome besitzt und sowohl Ketten als auch Antiketten der Mächtigkeit des Kontinuums enthält. Darüber hinaus untersuchen wir natürliche Referenzrelationen, darunter c.e.-Index-Analoge klassischer Äquivalenzrelationen aus der deskriptiven Mengenlehre, und weisen eine weitgehende Unvergleichbarkeit ihrer Lernmächtigkeit nach. Schließlich trennen wir nicht-effektives von berechenbarem tolerantem Lernen, indem wir eine universelle Relation angeben, die nicht berechenbar universell ist. Diese Ergebnisse zeigen, dass semantische Toleranz zu einer eigenständigen Gradtheorie an der Schnittstelle zwischen algorithmischer Lerntheorie und der Theorie von Äquivalenzrelationen führt. Im vierten Kapitel bestimmen wir Schranken der Komplexität von Bi-Einbettbarkeits\-relationen auf linearen Ordnungen. Wir stratifizieren die zerstreuten (engl.\ scattered) linearen Ordnungen nach ihrem Hausdorff-Rang und erhalten, für jede abzählbare Ordinalzahl $\alpha$, die Klasse $\text{LO}_\alpha$ von linearen Ordnungen mit Hausdorff-Rang höchstens $\alpha$ und die auf diese Klasse eingeschränkte Bi-Einbettbarkeitsrelation ${\approx} \restrict \text{LO}_\alpha$. Wir präsentieren eine $\Sigma_{2\alpha+2}$-Definition von ${\approx} \restrict \text{LO}_\alpha$ in der infinitären Logik $\mathcal{L}_{\omega_1,\omega}$. Daraus folgt, dass ${\approx} \restrict \text{LO}_\alpha$ für abzählbare $\alpha$ eine $\mathbf{\Sigma}^0_{2\alpha + 2}$-Relation und daher Borel ist. Weiters können wir aus unserem Beweis schlussfolgern, dass ${\approx} \restrict \text{LO}_\alpha$ für berechenbare $\alpha$ eine $\Sigma^0_{2\alpha + 2}$-Relation ist.

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}$.