Klon (Mathematik)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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 | Quelltext 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.

  • 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 | Quelltext 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 | Quelltext 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 | Quelltext 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].