Klon (Mathematik)
# 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 Endomophismenpoerade, 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.

