Äquivalenzrelationen in berechenbarer Modelltheorie

01.10.2015 - 30.09.2019
Forschungsförderungsprojekt

 A¿quivalenzrelationen stellen einen Begriff der A¿hnlichkeit von mathematischen Objekten dar. Objekte, die modulo einer A¿quivalenzrelation gleich sind, haben a¿hnliche strukturelle Eigenschaften. Aus Sicht der berechenbaren Modelltheorie gibt es mehrere Ansa¿tze, um die Rolle von A¿quivalenzrelationen zu untersuchen. In diesem Projekt behandeln wir zwei mo¿gliche Vorgehensweisen.

Der erste Anzatz steht in Verbindung zur Frage der algorithmischen Komplexita¿t von verschiedenen Repra¿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. Fu¿r viele Strukturen, mit verschiedensten computationalen und modelltheoretischen Eigenschaften, wurden die Grad-Spektren bereits ausfhrlich untersucht. Ku¿rzlich wurde auch der Begriff eines Grad- Spektrums fu¿r eine Theorie eingefu¿hrt. Es besteht aus allen Turing-Graden von Modellen der Theorie. Wir schlagen einen neuen Begriff vor, der die Ideen von Spektren fu¿r Strukturen und Theorien verallgemeinert. Unsere Spectren bestehen aus allen Graden von Strukturen, die zu der gegebenen Struktur a¿quivalent sind, hinsichtlich einer beliebigen ausgesuchten A¿quivalenzrelation. Fu¿r das vorliegende Projekt befassen wir uns mit Restriktionen von den A¿quivalenzrelationen von Isomorphismus, elementarer A¿quivalenz und Bi- Einbettbarkeit. Die Hauptfrage ist: welche Spektren sind fu¿r verschiedene A¿quivalenzrelationen mo¿glich?

Der zweite Ansatz befasst sich mit der Komplexita¿t einer Beschreibung fu¿r A¿quivalenzrelationen. Wir identifizieren A¿quivalenzrelationen auf berechenbaren Strukturen mit Relationen auf Indizes fu¿r solche Strukturen. Ihre Komplexita¿t vergleicht man mit Hilfe berechenbarer Reduzierbarkeit, die eine 2- dimensionale Version der m-Reduzierbarkeit darstellt. Wir schlagen vor, die Repra¿sentierbarkeit beliebiger A¿quivalenzrelationen auf natu¿rlichen Zahlen durch bestimmte A¿quivalenzrelationen auf berechenbaren Strkturen zu untersuchen. Außerdem schlagen wir vor, Relativisierungen der berechenbaren Reduzierbarkeit auf ho¿heren Komplexita¿tsebenen zu untersuchen. 

Personen

Projektleiter_in

Institut

Förderungsmittel

  • Fonds zur Förderung der wissenschaftlichen Forschung (FWF) (Nationale Förderung) Förderschiene Einzelprojekt Förderprogramm Fonds zur Förderung der wissenschaftlichen Forschung (FWF) Fördergeber Forschungsförderungsgesellschaft Reichweite Nationale Förderung Projekttyp Forschungsförderungsprojekt

Forschungsschwerpunkte

  • Additional Fields of Research