Klon (Mathematik)

Ein Klon auf einer Menge $A$ ist eine Menge von Abbildungen von Potenzen von $A$ nach $A$ , 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

Ein Klon oder konkreter Klon auf einer Menge $A$ ist eine Menge $C$ , bestehend aus Funktionen $f:A^{n}\to A$ für jedes positive ganze $n$ , sodass

alle Projektionen enthalten sind, das heißt, dass für alle $1\leq k\leq n$ die Abbildung $\pi _{k}^{n}\colon A^{n}\to A$ , die auf die $k$ -te Komponente projiziert, in $C$ ist und
$C$ unter Kompositionen abgeschlossen ist, das heißt für alle $f\colon A^{m}\to A$ in $C$ und alle $g_{1},...,g_{m}\colon A^{n}\to A$ in $C$ ist auch die Abbildung $A^{n}\to A,(x_{1},...,x_{n})\mapsto f(g_{1}(x_{1},...,x_{n}),...,g_{m}(x_{1},...,x_{n}))$ in $C$ .

Ein abstrakter Klon ist eine Folge $C_{n}$ von Mengen zusammen mit Elementen $\pi _{k}^{n}\in C_{n}$ für alle $1\leq k\leq n$ sowie Kompositionsabbildungen $*\colon C_{m}\times (C_{n})^{m}\to C_{n}$ für alle $m$ und $n$ , sodass folgendes gilt:

$c*(\pi _{1}^{n},...,\pi _{n}^{n})=c$ für alle $c\in C_{n}$
$\pi _{k}^{m}*(c_{1},...,c_{m})=c_{k}$ für alle $c_{1},...,c_{m}\in C_{n}$
$c*(d_{1}*(e_{1},...,e_{n}),...,d_{m}*(e_{1},...,e_{n}))=(c*(d_{1},...,d_{m}))*(e_{1},...,e_{n})$ für alle $c\in C_{m},d_{1},...,d_{m}\in C_{n},e_{1},...,e_{n}\in C_{k}$

Jeder konkrete Klon definiert einen abstrakten Klon.

Polymorphismenklone

Sei $A$ eine Struktur über einer Signatur $\sigma$ . Ein Polymorphismus von $A$ ist ein $\sigma$ -Homomorphismus von $A^{n}$ nach $A$ . Für $n=1$ ist also ein Polymorphismus genau ein Endomorphismus.

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

Beispiele

Für eine Gruppe $(G;\circ )$ sind die Polymorphismen genau die Gruppenhomomorphismen von $G\times ...\times G$ nach $G$ .

Für einen Körper $(K;0,1,+,\cdot )$ sind die Polymorphismen genau die unitären Ringhomomorphismen $K^{n}\to K$ . Es handelt sich dabei nur deshalb nicht um Körperhomomorphismen, da $K^{n}$ im Allgemeinen kein Körper ist.
Für einen unitären Ring $R$ mit Signatur $(0,1,+,\cdot )$ sind die Polymorphismen genau die unitären Ringhomomorphismen $R^{n}\to R$ . Betrachtet man $R$ über der Signatur $(0,+,\cdot )$ , so ergeben sich stattdessen alle Ringhomomorphismen $R^{n}\to R$ einschließlich nichtunitärer Morphismen.
Ein Vektorraum $V$ über einem Körper $K$ lässt sich als Struktur über der Signatur $(+,0,(\cdot \lambda )_{\lambda \in K})$ auffassen, wobei $\cdot \lambda$ die Skalarmultiplikation mit Elementen aus dem Körper bezeichnet. Die Polymorphismen dieser Struktur sind genau die linearen Abbildungen von $V^{n}$ nach $V$ . Der Polymorphismenklon ist damit nicht die Endomophismenoperade, in der die multilinearen Abbildungen betrachtet werden.

Galoisverbindungen für Polymorphismen

Wenn $C$ ein konkreter Klon auf $A$ ist, dann heißt eine Teilmenge $B\subseteq A^{m}$ stabil unter $C$ , wenn für alle $(b_{1,1},...,b_{1,m}),...,(b_{n,1},...,b_{n,m})\in B$ und alle $f\colon A^{n}\to A\in C$ auch das Tupel $(f(b_{1,1},...,b_{n,1}),...,f(b_{1,m},...,b_{n,m}))$ in $B$ liegt.

Wenn $(A;\sigma )$ eine endliche Struktur ist, dann ist eine Teilmenge $B\subseteq A^{n}$ genau dann stabil unter den Polymorphismen von $(A,\sigma )$ , wenn $B$ aus $\sigma$ primitiv positiv definierbar ist. Dabei heißt letzteres, dass $B$ definierbar in Logik erster Stufe ist, wobei nur Existenzquantoren, Und-Verknüpfungen, Falsum und Beziehungen aus $\sigma$ , sowie Gleichheit von Variablen zugelassen sind. Negationen, Allquantoren, sowie Oder-Verknüpfungen sind explizit ausgeschlossen.

Polymorphismen und Komplexitätstheorie

Für zwei Strukturen $(A;\sigma )$ und $(B;\sigma )$ über derselben Signatur lässt sich die Menge der $\sigma$ -Homomorphismen von $B$ nach $A$ untersuchen. Falls $A$ und $B$ 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 $(A;\sigma )$ ist das Folgende: Man finde für eine endliche Struktur $(B;\sigma )$ , die als Eingabe übergeben wird, heraus, ob es einen $\sigma$ -Homomorphismus von $B$ nach $A$ gibt. Die Komplexitätsklasse dieses Problems hängt von dem Vorhandensein von Polymorphismen von $A$ ab.

Eine Siggersfunktion ist ein Polymorphismus $s:A^{6}\to A$ , der die Identität $s(x,y,z,x,y,z)=s(y,z,x,z,x,y)$ erfüllt.

Das Bedingungserfüllbarkeitsproblem zu einer endlichen Struktur $A$ ist in P, falls es eine Siggersfunktion gibt und ansonsten NP-vollständig.

Einzelnachweise

↑ 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.
↑ David Geiger: Closed systems of functions and predicates. In: Pacific Journal of Mathematics. Band 27, Nr. 1, 1968, S. 95–100, Theorem 2.
↑ Manuel Bodirsky, Thomas Quinn-Gregson: Solving Equation Systems in $\omega$ -categorical Algebras. In: arXiv:1912.09815 [cs, math]. 31. Januar 2020, Theorem 2.1, arxiv:1912.09815v2 [abs].
↑ 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.
↑ 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].
↑ 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].

[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 $\omega$ -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].