Äquivalenzrelationen in berechenbarer Modelltheorie

Äquivalenzrelationen stellen einen Begriff der Ähnlichkeit von mathematischen Objekten dar. Objekte, die modulo einer Äquivalenzrelation gleich sind, haben ähnliche strukturelle Eigenschaften. Aus Sicht der berechenbaren Modelltheorie gibt es mehrere Ansätze, um die Rolle von Äquivalenzrelationen zu untersuchen. In diesem Projekt behandeln wir zwei mögliche Vorgehensweisen. Der erste Anzatz steht in Verbindung zur Frage der algorithmischen Komplexität von verschiedenen Repräsentationen einer Struktur. Um die Grade isomorpher Kopien der Struktur zu beschreiben, verwendet man den Begriff des Grad-Spektrums. Es besteht aus allen Turing-Graden von isomorphen Kopien der Struktur. Für viele Strukturen, mit verschiedensten computationalen und modelltheoretischen Eigenschaften, wurden die Grad-Spektren bereits ausfhrlich untersucht. Kürzlich wurde auch der Begriff eines Grad- Spektrums für eine Theorie eingeführt. Es besteht aus allen Turing-Graden von Modellen der Theorie. Wir schlagen einen neuen Begriff vor, der die Ideen von Spektren für Strukturen und Theorien verallgemeinert. Unsere Spectren bestehen aus allen Graden von Strukturen, die zu der gegebenen Struktur äquivalent sind, hinsichtlich einer beliebigen ausgesuchten Äquivalenzrelation. Für das vorliegende Projekt befassen wir uns mit Restriktionen von den Äquivalenzrelationen von Isomorphismus, elementarer Äquivalenz und Bi- Einbettbarkeit. Die Hauptfrage ist: welche Spektren sind für verschiedene Äquivalenzrelationen möglich? Der zweite Ansatz befasst sich mit der Komplexität einer Beschreibung für Äquivalenzrelationen. Wir identifizieren Äquivalenzrelationen auf berechenbaren Strukturen mit Relationen auf Indizes für solche Strukturen. Ihre Komplexität vergleicht man mit Hilfe berechenbarer Reduzierbarkeit, die eine 2- dimensionale Version der m-Reduzierbarkeit darstellt. Wir schlagen vor, die Repräsentierbarkeit beliebiger Äquivalenzrelationen auf natürlichen Zahlen durch bestimmte Äquivalenzrelationen auf berechenbaren Strkturen zu untersuchen. Außerdem schlagen wir vor, Relativisierungen der berechenbaren Reduzierbarkeit auf höheren Komplexitätsebenen zu untersuchen.

Äquivalenzrelationen stellen einen Begriff der Ähnlichkeit von mathematischen Objekten dar. Eine essenzielle Frage ist die Frage, ob es eine mathematische Struktur mit bestimmten Eigenschaften gibt, modulo einer Äquivalenzrelation. In berechenbarer Strukturtheorie untersucht man, ob eine bestimmte Struktur eine berechenbare Präsentation hat, d.h., ob die Struktur zur einer berechenbaren Struktur äquivalent ist. Falls das nicht der Fall ist, was sind die Turinggrade von äquivalenten Präsentationen der Struktur? Diese Frage war im Fokus des Projektes. Wir haben einen neuen Begriff eingeführt, der die Ideen von Spektren für Strukturen und Theorien verallgemeinert. Unsere Spektren bestehen aus allen Graden von Strukturen, die zu der gegebenen Struktur äquivalent sind, hinsichtlich einer beliebigen ausgesuchten Äquivalenzrelation. Außerdem, haben wir die Komplexität von Funktionen untersucht, die Äquivalenzrelationen zwischen Strukturen realisieren, in Einklang mit dem klassischen Anzatz der berechenbaren Kategorizität. Weiters haben wir die Struktur der Äquivalenzrelationen hinsichtlich berechenbarer Reduzierbarkeit untersucht. Schließlich, haben wir eine neue Forschungsrichtung begonnen, die sich mit on-the-fly Klassifikation von Strukturen befasst, in dem wir Ideen von berechenbarer Strukturtheorie und von algoritmischem Lernen zusammenbringen.