www.wikidata.de-de.nina.az
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 Wahrend 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 Inhaltsverzeichnis 1 Definition 1 1 Bemerkungen 2 Verallgemeinerungen von aus universellen Algebren bekannten Begriffen 2 1 Unteralgebren 2 2 Homomorphismen 2 3 Homomorphiesatz 3 Beispiele fur heterogene Algebren 3 1 Vektorraume 3 2 Moduln 3 3 Peirce Algebren 3 4 Kocher 3 5 Kleine Kategorien 3 6 Endliche Automaten 4 Anmerkungen und Einzelnachweise 5 LiteraturDefinition BearbeitenEine heterogene Algebra engl heterogeneous algebra besteht aus einem System einer Familie von nichtleeren Grundmengen A A j j J displaystyle A A j j in J nbsp und einem System einer Familie von Operationen W w i i I displaystyle Omega omega i i in I nbsp Die Operationen w i displaystyle omega i nbsp sind Abbildungen von einem moglicherweise leeren kartesischen Produkt der Grundmengen in eine der Grundmengen w i A j 1 A j n A j n A k displaystyle omega i colon A j 1 times dotsb times A j nu times dotsb times A j n longrightarrow A k nbsp Man beachte dass k n displaystyle k n nbsp und alle j n displaystyle j nu nbsp spezifisch fur die jeweilige Operation sind Das zu jeder Operation w i displaystyle omega i nbsp gehorende n 1 displaystyle n 1 nbsp Tupel j 1 j n j n k J n 1 displaystyle j 1 dotsc j nu dotsc j n k in J n 1 nbsp bezeichnet man als den Typ dieser Operation Eine Operation w i displaystyle omega i nbsp vom Typ k displaystyle k nbsp entspricht einer Konstanten aus der Grundmenge A k displaystyle A k nbsp Man kann die heterogene Algebra wie folgt angeben A A W A j j J w i i I displaystyle boldsymbol A A Omega bigl A j j in J omega i i in I bigr nbsp In gegebenem Zusammenhang ist dafur auch gleichwertig die Schreibweise A A j j J W displaystyle boldsymbol A A j mid j in J Omega nbsp gebrauchlich Die Familie der Typen der einzelnen Operationen w i displaystyle omega i nbsp mit Indexmenge I displaystyle I nbsp nennt man die vielsortige Signatur manchmal auch ebenfalls Typ s displaystyle sigma nbsp der heterogenen Algebra 1 Haben zwei Algebren die gleiche Signatur so sind ihre Operationen bijektiv zuordenbar Falls es nur eine Grundmenge gibt wenn also I displaystyle I nbsp eine Einermenge ist dann liegt eine gewohnliche universelle Algebra vor Bemerkungen Bearbeiten Manchmal erweist es sich auch als zweckmassig leere Mengen A j displaystyle A j emptyset nbsp als Tragermengen zuzulassen etwa damit sichergestellt ist dass die Menge aller Unteralgebren siehe unten einer heterogenen Algebra einen algebraischen Verband bildet Ersetzt man in der obigen Definition den Begriff Verknupfung durch partielle Verknupfung dann spricht man von einer partiellen heterogenen Algebra Vernupfungswerte mussen hier nicht fur alle Parameter n displaystyle n nbsp Tupel Kombinationen definiert sein Verallgemeinerungen von aus universellen Algebren bekannten Begriffen BearbeitenDa die heterogene Algebra eine Verallgemeinerung der universellen Algebra ist ist es von Interesse wie sich die bekannten Begriffe und Satze ubertragen lassen Unteralgebren Bearbeiten Ein Mengensystem U U j j J displaystyle U U j j in J nbsp bei dem fur jeden Index j displaystyle j nbsp die Teilmengenrelation U j A j displaystyle U j subseteq A j nbsp gilt ist genau dann Unteralgebra der heterogenen Algebra A A j j J W A j j J W displaystyle boldsymbol A A j mid j in J Omega bigl A j j in J Omega bigr nbsp wenn alle Operationen aus W displaystyle Omega nbsp abgeschlossen sind insbesondere auch die nullstelligen Operationen wenn also gilt w i u 1 u n U k displaystyle omega i u 1 dots u n in U k nbsp fur alle w i displaystyle omega i nbsp mit Typ j 1 j n k displaystyle j 1 dotsc j n k nbsp und fur alle u 1 U j 1 u n U j n displaystyle u 1 in U j 1 dotsc u n in U j n nbsp Fur nullstellige Operationen w i displaystyle omega i nbsp mit Typ 0 displaystyle 0 nbsp also n 0 displaystyle n 0 nbsp d h Konstanten bedeutet das dass diese alle in U displaystyle U nbsp liegen mussen w i U displaystyle omega i in U nbsp Wie auch bei universellen Algebren gilt Der mengentheoretische Durchschnitt von Unteralgebren ist stets eine Unteralgebra sofern er nicht leer ist Dabei ist der Durchschnitt fur jedes j J displaystyle j in J nbsp getrennt durchzufuhren und keiner der Durchschnitte darf leer sein Homomorphismen Bearbeiten Seien A A j j J W displaystyle boldsymbol A A j mid j in J Omega nbsp und B B j j J W displaystyle boldsymbol B B j mid j in J Omega nbsp heterogene Algebren derselben Signatur d h fur jedes i displaystyle i nbsp seien w i displaystyle omega i nbsp und w i displaystyle omega i nbsp vom gleichen Typ etwa j 1 j n k displaystyle j 1 dotsc j n k nbsp Weiter sei gegeben ein System eine Familie von Abbildungen f j j J displaystyle f j j in J nbsp mit f j A j B j displaystyle f j colon A j to B j nbsp fur jedes j displaystyle j nbsp Seien die Funktionen f j displaystyle f j nbsp nun in folgendem Sinne mit den Operationen w i displaystyle omega i nbsp vertauschbar Fur alle w i w i displaystyle omega i omega i nbsp mit gemeinsamem Typ j 1 j n k displaystyle j 1 dotsc j n k nbsp und fur alle a 1 a n A j 1 A j n displaystyle a 1 dotsc a n in A j 1 times dotsb times A j n nbsp gilt f k w i a 1 a n w i f j 1 a 1 f j n a n displaystyle f k omega i a 1 dotsc a n omega i f j 1 a 1 dotsc f j n a n nbsp dd Speziell im Fall von Konstanten d h fur die w i displaystyle omega i nbsp mit Typ k displaystyle k nbsp muss also gelten f k w i w i displaystyle f k omega i omega i nbsp mit w i A k displaystyle omega i in A k nbsp und w i B k displaystyle omega i in B k nbsp Dann spricht man von einem Homomorphismus von A displaystyle boldsymbol A nbsp in B displaystyle boldsymbol B nbsp Sind zusatzlich alle Funktionen f j displaystyle f j nbsp bijektiv so spricht man von einem Isomorphismus Homomorphiesatz Bearbeiten Fur jeden Homomorphismus f displaystyle f nbsp auf einer heterogenen Algebra ist das homomorphe Bild isomorph zu ihrer Faktoralgebra nach der Kongruenzrelation 8 f displaystyle theta f nbsp Siehe auch HomomorphiesatzBeispiele fur heterogene Algebren BearbeitenVektorraume Bearbeiten Ein Vektorraum V displaystyle V oplus odot nbsp uber einem Korper K displaystyle K cdot nbsp ist eine heterogene Algebra mit den zwei Grundmengen A 1 V displaystyle A 1 V nbsp und A 2 K displaystyle A 2 K nbsp Fur die zweistelligen Operationen gilt Folgendes A 1 A 1 A 1 displaystyle oplus colon A 1 times A 1 to A 1 nbsp hat Typ 1 1 1 displaystyle 1 1 1 nbsp A 2 A 1 A 1 displaystyle odot colon A 2 times A 1 to A 1 nbsp hat Typ 2 1 1 displaystyle 2 1 1 nbsp A 2 A 2 A 2 displaystyle colon A 2 times A 2 to A 2 nbsp hat Typ 2 2 2 displaystyle 2 2 2 nbsp A 2 A 2 A 2 displaystyle cdot colon A 2 times A 2 to A 2 nbsp hat Typ 2 2 2 displaystyle 2 2 2 nbsp In quantorenfreier Notation der Axiome ohne Existenzquantor kommen noch dazu als einstellige Operationen die Bildung des additiven Inversen Negativen in V displaystyle V oplus nbsp und des additiven und multiplikativen Inversen in K displaystyle K cdot nbsp sowie als Konstanten nullstellige Operationen der Nullvektor 0 V displaystyle 0 V nbsp in V displaystyle V oplus nbsp und Null und Einselement 0 1 displaystyle 0 1 nbsp in K displaystyle K cdot nbsp A 1 A 1 displaystyle ominus colon A 1 to A 1 nbsp hat Typ 1 1 displaystyle 1 1 nbsp A 2 A 2 displaystyle colon A 2 to A 2 nbsp hat Typ 2 2 displaystyle 2 2 nbsp inv 1 A 2 A 2 displaystyle operatorname inv 1 colon A 2 not to A 2 nbsp hat Typ 2 2 displaystyle 2 2 nbsp als partielle Operation 0 V A 1 displaystyle 0 V in A 1 nbsp hat Typ 1 displaystyle 1 nbsp als Konstante A 1 0 A 1 displaystyle A 1 0 emptyset to A 1 nbsp siehe leeres Produkt 0 A 2 displaystyle 0 in A 2 nbsp und 1 A 2 displaystyle 1 in A 2 nbsp haben beide Typ 2 displaystyle 2 nbsp Streng genommen ist der Vektorraum also eine partielle heterogene Struktur Verallgemeinerungen sind Links und Rechtsvektorraume uber Schiefkorpern Wegfall der multiplikativen Kommutativitat der Skalare Spezielle Vektorraume sind die Algebren uber einem Korper K Algebren veraltet auch lineare Algebren und Lie Algebren Moduln Bearbeiten Ein Modul M displaystyle M oplus odot nbsp uber einem kommutativen Ring R displaystyle R cdot nbsp mit Einselement 1 displaystyle 1 nbsp ist eine heterogene Algebra mit den zwei Grundmengen A 1 M displaystyle A 1 M nbsp und A 2 R displaystyle A 2 R nbsp Moduln sind verallgemeinerte Vektorraume fur die Operationen gelten analoge Regeln wie oben Weitere Verallgemeinerungen bestehen im Wegfall der multiplikativen Kommutativitat 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 Rechtsverknufungen mit Elementen weiterer Tragermengen Ein Beispiel sind zweistellige Relationen R A B displaystyle R subseteq A times B nbsp zwischen Elementen zweier Mengen A displaystyle A nbsp und B displaystyle B nbsp Vor und Nachbereich zusammen mit Vor und Nachbeschrankung auf Teilmengen von A displaystyle A nbsp bzw B displaystyle B nbsp Kocher Bearbeiten Ein Kocher G V E s t displaystyle Gamma V E operatorname s operatorname t nbsp in der Graphentheorie ist eine heterogene Algebra mit zwei Grundmengen A 1 V displaystyle A 1 V nbsp Punkten oder Knoten genannt und A 2 E displaystyle A 2 E nbsp Pfeile oder gerichtete Kanten genannt Die einstelligen Operationen s displaystyle operatorname s nbsp und t displaystyle operatorname t nbsp sind beide vom Typ 2 1 displaystyle 2 1 nbsp und ordnen jedem Pfeil seinen Anfangs und Endpunkt zu Kleine Kategorien Bearbeiten Eine kleine Kategorie C W M dom cod id displaystyle mathcal C mathit Omega M operatorname dom operatorname cod circ operatorname id nbsp in der Kategorientheorie ist eine partielle heterogene Algebra mit zwei Grundmengen 2 A 1 W Ob C displaystyle A 1 mathit Omega operatorname Ob mathcal C nbsp Objekte genannt und A 2 M Ar C displaystyle A 2 M operatorname Ar mathcal C nbsp Morphismen oder Pfeile genannt Die einstelligen Operationen dom displaystyle operatorname dom nbsp und cod displaystyle operatorname cod nbsp sind beide vom Typ 2 1 displaystyle 2 1 nbsp und ordnen jedem Morphismus Pfeil sein Quell und Zielobjekt zu displaystyle circ nbsp ist eine zweistellige partielle Verknupfung vom Typ 2 2 1 displaystyle 2 2 1 nbsp und ordnet je zwei Morphismen f g displaystyle f g nbsp mit cod f dom g displaystyle operatorname cod f operatorname dom g nbsp die Verknupfung g f displaystyle g circ f nbsp zu Die Identitatsabbildung id displaystyle operatorname id nbsp ist eine einstellige Verknupfung vom Typ 1 2 displaystyle 1 2 nbsp die jedem Objekt X displaystyle X nbsp seinen Identitatsmorphismus id X displaystyle operatorname id X nbsp mit dom id X cod id X X displaystyle operatorname dom operatorname id X operatorname cod operatorname id X X nbsp zuordnet Die ersten vier Komponenten einer kleinen Kategorie C W M dom cod id displaystyle mathcal C mathit Omega M operatorname dom operatorname cod circ operatorname id nbsp definieren einen Kocher G W M dom cod displaystyle Gamma mathit Omega M operatorname dom operatorname cod nbsp Endliche Automaten Bearbeiten Ein endlicher Automat S S s 0 d F displaystyle Sigma S s 0 delta F nbsp in der Automatentheorie ist eine heterogene Algebra 3 mit den zwei Grundmengen A 1 S displaystyle A 1 Sigma nbsp dem Eingabealphabet und A 2 S displaystyle A 2 S nbsp der Menge der Zustande Fur die Operationen gilt Folgendes Der Anfangszustand s 0 A 2 displaystyle s 0 colon to A 2 nbsp hat Typ 2 displaystyle 2 nbsp Die Zustandsubergangsfunktion d A 2 A 1 A 2 displaystyle delta colon A 2 times A 1 to A 2 nbsp hat Typ 2 1 2 displaystyle 2 1 2 nbsp Anmerkungen und Einzelnachweise Bearbeiten Man kann die Indexmenge I displaystyle I nbsp verstehen als ein Alphabet von Bezeichnern Sorten der Grundmengen und die Indexmenge J displaystyle J nbsp als eine Menge von Funktionssymbolen oder bezeichnern Die Beschrankung auf Grundmengen bedeutet dass C displaystyle mathcal C nbsp eine kleine Kategorie ist In der Kategorientheorie bilden allerdings die Objekte und Morphismen der betrachteten Kategorien gewohnlich eigentliche Klassen statt Mengen Opolka 2010 S 141 Literatur BearbeitenHans Kaiser Rainer Mlitz Gisela Zeilinger Algebra fur Informatiker 2 Auflage Springer Verlag Wien 1985 ISBN 978 3 7091 8820 0 doi 10 1007 978 3 7091 8820 0 Miroslav Novotny 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 fur die Informatik Bei TU Braunschweig de Institut fur Analysis und Algebra PDF 2010 kein Zugriff ohne Berechtigung Abgerufen von https de wikipedia org w index php title Heterogene Algebra amp oldid 198346007