Heterogene Algebra

Algebraische Struktur die als Grundmenge ein Mengensystem hat

Heterogene Algebren sind im mathematischen Teilgebiet der universellen Algebra untersuchte algebraische Strukturen und stellen in gewissem 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

Bearbeiten

Eine heterogene Algebra (engl. heterogeneous algebra) besteht aus einem System (einer Familie) von nichtleeren Grundmengen   und einem System (einer Familie) von Operationen  .

Die Operationen   sind Abbildungen von einem (möglicherweise leeren) kartesischen Produkt der Grundmengen in eine der Grundmengen

 .

Man beachte, dass   und alle   spezifisch für die jeweilige Operation sind. Das zu jeder Operation   gehörende  -Tupel   bezeichnet man als den Typ dieser Operation. Eine Operation   vom Typ   entspricht einer Konstanten (aus der Grundmenge  ).

Man kann die heterogene Algebra wie folgt angeben:

 

In gegebenem Zusammenhang ist dafür auch gleichwertig die Schreibweise

 

gebräuchlich.

Die Familie der Typen der einzelnen Operationen   mit Indexmenge   nennt man die (vielsortige) Signatur (manchmal auch ebenfalls Typ)   der heterogenen Algebra.[1] Haben zwei Algebren die gleiche Signatur, so sind ihre Operationen bijektiv zuordenbar.

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

Bemerkungen

Bearbeiten
  1. Manchmal erweist es sich auch als zweckmäßig, leere Mengen   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 ( -Tupel-Kombinationen) definiert sein.

Verallgemeinerungen von aus universellen Algebren bekannten Begriffen

Bearbeiten

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

Unteralgebren

Bearbeiten

Ein Mengensystem  , bei dem für jeden Index   die Teilmengenrelation   gilt, ist genau dann Unteralgebra der heterogenen Algebra  , wenn alle Operationen aus   abgeschlossen sind (insbesondere auch die nullstelligen Operationen), wenn also gilt:

  für alle   mit Typ   und für alle  

Für nullstellige Operationen   (mit Typ  , also  ), d. h. Konstanten, bedeutet das, dass diese alle in   liegen müssen:

 

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   getrennt durchzuführen und keiner der Durchschnitte darf leer sein.

Homomorphismen

Bearbeiten

Seien   und   heterogene Algebren derselben Signatur, d. h., für jedes   seien   und   vom gleichen Typ, etwa  .

Weiter sei gegeben ein System (eine Familie) von Abbildungen   mit   für jedes  .

Seien die Funktionen   nun in folgendem Sinne mit den Operationen   vertauschbar:

Für alle   mit gemeinsamem Typ   und für alle   gilt:
 

Speziell im Fall von Konstanten, d. h. für die   mit Typ  , muss also gelten:   mit   und  .

Dann spricht man von einem Homomorphismus von   in  .
Sind zusätzlich alle Funktionen   bijektiv, so spricht man von einem Isomorphismus.

Homomorphiesatz

Bearbeiten

Für jeden Homomorphismus   auf einer heterogenen Algebra ist das homomorphe Bild isomorph zu ihrer Faktoralgebra nach der Kongruenzrelation  .

Beispiele für heterogene Algebren

Bearbeiten

Vektorräume

Bearbeiten

Ein Vektorraum   über einem Körper   ist eine heterogene Algebra mit den zwei Grundmengen   und  . Für die zweistelligen Operationen gilt Folgendes:

  •   hat Typ  .
  •   hat Typ  .
  •   hat Typ  .
  •   hat Typ  .

In quantorenfreier Notation der Axiome (ohne Existenzquantor) kommen noch dazu als einstellige Operationen die Bildung des additiven Inversen (Negativen) in   und des additiven und multiplikativen Inversen in  , sowie als Konstanten (nullstellige Operationen) der Nullvektor   in   und Null- und Einselement   in  :

  •   hat Typ  .
  •   hat Typ  .
  •   hat Typ   (als partielle Operation).
  •   hat Typ   (als Konstante  , siehe leeres Produkt).
  •   und   haben beide Typ  .

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.

Ein Modul   über einem kommutativen Ring   mit Einselement   ist eine heterogene Algebra mit den zwei Grundmengen   und  . 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

Bearbeiten

Eine Peirce-Algebra ist eine abstrakte Relationsalgebra zusammen mit Links- und Rechtsverknüfungen mit Elementen weiterer Trägermengen. Ein Beispiel sind zweistellige Relationen   zwischen Elementen zweier Mengen   und   (Vor- und Nachbereich) zusammen mit Vor- und Nachbeschränkung auf Teilmengen von   bzw.  .

Ein Köcher   in der Graphentheorie ist eine heterogene Algebra mit zwei Grundmengen   (Punkten oder Knoten genannt) und   (Pfeile oder gerichtete Kanten genannt). Die einstelligen Operationen   und   sind beide vom Typ   und ordnen jedem Pfeil seinen Anfangs- und Endpunkt zu.

Kleine Kategorien

Bearbeiten

Eine kleine Kategorie   in der Kategorientheorie ist eine (partielle) heterogene Algebra mit zwei Grundmengen[2]   (Objekte genannt) und   (Morphismen oder Pfeile genannt). Die einstelligen Operationen   und   sind beide vom Typ   und ordnen jedem Morphismus (Pfeil) sein Quell- und Zielobjekt zu.   ist eine zweistellige partielle Verknüpfung vom Typ   und ordnet je zwei Morphismen   mit   die Verknüpfung   zu. Die Identitätsabbildung   ist eine einstellige Verknüpfung vom Typ  , die jedem Objekt   seinen Identitätsmorphismus   mit   zuordnet. Die ersten vier Komponenten einer kleinen Kategorie   definieren einen Köcher  .

Endliche Automaten

Bearbeiten

Ein endlicher Automat   in der Automatentheorie ist eine heterogene Algebra[3] mit den zwei Grundmengen   (dem Eingabealphabet) und   (der Menge der Zustände). Für die Operationen gilt Folgendes:

  • Der Anfangszustand   hat Typ  .
  • Die Zustandsübergangsfunktion   hat Typ  .

Anmerkungen und Einzelnachweise

Bearbeiten
  1. Man kann die Indexmenge   verstehen als ein Alphabet von Bezeichnern (Sorten) der Grundmengen und die Indexmenge   als eine Menge von Funktionssymbolen (oder -bezeichnern).
  2. Die Beschränkung auf Grundmengen bedeutet, dass   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

Bearbeiten
  • 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.