Heterogene Algebra

Heterogene Algebren sind algebraische Strukturen und stellen im gewissen Sinn eine Verallgemeinerung von universellen Algebren 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 von Grundmengen $A_i, i \in I$ und einem System Ω von Operationen ω_i.

Die Operationen ω_i sind entweder Abbildungen von einem kartesischen Produkt der Grundmengen in eine der Grundmengen

$\omega_i: A_{j_1} \times \dots \times A_{j_n} \longrightarrow A_k$

oder zeichnen eine spezielles Element (z. B.: ein bezüglich einer Operation neutrales Element) in einer der Mengen aus.

Das (n+1)-Tupel $(j_1, \dots, j_n ; k)\!$ bezeichnet man als den Typ der Operation ω

Das System von Indexmenge I und den Typen der einzelnen Operationen nennt man Signatur der Algebra. Haben zwei Algebren nun gleiche Signatur so sind ihre Operationen bijektiv zuordenbar.

Man kann die heterogene Algebra wie folgt anschreiben: $(A_i | i \in I , \Omega)\!$

Verallgemeinerungen von über 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_i \subseteq A_i$ ist genau dann Unteralgebra der heterogenen Algebra $(A_i | i \in I , \Omega)\!$, wenn alle Operationen aus Ω abgeschlossen sind. (Insbesondere die Nullstelligen Operationen) also wenn gilt:

$\omega(u_1, \dots , u_n) \in U_j,\quad \forall\ u_1 \in u_{i_1}, \dots , u_n \in u_{i_n},\ \forall\ \omega\ mit\ Typ\ (i_1, \dots , i_n ;j)$

Wie auch bei universelle Algebren gilt: Der mengentheoretische Durchschnitt von Unteralgebren ist stets eine Unteralgebra (sofern er nicht leer ist). Wobei hier der Durchschnitt in jede Menge A_i getrennt durchgeführt wird und keiner der Durchschnitte leer sein darf.

siehe auch: Unteralgebra

Homomorphismen

Seinen $(A_i | i \in I , \Omega)\!$ und $(B_i | i \in I , \Omega)\!$ heterogene Algebren derselben Signatur.

Des Weiteren sei $(f_i | i \in I) \!$ mit $f_i: A_i \rightarrow B_i$ ein System vom Abbildungen.

Sind die Funktionen $f_i \!$ nun im folgenden Sinne mit der Operationen $\omega{}_i \!$ vertauschbar:

$f_j(\omega (a_1 , \dots , a_n)) = \omega(f_{i_1}(a_1) , \dots , f_{i_n}(a_n)) \qquad \forall \ (a_1 , \dots , a_n) \in A_{i_1} \times \dots \times A_{i_n} \qquad \forall \ \omega \ mit \ Typ \ (i_1, ... ,i_n;j)$

und für $\omega \!$ mit Typ $(;j) \!$ gilt: $f_j(\omega_{A_j})=\omega_{B_j}\!$

so spricht man von einem Homomorphismus, sind zusätzlich alle Funktionen $f_i\!$ 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 θ_f.

siehe auch Homomorphiesatz

Literatur

• 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