Gleichungen in Polymorphismenalgebren unendlicher Strukturen

Eine Algebra besteht aus einer Menge und Funktionen auf dieser Menge. Beispiele sind die Menge der ganzen Zahlen mit den Funktionen der Addition und Multiplikation; die Menge der der reellen Zahlen mit der Addition, der Multiplikation, und der Potenzfunktion; oder die Menge bestehend aus zwei Elementen, 0 und 1, mit der Maximumsfunktion. Aufgrund ihrer Allgemeinheit treten Algebren in allen Gebieten der Mathematik auf, und modellieren Situationen, in denen wir es mit Objekten zu tun haben (die den Elementen der Menge entsprechen, auf denen die Algebra lebt), zwischen denen es Interaktionen gibt (die den Funktionen auf den Elementen entsprechen). Theoretisch könnte man jede Algebra, welche in der Mathematik auftritt, getrennt erforschen; dies ist auch für besonders wichtige Algebren der Fall. Das Gebiet der universellen Algebra erforscht nun aber abstrakt den Zusammenhang zwischen den Gleichungen, welche in einer Algebra gelten, und deren Struktur, ohne eine konkrete Algebra zu betrachten. So erfüllt beispielsweise die Algebra auf den ganzen Zahlen mit der Addition die Gleichungen x-x+y=y=y-x+x, was allgemeine strukturelle Konsequenzen hat: jede beliebige Algebra, in der eine ähnliche Gleichung gilt, teilt mit dieser Algebra gewisse strukturelle Eigenschaften. Die Theorie der Gleichungen in endlichen Algebren, zu denen beispielsweise die oben genannte Algebra auf den Elementen 0,1 mit der Maximumsfunktion gehört, wird schon seit den Anfängen der universellen Algebra erforscht, hat aber unlängst grosse Fortschritte erfahren, seit Anwendungen in der theoretischen Informatik entdeckt wurden: es modellieren endliche Algebren nämlich bestimmte Berechnungsprobleme, und wie sich herausgestellt hat, bestimmen die Gleichungen, welche in einer Algebra gelten, die Komplexität des modellierten Berechnungsproblemes. Fast zwanzig Jahre nach dieser Entdeckung wurde schliesslich letztes Jahr klassifiziert, welche Gleichungen implizieren, dass ein Berechnungsproblem effizient gelöst werden kann. In diesem Projekt wollen wir die neuen Methoden von endlichen Algebren auf unendliche Algebren erweitern. Während schon einige sporadische und überraschende Ergebnisse in dieser Richtung für unendliche Algebren erzielt wurden, gibt es, im Unterschied zu endlichen Algebren, noch keine allgemeine Methode, um solche Ergebnisse zu zeigen. Unser Projekt ist einerseits durch die oben genannten Anwendungen in der theoretischen Informatik motiviert, andererseits hat die Erforschung der Struktur von unendlichen Algebren über ihre Gleichungen ihren Wert für sich, da diese natürlich auftreten; siehe die obigen Beispiele. Wir hoffen auch, die endlichen Methoden selbst durch ihre Anwendung in einem breiteren Kontext besser verstehen zu können.

Eine Algebra besteht aus einer Menge und Funktionen auf dieser Menge. Beispiele sind die Menge der ganzen Zahlen mit den Funktionen der Addition und Multiplikation; die Menge der der reellen Zahlen mit der Addition, der Multiplikation, und der Potenzfunktion; oder die Menge bestehend aus zwei Elementen, 0 und 1, mit der Maximumsfunktion. Aufgrund ihrer Allgemeinheit treten Algebren in allen Gebieten der Mathematik auf, und modellieren Situationen, in denen wir es mit Objekten zu tun haben (die den Elementen der Menge entsprechen, auf denen die Algebra lebt), zwischen denen es Interaktionen gibt (die den Funktionen auf den Elementen entsprechen). Theoretisch könnte man jede Algebra, welche in der Mathematik auftritt, getrennt erforschen; dies ist auch für besonders wichtige Algebren der Fall. Das Gebiet der universellen Algebra erforscht nun aber abstrakt den Zusammenhang zwischen den Gleichungen, welche in einer Algebra gelten, und deren Struktur, ohne eine konkrete Algebra zu betrachten. So erfüllt beispielsweise die Algebra auf den ganzen Zahlen mit der Addition die Gleichungen x-x+y=y=y-x+x, was allgemeine strukturelle Konsequenzen hat: jede beliebige Algebra, in der eine ähnliche Gleichung gilt, teilt mit dieser Algebra gewisse strukturelle Eigenschaften. Die Theorie der Gleichungen in endlichen Algebren, zu denen beispielsweise die oben genannte Algebra auf den Elementen 0,1 mit der Maximumsfunktion gehört, wird schon seit den Anfängen der universellen Algebra erforscht, hat aber unlängst grosse Fortschritte erfahren, seit Anwendungen in der theoretischen Informatik entdeckt wurden: es modellieren endliche Algebren nämlich bestimmte Berechnungsprobleme, und wie sich herausgestellt hat, bestimmen die Gleichungen, welche in einer Algebra gelten, die Komplexität des modellierten Berechnungsproblemes. Fast zwanzig Jahre nach dieser Entdeckung wurde schliesslich 2017 klassifiziert, welche Gleichungen implizieren, dass ein Berechnungsproblem effizient gelöst werden kann. In diesem Projekt konnten wir einige der neuen Methoden von endlichen Algebren auf unendliche Algebren erweitern.