Ein Klon auf einer Menge ist eine Menge von Abbildungen von Potenzen von nach , die die Projektionen enthält und unter Kompositionen abgeschlossen ist. Klone lassen sich als Spezialfall von Operaden auffassen. Sie werden in der universellen Algebra untersucht.

Definition

Bearbeiten

Ein Klon oder konkreter Klon auf einer Menge   ist eine Menge  , bestehend aus Funktionen   für jedes positive ganze  , sodass

  • alle Projektionen enthalten sind, das heißt, dass für alle   die Abbildung  , die auf die  -te Komponente projiziert, in   ist und
  •   unter Kompositionen abgeschlossen ist, das heißt für alle   in   und alle   in   ist auch die Abbildung   in  .

Ein abstrakter Klon[1] ist eine Folge   von Mengen zusammen mit Elementen   für alle   sowie Kompositionsabbildungen   für alle   und  , sodass folgendes gilt:

  •   für alle  
  •   für alle  
  •   für alle  

Jeder konkrete Klon definiert einen abstrakten Klon.

Polymorphismenklone

Bearbeiten

Sei   eine Struktur über einer Signatur  . Ein Polymorphismus von   ist ein  -Homomorphismus von   nach  . Für   ist also ein Polymorphismus genau ein Endomorphismus.

Die Menge aller Polymorphismen auf einer Struktur bildet einen Klon, den sogenannten Polymorphismenklon.

Beispiele

Bearbeiten
  • Für eine Gruppe   sind die Polymorphismen genau die Gruppenhomomorphismen von   nach  .
  • Für einen Körper   sind die Polymorphismen genau die unitären Ringhomomorphismen  . Es handelt sich dabei nur deshalb nicht um Körperhomomorphismen, da   im Allgemeinen kein Körper ist.
  • Für einen unitären Ring   mit Signatur   sind die Polymorphismen genau die unitären Ringhomomorphismen  . Betrachtet man   über der Signatur  , so ergeben sich stattdessen alle Ringhomomorphismen   einschließlich nichtunitärer Morphismen.
  • Ein Vektorraum   über einem Körper   lässt sich als Struktur über der Signatur   auffassen, wobei   die Skalarmultiplikation mit Elementen aus dem Körper bezeichnet. Die Polymorphismen dieser Struktur sind genau die linearen Abbildungen von   nach  . Der Polymorphismenklon ist damit nicht die Endomophismenpoerade, in der die multilinearen Abbildungen betrachtet werden.

Galoisverbindungen für Polymorphismen

Bearbeiten

Wenn   ein konkreter Klon auf   ist, dann heißt eine Teilmenge   stabil unter  , wenn für alle   und alle   auch das Tupel   in   liegt.

Wenn   eine endliche Struktur ist, dann ist eine Teilmenge   genau dann stabil unter den Polymorphismen von  , wenn   aus   primitiv positiv definierbar ist.[2] Dabei heißt letzteres, dass   definierbar in Logik erster Stufe ist, wobei nur Existenzquantoren, Und-Verknüpfungen, Falsum und Beziehungen aus  , sowie Gleichheit von Variablen zugelassen sind. Negationen, Allquantoren, sowie Oder-Verknüpfungen sind explizit ausgeschlossen.

Polymorphismen und Komplexitätstheorie

Bearbeiten

Für zwei Strukturen   und   über derselben Signatur lässt sich die Menge der  -Homomorphismen von   nach   untersuchen. Falls   und   endliche Mengen sind, so ist es ein endliches Problem, zu entscheiden ob diese Menge leer ist. Das Bedingungserfüllbarkeitsproblem (aus dem Englischen auch constraint satisfaction problem, CSP) zu einer Struktur   ist das Folgende: Man finde für eine endliche Struktur  , die als Eingabe übergeben wird, heraus, ob es einen  -Homomorphismus von   nach   gibt. Die Komplexitätsklasse dieses Problems hängt von dem Vorhandensein von Polymorphismen von   ab.

Eine Siggersfunktion ist ein Polymorphismus  , der die Identität   erfüllt.

Das Bedingungserfüllbarkeitsproblem zu einer endlichen Struktur   ist in P, falls es eine Siggersfunktion gibt und ansonsten NP-vollständig.[3][4][5][6]

Einzelnachweise

Bearbeiten
  1. Paul Moritz Cohn: Universal Algebra. In: Mathematics and its Applications. 2. Auflage. Band 6. D. Reidel Publishing Co., Dordrecht-Boston, Mass., USA 1991, ISBN 978-90-277-1254-7, S. 127.
  2. David Geiger: Closed systems of functions and predicates. In: Pacific Journal of Mathematics. Band 27, Nr. 1, 1968, S. 95–100, Theorem 2.
  3. Manuel Bodirsky, Thomas Quinn-Gregson: Solving Equation Systems in  -categorical Algebras. In: arXiv:1912.09815 [cs, math]. 31. Januar 2020, Theorem 2.1, arxiv:1912.09815v2 [abs].
  4. Mark H. Siggers: A strong Mal’cev condition for varieties omitting the unary type. In: Algebra Universalis. Band 64, Nr. 1, 2010, S. 15–20.
  5. Andrei A. Bulatov: A dichotomy theorem for nonuniform CSPs. In: FOCS 2017 (Hrsg.): 58th IEEE annual symposium on foundations of computer science. berkeley, ca, usa 17. Oktober 2017, S. 319–330, arxiv:1703.03021 [abs].
  6. Dmitriy Zhuk: A proof of CSP dichotomy conjecture. In: FOCS 2017 (Hrsg.): 58th IEEE annual symposium on founda- tions of computer science. berkeley, ca, usa 17. Oktober 2017, S. 331–342, arxiv:1704.01914 [abs].