Heterogene Algebra

Heterogene Algebren sind im mathematischen Teilgebiet der universellen Algebra untersuchte algebraische Strukturen und stellen im gewissen Sinn eine Verallgemeinerung von universellen Algebren (zu unterscheiden von der Disziplin) dar. Während bei universellen Algebren von einer einzelnen Menge als Grundmenge ausgegangen wird ist die Grundmenge einer Heterogenen Algebra ein Mengensystem.

Verwendung finden sie in der algebraischen Spezifikation, einer Form der Spezifikation eines Datentyps.

Definition

Eine Heterogene Algebra (engl. heterogeneous algebra) besteht aus einem System (Familie) von nichtleeren Grundmengen $A=(A_{j})_{j\in J}$ und einem System (Familie) von Operationen $\Omega =(\omega _{i})_{i\in I}$.

Die Operationen $\omega _{i}$ sind Abbildungen von einem (möglicherweise leeren) kartesischen Produkt der Grundmengen in eine der Grundmengen

$\omega _{i}:A_{j_{1}}\times \dots \times A_{j_{\nu }}\times \dots \times A_{j_{n}}\longrightarrow A_{k}$.

Man beachte, dass k, n und alle j_ν spezifisch für die jeweilige Operation sind. Das zu jeder Operation $\omega _{i}$ gehörende (n+1)-Tupel $(j_{1},\dots ,j_{\nu },\dots j_{n};k)\!$ bezeichnet man als den Typ dieser Operation. Eine Operation $\omega _{i}$ vom Typ $(;k)$ entspricht einer Konstanten (aus der Grundmenge A_k).

Man kann die heterogene Algebra wie folgt angeben:

${\boldsymbol {A}}=(A,\Omega )={\bigl (}(A_{j})_{j\in J},(\omega _{i})_{i\in I}{\bigr )}$

Im gegebenen Zusammenhang ist dafür auch gleichwertig die Schreibweise

${\boldsymbol {A}}=(A_{j}|j\in J,\Omega )$

gebräuchlich.

Die Familie der Typen der einzelnen Operationen $\omega _{i}$ mit Indexmenge I nennt man die Signatur (manchmal auch ebenfalls Typ) $\sigma$ der heterogenen Algebra. Haben zwei Algebren die gleiche Signatur, so sind ihre Operationen bijektiv zuordenbar.

Falls es nur eine Grundmenge gibt (wenn also I eine Einermenge ist), dass liegt eine gewöhnliche (universelle) Algebra vor.

Bemerkung
Manchmal erweist es sich auch als zweckmäßig, leere Mengen $A_{j}=\emptyset$ als Trägermengen zuzulassen, etwa damit sichergestellt ist, dass die Menge aller Unteralgebren (siehe unten) einer heterogenen Algebra einen algebraischen Verband bildet.

Verallgemeinerungen von aus universellen Algebren bekannten Begriffen

Da die Heterogene Algebra ja eine Verallgemeinerung der universellen Algebra ist, ist es von Interesse, wie sich die bekannten Begriffe und Sätze übertragen lassen.

Unteralgebren

Ein Mengensystem $U=(U_{j})_{j\in {J}}$, bei dem für jeden Index j die Teilmengenrelation $U_{j}\subseteq A_{j}$ gilt, ist genau dann Unteralgebra der heterogenen Algebra ${\boldsymbol {A}}=(A_{j}|j\in I,\Omega )={\bigl (}(A_{j})_{j\in J},\Omega {\bigr )}$, wenn alle Operationen aus $\Omega$ abgeschlossen sind (insbesondere auch die nullstelligen Operationen), also wenn gilt:

$\forall \omega _{i}\operatorname {mit} \operatorname {Typ} \ (j_{1},\dots ,j_{n};k),\qquad \forall {u_{1}}\in U_{j_{1}},\dots ,u_{n}\in U_{j_{n}}:\qquad \omega _{i}(u_{1},\dots ,u_{n})\in U_{k},\quad$

Für nullstellige (mit Typ $(;0)$, also $n\!=\!0$) Operationen $\omega _{i}$, d. h. Konstanten, bedeutet das, dass diese alle in U liegen müssen: $\omega _{i}\in U$.

Wie auch bei universellen Algebren gilt: Der mengentheoretische Durchschnitt von Unteralgebren ist stets eine Unteralgebra (sofern er nicht leer ist). Dabei ist der Durchschnitt für jedes $j\in J$ getrennt durchzuführen und keiner der Durchschnitte darf leer sein.

Homomorphismen

Seien ${\boldsymbol {A}}=(A_{j}|j\in J,\Omega )$ und ${\boldsymbol {B}}=(B_{j}|j\in J,\Omega ')$ heterogene Algebren derselben Signatur, d. h. für jedes $i$ seien $\omega _{i}$ und $\omega '_{i}$ vom gleichen Typ, etwa $(j_{1},...,j_{n};k)$.

Weiter sei gegeben ein System (Familie) von Abbildungen $(f_{j})_{j\in J}$ mit $f_{j}:A_{j}\rightarrow B_{j}$ für jedes $j$.

Seien die Funktionen $f_{j}$ nun im folgenden Sinne mit den Operationen $\omega _{i}$ vertauschbar:

$\forall \omega _{i},\omega '_{i}\ \operatorname {mit} \operatorname {gemeinsamem} \operatorname {Typ} (j_{1},...,j_{n};k),\qquad \forall \ (a_{1},\dots ,a_{n})\in A_{j_{1}}\times \dots \times A_{j_{n}}:\qquad f_{k}(\omega _{i}(a_{1},\dots ,a_{n}))=\omega '_{i}(f_{j_{1}}(a_{1}),\dots ,f_{j_{n}}(a_{n}))$

Speziell im Fall von Konstanten, d. h. für die $\omega _{i}$ mit Typ $(;k)$, muss also gelten: $f_{k}(\omega _{i})=\omega '_{i}$, wobei $\omega _{i}\in A_{k}$ und $\omega '_{i}\in B_{k}$.

Dann spricht man von einem Homomorphismus von ${\boldsymbol {A}}$ in ${\boldsymbol {B}}$.
Sind zusätzlich alle Funktionen $f_{j}$ bijektiv, so spricht man von einem Isomorphismus.

Siehe auch: Homomorphismus

Kongruenzrelationen

Siehe auch: Kongruenzrelation

Homomorphiesatz

Für jeden Homomorphismus $f$ auf einer heterogenen Algebra ist das homomorphe Bild isomorph zu ihrer Faktoralgebra nach der Kongruenzrelation $\theta {}_{f}$.

Siehe auch: Homomorphiesatz

Literatur

• Hans Kaiser, Rainer Mlitz, Gisela Zeilinger: Algebra für Informatiker. 2. Auflage. Springer-Verlag, Wien 1985, ISBN 978-3-7091-8820-0, doi:10.1007/978-3-7091-8820-0. 
• Miroslav Novotný: Homomorphisms of heterogeneous algebras, In: Czechoslovak Mathematical Journal, 52 (127), 2002, S. 415–428
• G. Birkhoff, J.D. Lipson: Heterogeneous algebras, In: Journal of Combinatorial Theory, 8, 1970, S. 115–133
• J. A. Goguen, J.W. Thatcher, E.G. Wagner, J. B. Wright: Initial algebra semantics and continuous algebras, In: Journal of the Association for Computing Machinery, 24, 1977, S. 68–95
• P. J. Higgins: Algebras with a schema of operators, In: Mathematische Nachrichten, 27, 1963, S. 115–132