Heterogeneous algebra

Heterogeneous algebras are algebraic structures investigated in the mathematical sub-area of universal algebra and represent in a certain sense a generalization of universal algebras (to be distinguished from the discipline). While universal algebras are based on a single set as the basic set, the basic set is a heterogeneous algebra a set system.

They are used in the algebraic specification , a form of specification of a data type.

definition

A heterogeneous algebra consists of a system (a family ) of non-empty basic sets and a system (a family) of operations . ${\displaystyle A=(A_{j})_{j\in J}}$ ${\displaystyle \Omega =(\omega _{i})_{i\in I}}$

The operations are mappings of a (possibly empty) Cartesian product of the basic sets into one of the basic sets ${\displaystyle \omega _{i}}$

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

Note that and all are specific to the particular operation. The operation at any part of tuples is called the type of the operation. An operation of the type corresponds to a constant (from the basic set ). ${\displaystyle k,n}$ ${\displaystyle j_{\nu }}$ ${\displaystyle \omega _{i}}$ ${\displaystyle (n+1)}$ ${\displaystyle (j_{1},\dotsc ,j_{\nu },\dotsc ,j_{n};k)\in J^{n+1}}$ ${\displaystyle \omega _{i}}$ ${\displaystyle (;k)}$ ${\displaystyle A_{k}}$

The heterogeneous algebra can be specified as follows:

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

In the given context, the spelling is also equivalent

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

common.

The family of types of the individual operations with an index set is called the (multi-faceted) signature (sometimes also type ) of heterogeneous algebra. If two algebras have the same signature, their operations can be assigned bijectively. ${\displaystyle \omega _{i}}$ ${\displaystyle I}$ ${\displaystyle \sigma }$

If there is only one basic set ( i.e. if there is a unit), then we have an ordinary ( universal ) algebra . ${\displaystyle I}$

Remarks

1. Sometimes it is also useful to allow empty sets as carrier sets , for example to ensure that the set of all sub-algebras (see below) of a heterogeneous algebra forms an algebraic lattice . ${\displaystyle A_{j}=\emptyset }$
2. If the term linkage is replaced by partial linkage in the above definition , then one speaks of a partial heterogeneous algebra. Link values ​​do not have to be defined here for all parameters ( tuple combinations). ${\displaystyle n}$

Generalizations of terms known from universal algebras

Since heterogeneous algebra is a generalization of universal algebra, it is of interest how the known concepts and sentences can be translated.

Sub-algebras

A set system in which the subset relation applies to every index is a subalgebra of heterogeneous algebra if and only if all operations from are closed (especially also the zero-digit operations), so if: ${\displaystyle U=(U_{j})_{j\in {J}}}$ ${\displaystyle j}$ ${\displaystyle U_{j}\subseteq A_{j}}$ ${\displaystyle {\boldsymbol {A}}=(A_{j}\mid j\in J,\Omega )={\bigl (}(A_{j})_{j\in J},\Omega {\bigr )}}$ ${\displaystyle \Omega }$

${\displaystyle \omega _{i}(u_{1},\dots ,u_{n})\in U_{k}}$for everyone with type and for everyone ${\displaystyle \omega _{i}}$ ${\displaystyle (j_{1},\dotsc ,j_{n};k)}$ ${\displaystyle {u_{1}}\in U_{j_{1}},\dotsc ,u_{n}\in U_{j_{n}}}$

Null digit operations (with type , that is ), d. H. Constants, this means that they must all be in: ${\displaystyle \omega _{i}}$ ${\displaystyle (;0)}$ ${\displaystyle n=0}$ ${\displaystyle U}$

${\displaystyle \omega _{i}\in U}$

As with universal algebras, the following applies: The set theoretic average of subalgebras is always a subalgebra (provided it is not empty). The average must be carried out separately for each and none of the averages may be empty. ${\displaystyle j\in J}$

Homomorphisms

Let and heterogeneous algebras have the same signature, i.e. h., each are and of the same type, for example . ${\displaystyle {\boldsymbol {A}}=(A_{j}\mid j\in J,\Omega )}$ ${\displaystyle {\boldsymbol {B}}=(B_{j}\mid j\in J,\Omega ')}$ ${\displaystyle i}$ ${\displaystyle \omega _{i}}$ ${\displaystyle \omega '_{i}}$ ${\displaystyle (j_{1},\dotsc ,j_{n};k)}$

Let there be a system (family) of mappings with for each . ${\displaystyle (f_{j})_{j\in J}}$ ${\displaystyle f_{j}\colon A_{j}\to B_{j}}$ ${\displaystyle j}$

Let the functions be interchangeable with the operations in the following sense : ${\displaystyle f_{j}}$ ${\displaystyle \omega _{i}}$

The following applies to everyone with a common type and for everyone : ${\displaystyle \omega _{i},\omega '_{i}}$ ${\displaystyle (j_{1},\dotsc ,j_{n};k)}$ ${\displaystyle (a_{1},\dotsc ,a_{n})\in A_{j_{1}}\times \dotsb \times A_{j_{n}}}$

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

Especially in the case of constants, i. H. for those with type , the following must apply: with and . ${\displaystyle \omega _{i}}$ ${\displaystyle (;k)}$ ${\displaystyle f_{k}(\omega _{i})=\omega '_{i}}$ ${\displaystyle \omega _{i}\in A_{k}}$ ${\displaystyle \omega '_{i}\in B_{k}}$

Then one speaks of a homomorphism of in . If all functions are also bijective, one speaks of an isomorphism . ${\displaystyle {\boldsymbol {A}}}$ ${\displaystyle {\boldsymbol {B}}}$
${\displaystyle f_{j}}$

Homomorphism theorem

For every homomorphism on a heterogeneous algebra, the homomorphic image is isomorphic to its factor algebra according to the congruence relation . ${\displaystyle f}$ ${\displaystyle \theta _{f}}$

See also : Homomorphism Theorem

Examples of heterogeneous algebras

Vector spaces

A vector space over a field is a heterogeneous algebra with the two basic sets and . The following applies to the two-digit operations: ${\displaystyle (V,\oplus ,\odot )}$ ${\displaystyle (K,+,\cdot )}$ ${\displaystyle A_{1}=V}$ ${\displaystyle A_{2}=K}$

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

In the quantifier-free notation of the axioms (without existential quantifier ), the formation of the additive inverse (negative) in and the additive and multiplicative inverse in , as well as constants (zero-digit operations) the zero vector in and zero and one element in : ${\displaystyle (V,\oplus )}$ ${\displaystyle (K,+,\cdot )}$ ${\displaystyle 0_{V}}$ ${\displaystyle (V,\oplus )}$ ${\displaystyle 0,1}$ ${\displaystyle (K,+,\cdot )}$

• ${\displaystyle \ominus \colon A_{1}\to A_{1}}$has type . ${\displaystyle (1;1)}$
• ${\displaystyle -\colon A_{2}\to A_{2}}$has type . ${\displaystyle (2;2)}$
• ${\displaystyle \operatorname {inv} ={}^{-1}\colon A_{2}\not \to A_{2}}$has type (as a partial operation). ${\displaystyle (2;2)}$
• ${\displaystyle 0_{V}\in A_{1}}$has type (as a constant , see empty product ). ${\displaystyle (;1)}$ ${\displaystyle {A_{1}}^{0}=\{\emptyset \}\to A_{1}}$
• ${\displaystyle 0\in A_{2}}$and both have type . ${\displaystyle 1\in A_{2}}$ ${\displaystyle (;2)}$

Strictly speaking, the vector space is therefore a partially heterogeneous structure.
Generalizations are left and right vector spaces over skew fields (omission of the multiplicative commutativity of the scalars). Special vector spaces are the algebras over a field (K-algebras, also obsolete: linear algebras) and Lie algebras .

Modules

A module over a commutative ring with one element is a heterogeneous algebra with the two basic sets and . Modules are generalized vector spaces, for the operations analogous rules apply as above. Further generalizations exist in the absence of the multiplicative commutativity of the scalars (in which case a distinction must then be made between left and right modules) or of the one element. ${\displaystyle (M,\oplus ,\odot )}$ ${\displaystyle (R,+,\cdot )}$ ${\displaystyle 1}$ ${\displaystyle A_{1}=M}$ ${\displaystyle A_{2}=R}$

Peirce algebras

A Peirce algebra is an abstract relational algebra together with left and right links with elements of other carrier sets. An example are two-digit relations between elements of two sets and (pre- and post-area) together with pre- and post-restriction to subsets of or . ${\displaystyle R\subseteq A\times B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

quiver

A quiver in graph theory is a heterogeneous algebra with two basic sets (called points or nodes) and (called arrows or directed edges). The one-digit operations and are both of the type and assign each arrow its start and end point. ${\displaystyle \Gamma =(V,E,\operatorname {s} ,\operatorname {t} )}$ ${\displaystyle A_{1}=V}$ ${\displaystyle A_{2}=E}$ ${\displaystyle \operatorname {s} }$ ${\displaystyle \operatorname {t} }$ ${\displaystyle (2;1)}$

Small categories

A small category in category theory is a (partial) heterogeneous algebra with two basic sets (called objects) and (called morphisms or arrows). The one-digit operations and are both of the type and assign each morphism (arrow) its source and target object. is a two-digit partial link of the type and assigns two morphisms to the link . The identity mapping is a unary operation type associated with each object its Identitätsmorphismus with associates. The first four components of a small category define a quiver . ${\displaystyle {\mathcal {C}}=({\mathit {\Omega }},M,\operatorname {dom} ,\operatorname {cod} ,\circ ,\operatorname {id} )}$ ${\displaystyle A_{1}={\mathit {\Omega }}=\operatorname {Ob} ({\mathcal {C}})}$ ${\displaystyle A_{2}=M=\operatorname {Ar} ({\mathcal {C}})}$ ${\displaystyle \operatorname {dom} }$ ${\displaystyle \operatorname {cod} }$ ${\displaystyle (2;1)}$ ${\displaystyle \circ }$ ${\displaystyle (2,2;1)}$ ${\displaystyle f,g}$ ${\displaystyle \operatorname {cod} (f)=\operatorname {dom} (g)}$ ${\displaystyle g\circ f}$ ${\displaystyle \operatorname {id} }$ ${\displaystyle (1;2)}$ ${\displaystyle X}$ ${\displaystyle \operatorname {id} _{X}}$ ${\displaystyle \operatorname {dom} (\operatorname {id} _{X})=\operatorname {cod} (\operatorname {id} _{X})=X}$ ${\displaystyle {\mathcal {C}}=({\mathit {\Omega }},M,\operatorname {dom} ,\operatorname {cod} ,\circ ,\operatorname {id} )}$ ${\displaystyle \Gamma =({\mathit {\Omega }},M,\operatorname {dom} ,\operatorname {cod} )}$

Finite automatons

A finite automaton in automaton theory is a heterogeneous algebra with the two basic sets (the input alphabet) and (the set of states). The following applies to the operations: ${\displaystyle (\Sigma ,S,s_{0},\delta ,F)}$ ${\displaystyle A_{1}=\Sigma }$ ${\displaystyle A_{2}=S}$

• The initial state has type . ${\displaystyle s_{0}\colon \to A_{2}}$ ${\displaystyle (;2)}$
• The state transition function has type . ${\displaystyle \delta \colon A_{2}\times A_{1}\to A_{2}}$ ${\displaystyle (2,1;2)}$

Notes and individual references

1. ↑ The index set can be understood as an alphabet of identifiers (types) of the basic sets and the index set as a set of function symbols (or identifiers). ${\displaystyle I}$ ${\displaystyle J}$
2. ↑ The restriction on basic quantities means that there is a small category. In category theory, however, the objects and morphisms of the categories under consideration usually form actual classes instead of sets. ${\displaystyle {\mathcal {C}}}$
3. ↑ Opolka 2010, p. 141.

literature

• Hans Kaiser, Rainer Mlitz, Gisela Zeilinger: Algebra for computer scientists . 2nd Edition. Springer-Verlag, Vienna 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, pp. 415-428.
• G. Birkhoff, JD Lipson: Heterogeneous algebras. In: Journal of Combinatorial Theory. 8, 1970, pp. 115-133.
• JA Goguen, JW Thatcher, EG Wagner, JB Wright: Initial algebra semantics and continuous algebras. In: Journal of the Association for Computing Machinery. 24, 1977, pp. 68-95.
• PJ Higgins: Algebras with a schema of operators. In: Mathematical News. 27, 1963, pp. 115-132.
• Hans Opolka: Algebra for Computer Science. At: TU-Braunschweig.de. Institute for Analysis and Algebra. PDF, 2010, no access without authorization.