Clones and homogeneous structures

Abstract

Eine Struktur A heißt homogen, falls sich jeder Isomorphismus zwischen endlich erzeugten Unterstrukturen zu einem Automorphismus von A fortsetzen lässt. Eine Konstruktionsmethode solcher Strukturen wurde erstmals von Fraissé 1954 beschrieben; seitdem wurden homogene Strukturen zu einem Objekt von Interesse in zahlreichen Gebieten der Mathematik, insbesondere in der Modelltheorie, Ramsey Theorie, der Theorie unendlicher Permutationsgruppen und der theoretischen Informatik. In Kapitel 1 geben wir eine Einführung zu homogenen Strukturen und legen dabei den Schwerpunkt auf Resultate, die für den Rest der Arbeit von Bedeutung sind. Ein wichtiges offenes Problem auf dem Gebiet ist die Vermutung von Thomas, die besagt, dass jede abzählbare homogene Struktur A in endlicher relationaler Sprache bis auf Interdefinierbarkeit nur endliche viele Redukte hat, sprich, dass in Logik erster Ordnung nur endlich viele Strukturen über A definiert werden können. In Kapitel 2 bestimmen wir alle Redukte jener homogenen gerichteten Graphen, die von Henson beschrieben wurden. Wir zeigen, dass all diese kontinuum viele, homogene Digraphen nur endlich viele Redukte haben, was im Einklang mit Thomas’ Vermutung steht. Als Korollar unserer Klassifizierung können wir zeigen, dass die symmetrische Gruppe auf einer abzählbaren Menge kontinuum viele nicht-isomorphe maximale abgeschlossene Untergruppen hat. Dies beantwortet einen offene Frage von Macpherson. In Kapitel 3 bestimmen wir die Komplexität einer Familie von Problem aus der theoretischen Informatik, bei denen der Input aus quantorenfreien Formeln in der Sprache der Ordnungen besteht, und die Frage ist, ob es eine partielle Ordnung gibt, in der diese Formeln erfüllbar sind. Diese Probleme können als constraint satisfaction problems von Redukten der random partial order P modelliert werden, also jener homogenen Struktur, die als Fraıssé-Grenzwert der Klasse aller endlichen partiellen Ordnungen gebildet werden kann. Die Redukte von P sind bereits bis auf first-order Interdefinierbarkeit bestimmt. Wir verfeinern diese Ergebnisse, und untersuchen Eigenschaften der primitiv positiven Theorie der Redukte. Dadurch können wir zeigen, dass alle obigen Erfüllbarkeitsprobleme entweder in P oder NP-vollständig sind. Dabei verwenden wir Methoden aus der universellen Algebra: Genauso wie die Automorphismengruppe Aut(A) einer ω-kategorischen Struktur A, diese bis auf first-order Interdefinierbarkeit bestimmt, legt der sogenannten Polymorphismenklon Pol(A), also die Algebra aller Homomorphismen A n A die Struktur A bist auf primitiv-positive Definierbarkeit fest. Wir untersuchen folglich den Verband aller Polymorphismenklone, die Aut(P) enthalten. Sowohl Kapitel 3 als auch Kapitel 2 bauen stark auf die Ramsey-theoretischen Methoden, die von Bodirsky und Pinsker entwickelt wurden und sich bereits vielfach als wichtiges Werkzeug im Klassifizieren von Redukten erwiesen haben. In Kapitel 4 beschäftigen wir uns mit einer Fragestellung zur “Rekonstruierbarkeit” ω-kategorische Strukturen. Zwei ω-kategorische Strukturen sind first-order interdefinierbar (bzw. bi-interpretierbar), genau dann wenn ihre Automorphismengruppen übereinstimmen (bzw. topologisch isomorph sind). Dies motiviert die Fragestellung, inwieweit eine ω-kategorische Struktur bereits aus der Automorphismengruppe als abstrakter Gruppe rekonstruiert werden kann. Obwohl es zahlreichen positiven Resultate auf dem Gebiet gibt, wurde von Evans und Hewitt gezeigt, dass es zwei ω-kategorische Strukturen gibt, die zwar isomorphe, aber nicht topologisch isomorphe Automorphismengruppen haben. Wir zeigen, dass dieses Gegenbeispiel derart modifiziert werden kann, dass auch die Endomorphismen-Monoide und Polymorphismen-Klone der beiden Strukturen jeweils isomorph, aber nicht topologisch isomorph sind. Die Kapitel 2, 3 und 4 entsprechen jeweils den Publikationen [AK15] (mit Lovkush Agarwal), [KP17] (mit Trung Van Pham) und [BEKP] (mit Manuel Bodirsky, David Evans und Michael Pinsker).

A structure A is called homogeneous, if every isomorphism between its finitely generated substructures extends to an automorphism of A. In this thesis we are studying homogeneous structures with countable domains. A method to construct such structures was introduced by Fraıssé in 1954]; since then homogeneous structures became subject of interest in various areas of mathematics, in particular model theory, infinite permutation groups, Ramsey theory and theoretical computer science. In Chapter 1 we give an introduction to homogeneous structures, focussing on theoretical background needed for the rest of the thesis. An important open problem regarding homogeneous structures is Thomas’ conjecture, which claims that every countable homogeneous structure in a finite relational language has finitely many reducts up to first-order interdefinability. In Chapter 2 of this thesis we classify the reducts of the homogeneous digraphs that were described by Henson. For all of these continuum many Henson digraphs there are only finitely many first-order reducts, which is in accordance with Thomas’ conjecture. Our proof uses the well-know fact that reducts of an ω- categorical structure A correspond to the closed supergroups of the automorphism group Aut(A). As a corollary of our result we can show that Sym(ω), the symmetric group on a countable set, has continuum many non-isomorphic maximal closed subgroups, which answers an open question by Macpherson [BM16]. In Chapter 3 we discuss the complexity of a class of problems from theoretical computer science, where the input consists of quantifier-free formulas in the language of orders and the question is, whether there is a partial order that satisfies the formulas. These problems can be modeled as constraint satisfaction problems of reducts of the random partial order P, which is a well-known homogeneous structure. The reducts of P are already known up to first-order definability. We refine this result and discuss properties of the primitive positive theory of those structures. This enables us to prove a dichotomy result: All the decision problems described above are either in P or NP-complete. As in the previous chapter we use algebraic methods to prove our result. The so called polymorphism clone Pol(A) of a structure A is the algebra consisting of all homomorphisms A n A. For ω-categorical structures, the relations on A that are invariant under the action of Pol(A) are exactly the primitive positive definable relations in A. Hence, studying reducts of P up to primitive positive definability is equivalent to study the lattice of closed clones containing Aut(P). Both Chapter 2 and Chapter 3 rely on the Ramsey theoretical methods developed by Bodirsky and Pinsker that proved to be a useful tool in studying reducts in many classifications. In Chapter 4 of the thesis we discuss a questions about “reconstruction”. It is a well known result that two ω-categorical structures are first-order interdefinable (respectively bi-interpretable) if and only if their automorphism groups are equal (respectively topologically isomorphic). These facts motivate the question whether an ω-categorical structures can be already reconstructed from its automorphism group as an abstract group. Evans and Hewitt gave a counterexample of two ω-categorical structures with isomorphic, but not topologically isomorphic automorphism groups. We modify their result and construct two ω-categorical structures such that also the endomorphism monoids and polymorphism clones are isomorphic, but not topologically isomorphic. The chapters 2, 3 and 4 correspond to the publications [AK15] (with Lovkush Agarwal), [KP17] (with Trung Van Pham) and [BEKP] (with Manuel Bodirsky, David Evans und Michael Pinsker).