Heterogene Algebra

Heterogene Algebren s​ind im mathematischen Teilgebiet d​er universellen Algebra untersuchte algebraische Strukturen u​nd stellen i​n gewissem Sinn e​ine Verallgemeinerung v​on universellen Algebren (zu unterscheiden v​on der Disziplin) dar. Während b​ei universellen Algebren v​on einer einzelnen Menge a​ls Grundmenge ausgegangen wird, i​st die Grundmenge e​iner heterogenen Algebra e​in Mengensystem.

Verwendung finden s​ie in d​er algebraischen Spezifikation, e​iner Form d​er Spezifikation e​ines Datentyps.

Definition

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

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

${\displaystyle \omega _{i}\colon A_{j_{1}}\times \dotsb \times A_{j_{\nu }}\times \dotsb \times A_{j_{n}}\longrightarrow A_{k}}$.

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

Man k​ann die heterogene Algebra w​ie folgt angeben:

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

In gegebenem Zusammenhang i​st dafür a​uch gleichwertig d​ie Schreibweise

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

gebräuchlich.

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

Falls es nur eine Grundmenge gibt (wenn also ${\displaystyle I}$ eine Einermenge ist), dann liegt eine gewöhnliche (universelle) Algebra vor.

Bemerkungen

1. Manchmal erweist es sich auch als zweckmäßig, leere Mengen ${\displaystyle 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.
2. Ersetzt man in der obigen Definition den Begriff Verknüpfung durch partielle Verknüpfung, dann spricht man von einer partiellen heterogenen Algebra. Vernüpfungswerte müssen hier nicht für alle Parameter (${\displaystyle n}$-Tupel-Kombinationen) definiert sein.

Verallgemeinerungen von aus universellen Algebren bekannten Begriffen

Da d​ie heterogene Algebra e​ine Verallgemeinerung d​er universellen Algebra ist, i​st es v​on Interesse, w​ie sich d​ie bekannten Begriffe u​nd Sätze übertragen lassen.

Unteralgebren

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

${\displaystyle \omega _{i}(u_{1},\dots ,u_{n})\in U_{k}}$ für alle ${\displaystyle \omega _{i}}$ mit Typ ${\displaystyle (j_{1},\dotsc ,j_{n};k)}$ und für alle ${\displaystyle {u_{1}}\in U_{j_{1}},\dotsc ,u_{n}\in U_{j_{n}}}$

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

${\displaystyle \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 ${\displaystyle j\in J}$ getrennt durchzuführen und keiner der Durchschnitte darf leer sein.

Homomorphismen

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

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

Seien die Funktionen ${\displaystyle f_{j}}$ nun in folgendem Sinne mit den Operationen ${\displaystyle \omega _{i}}$ vertauschbar:

Für alle ${\displaystyle \omega _{i},\omega '_{i}}$ mit gemeinsamem Typ ${\displaystyle (j_{1},\dotsc ,j_{n};k)}$ und für alle ${\displaystyle (a_{1},\dotsc ,a_{n})\in A_{j_{1}}\times \dotsb \times A_{j_{n}}}$ gilt:

${\displaystyle f_{k}(\omega _{i}(a_{1},\dotsc ,a_{n}))=\omega '_{i}(f_{j_{1}}(a_{1}),\dotsc ,f_{j_{n}}(a_{n}))}$

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

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

Homomorphiesatz

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

Siehe auch: Homomorphiesatz

Beispiele für heterogene Algebren

Vektorräume

Ein Vektorraum ${\displaystyle (V,\oplus ,\odot )}$ über einem Körper ${\displaystyle (K,+,\cdot )}$ ist eine heterogene Algebra mit den zwei Grundmengen ${\displaystyle A_{1}=V}$ und ${\displaystyle A_{2}=K}$. Für die zweistelligen Operationen gilt Folgendes:

• ${\displaystyle \oplus \colon A_{1}\times A_{1}\to A_{1}}$ hat Typ ${\displaystyle (1,1;1)}$.
• ${\displaystyle \odot \colon A_{2}\times A_{1}\to A_{1}}$ hat Typ ${\displaystyle (2,1;1)}$.
• ${\displaystyle +\colon A_{2}\times A_{2}\to A_{2}}$ hat Typ ${\displaystyle (2,2;2)}$.
• ${\displaystyle \cdot \colon A_{2}\times A_{2}\to A_{2}}$ hat Typ ${\displaystyle (2,2;2)}$.

In quantorenfreier Notation der Axiome (ohne Existenzquantor) kommen noch dazu als einstellige Operationen die Bildung des additiven Inversen (Negativen) in ${\displaystyle (V,\oplus )}$ und des additiven und multiplikativen Inversen in ${\displaystyle (K,+,\cdot )}$, sowie als Konstanten (nullstellige Operationen) der Nullvektor ${\displaystyle 0_{V}}$ in ${\displaystyle (V,\oplus )}$ und Null- und Einselement ${\displaystyle 0,1}$ in ${\displaystyle (K,+,\cdot )}$:

• ${\displaystyle \ominus \colon A_{1}\to A_{1}}$ hat Typ ${\displaystyle (1;1)}$.
• ${\displaystyle -\colon A_{2}\to A_{2}}$ hat Typ ${\displaystyle (2;2)}$.
• ${\displaystyle \operatorname {inv} ={}^{-1}\colon A_{2}\not \to A_{2}}$ hat Typ ${\displaystyle (2;2)}$ (als partielle Operation).
• ${\displaystyle 0_{V}\in A_{1}}$ hat Typ ${\displaystyle (;1)}$ (als Konstante ${\displaystyle {A_{1}}^{0}=\{\emptyset \}\to A_{1}}$, siehe leeres Produkt).
• ${\displaystyle 0\in A_{2}}$ und ${\displaystyle 1\in A_{2}}$ haben beide Typ ${\displaystyle (;2)}$.

Streng genommen ist der Vektorraum also eine partielle heterogene Struktur.
Verallgemeinerungen sind Links- und Rechtsvektorräume über Schiefkörpern (Wegfall der multiplikativen Kommutativität der Skalare). Spezielle Vektorräume sind die Algebren über einem Körper (K-Algebren, veraltet auch: lineare Algebren) und Lie-Algebren.

Moduln

Ein Modul ${\displaystyle (M,\oplus ,\odot )}$ über einem kommutativen Ring ${\displaystyle (R,+,\cdot )}$ mit Einselement ${\displaystyle 1}$ ist eine heterogene Algebra mit den zwei Grundmengen ${\displaystyle A_{1}=M}$ und ${\displaystyle A_{2}=R}$. Moduln sind verallgemeinerte Vektorräume, für die Operationen gelten analoge Regeln wie oben. Weitere Verallgemeinerungen bestehen im Wegfall der multiplikativen Kommutativität der Skalare (wobei dann zwischen Links- und Rechtsmoduln unterschieden werden muss) oder des Einselements.

Peirce-Algebren

Eine Peirce-Algebra ist eine abstrakte Relationsalgebra zusammen mit Links- und Rechtsverknüfungen mit Elementen weiterer Trägermengen. Ein Beispiel sind zweistellige Relationen ${\displaystyle R\subseteq A\times B}$ zwischen Elementen zweier Mengen ${\displaystyle A}$ und ${\displaystyle B}$ (Vor- und Nachbereich) zusammen mit Vor- und Nachbeschränkung auf Teilmengen von ${\displaystyle A}$ bzw. ${\displaystyle B}$.

Köcher

Ein Köcher ${\displaystyle \Gamma =(V,E,\operatorname {s} ,\operatorname {t} )}$ in der Graphentheorie ist eine heterogene Algebra mit zwei Grundmengen ${\displaystyle A_{1}=V}$ (Punkten oder Knoten genannt) und ${\displaystyle A_{2}=E}$ (Pfeile oder gerichtete Kanten genannt). Die einstelligen Operationen ${\displaystyle \operatorname {s} }$ und ${\displaystyle \operatorname {t} }$ sind beide vom Typ ${\displaystyle (2;1)}$ und ordnen jedem Pfeil seinen Anfangs- und Endpunkt zu.

Kleine Kategorien

Eine kleine Kategorie ${\displaystyle {\mathcal {C}}=({\mathit {\Omega }},M,\operatorname {dom} ,\operatorname {cod} ,\circ ,\operatorname {id} )}$ in der Kategorientheorie ist eine (partielle) heterogene Algebra mit zwei Grundmengen[2] ${\displaystyle A_{1}={\mathit {\Omega }}=\operatorname {Ob} ({\mathcal {C}})}$ (Objekte genannt) und ${\displaystyle A_{2}=M=\operatorname {Ar} ({\mathcal {C}})}$ (Morphismen oder Pfeile genannt). Die einstelligen Operationen ${\displaystyle \operatorname {dom} }$ und ${\displaystyle \operatorname {cod} }$ sind beide vom Typ ${\displaystyle (2;1)}$ und ordnen jedem Morphismus (Pfeil) sein Quell- und Zielobjekt zu. ${\displaystyle \circ }$ ist eine zweistellige partielle Verknüpfung vom Typ ${\displaystyle (2,2;1)}$ und ordnet je zwei Morphismen ${\displaystyle f,g}$ mit ${\displaystyle \operatorname {cod} (f)=\operatorname {dom} (g)}$ die Verknüpfung ${\displaystyle g\circ f}$ zu. Die Identitätsabbildung ${\displaystyle \operatorname {id} }$ ist eine einstellige Verknüpfung vom Typ ${\displaystyle (1;2)}$, die jedem Objekt ${\displaystyle X}$ seinen Identitätsmorphismus ${\displaystyle \operatorname {id} _{X}}$ mit ${\displaystyle \operatorname {dom} (\operatorname {id} _{X})=\operatorname {cod} (\operatorname {id} _{X})=X}$ zuordnet. Die ersten vier Komponenten einer kleinen Kategorie ${\displaystyle {\mathcal {C}}=({\mathit {\Omega }},M,\operatorname {dom} ,\operatorname {cod} ,\circ ,\operatorname {id} )}$ definieren einen Köcher ${\displaystyle \Gamma =({\mathit {\Omega }},M,\operatorname {dom} ,\operatorname {cod} )}$.

Endliche Automaten

Ein endlicher Automat ${\displaystyle (\Sigma ,S,s_{0},\delta ,F)}$ in der Automatentheorie ist eine heterogene Algebra[3] mit den zwei Grundmengen ${\displaystyle A_{1}=\Sigma }$ (dem Eingabealphabet) und ${\displaystyle A_{2}=S}$ (der Menge der Zustände). Für die Operationen gilt Folgendes:

• Der Anfangszustand ${\displaystyle s_{0}\colon \to A_{2}}$ hat Typ ${\displaystyle (;2)}$.
• Die Zustandsübergangsfunktion ${\displaystyle \delta \colon A_{2}\times A_{1}\to A_{2}}$ hat Typ ${\displaystyle (2,1;2)}$.

Anmerkungen und Einzelnachweise

1. Man kann die Indexmenge ${\displaystyle I}$ verstehen als ein Alphabet von Bezeichnern (Sorten) der Grundmengen und die Indexmenge ${\displaystyle J}$ als eine Menge von Funktionssymbolen (oder -bezeichnern).
2. Die Beschränkung auf Grundmengen bedeutet, dass ${\displaystyle {\mathcal {C}}}$ eine kleine Kategorie ist. In der Kategorientheorie bilden allerdings die Objekte und Morphismen der betrachteten Kategorien gewöhnlich eigentliche Klassen statt Mengen.
3. Opolka 2010, S. 141.

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.
• Hans Opolka: Algebra für die Informatik. Bei: TU-Braunschweig.de. Institut für Analysis und Algebra. PDF, 2010, kein Zugriff ohne Berechtigung.