Sigma-algebra (Computer Science)

2020 Mathematics Subject Classification: Primary: 68P05 [MSN][ZBL]

$\Sigma$-Algebras are the semantical counterpart to the signatures, which are pure syntactical objects. In order to give the function symbols $f\in F$ of a signature $\Sigma=(S,F)$ a meaning, a (total) $\Sigma$-algebra provides an object with the same structure as $\Sigma$ but consisting of concrete elements and concrete functions operating on these elements. The elements and functions of a $\Sigma$-algebra correspond to the sorts and function symbols of the signature $\Sigma$.

$\Sigma$-Algebras

Definition of $\Sigma$-Algebras

Formally, a $\Sigma$-algebra $A=((s^A)_{s\in S},(f^A)_{f\in F})$ consists of a family $(s^A)_{s\in S}$ of carrier sets $s^A$ corresponding to the sorts $s\in S$ and a family $(f^A)_{f\in F}$ of functions on these carrier sets corresponding to the function symbols $f\in F$. The compatibility requirement is that for a function symbol $f$ of type$(f)= s_1\times\cdots\times s_n \longrightarrow s$, the function $f^A$ must have the form $f^A\colon s_1^A\times\cdots\times s_n^A \longrightarrow s^A$.

Category of $\Sigma$-Algebras

Let $\Sigma=(S,F)$ be a signature and let $A,B$ be $\Sigma$-algebras. A $\Sigma$-algebra-morphism $m\colon A\longrightarrow B$ is a family $(m_s\colon s^A \longrightarrow s^B)_{s\in S}$ of mappings between the carrier sets of $A,B$ fulfilling the following compatibility properties

• $m_s(f^A)= f^B$ for $f\in F$ with ar$(f)=0$ and $\mathrm{type}(f)=\,\, \rightarrow s$
• $m_s(f^A(a_1,\ldots,a_n))=f^B(m_{s_1}(a_1),\ldots,m_{s_n}(a_n))$ for $f\in F$ with $\mathrm{type}(f)= s_1\times\cdots\times s_n \longrightarrow s$ and for $a_i\in s_i^A$.

A map $f\colon A\longrightarrow B$ is a $\Sigma$-algebra-morphism, iff $\forall t\in T(\Sigma)\colon f(t^A)=t^B$. The class of $\Sigma$-algebras together with the $\Sigma$-algebra-morphisms forms a category [W90].

The option to use partially defined functions complicates the situation considerably and leads to refined versions of the definition. Though this does not belong to the scope of this entry, a short remarks seems to be appropriate. For example it is possible under this generalization that $m_s(f^A(a_1,\ldots,a_n))$ is undefined though $f^A(a_1,\ldots,a_n)$ is defined. This can be caused by an undefinedness of a term $m_{s_j}(a_j)$ or of $f^B(m_{s_1}(a_1),\ldots,m_{s_n}(a_n))$ [M89].

$\Sigma$-Subalgebras

Definition of $\Sigma$-Subalgebras

One can easily imagine that typically many different $\Sigma$-algebras exist for the same signature $\Sigma$. This holds even in the case of algebraic specifications, which can restrict the set of admissable $\Sigma$-algebras by additional axioms. In effect, this means that an abstract signature $\Sigma$ can be 'implemented' by concrete $\Sigma$-algebras with different semantics. This leads to an interest in the relationships between these $\Sigma$-algebras. One method to discuss the relationships is to use $\Sigma$-algebra-morphisms, another is the notion of $\Sigma$-subalgebras.

$\Sigma$-Subalgebras of $\Sigma$-algebras are defined in the usual way. A $\Sigma$-Algebra $A$ is called a $\Sigma$-subalgebra of a $\Sigma$-Algebra $B$, if $\forall s\in S\colon s^A\subseteq s^B$ and if $f^A(a_1,\ldots,a_n) = f^B(a_1,\ldots,a_n)$ for $f\in F$ with $\mathrm{type}(f)= s_1\times\cdots\times s_n \longrightarrow s$ and for $a_i\in s_i^A$. The subalgebra-property is written as $A\subseteq B$. The relation $\subseteq$ is reflexive, antisymmetric, and transitive [EM85].

Another way to characterize the subalgebra-property is the existence of a $\Sigma$-algebra-morphism $m\colon A\longrightarrow B$, which is the identity on each carrier set of $A$, i.e. $m=(\mathrm{id}_{s^A})_{s\in S}$.

Properties of $\Sigma$-Subalgebras

(Carriers of) $\Sigma$-Subalgebras are closed under intersection. For a family $((s^{A_i})_{s\in S},(f^{A_i})_{f\in F})_{i\in I}$ of $\Sigma$-subalgebras $A_i$, their intersection $A=((s^{A})_{s\in S}, (f^{A})_{f\in F})$ is a $\Sigma$-subalgebra given by carrier sets $s^A:= \bigcap\limits_{i\in I} s^{A_i}$ for all $s\in S$ and functions $f^A:= f^{A_k}|_{s^A}$ for all $f\in F$ for an arbitrarily chosen $k\in I$. The declaration $f^A$ is well-defined, because according to the definition of a $\Sigma$-subalgebra the functions $f^{A_i}$ must behave in the same way on $s^A$.

The closedness of the set of $\Sigma$-subalgebras under intersections has an important consequence. For a $\Sigma$-algebra $A=((s^A)_{s\in S}, (f^A)_{f\in F})$ and an $S$-sorted set $X=(\bar s)_{s\in S}$ with $\bar s\subseteq s^A$ for all $s\in S$, it assures the existence of a smallest $\Sigma$-subalgebra $A'\subseteq A$ of $A$ containing $X$, i.e. $\bar s\subseteq s^{A'}$. The $\Sigma$-algebra $A'$ is called the $\Sigma$-subalgebra of $A$ generated by $X$ [ST99].

The subalgebra-property is compatible with $\Sigma$-algebra-morphisms. Let $A,B$ be $\Sigma$-algebras and let $m=(m_s)_{s\in S}\colon A \longrightarrow B$ be a $\Sigma$-algebra-morphism. For a $\Sigma$-subalgebra $A'\subseteq A$ of $A$, its image $m(A')\subseteq B$ is a $\Sigma$-subalgebra of $B$. The expression $B':=m(A')$ is defined in the obvious way, i.e. for $A'=((s^{A'})_{s\in S},(f^{A'})_{f\in F})$ the $\Sigma$-subalgebra $B'=((s^{B'})_{s\in S},(f^{B'})_{f\in F})$ is given by $s^{B'}:=\{m_s(a)|a\in s^{A'}\}$ for all $s\in S$ and $f_{B'}(m_{s_1}(a_1),\ldots,m_{s_n}(a_n)) = m_s(f_{A'}(a_1,\ldots,a_n))$ for all function symbols $f \colon s_1 \times \ldots\times s_n \longrightarrow s$ with $f\in F$ and $a_i \in s_i^{A'}$. The coimage of a $\Sigma$-subalgebra $B'\subseteq B$ of $B$ under $m$ is a $\Sigma$-subalgebra $m^{-1}(B')\subseteq A$ of $A$. The expression $m^{-1}(B')$ can be defined analogously to $m(A')$ and is omitted here [ST99].

Initial and Terminal $\Sigma$-Algebras

Initial $\Sigma$-Algebras

Many $\Sigma$-algebras have unpleasant properties like junk (i.e. elements, which are not term-generated). Thus, there is a natural interest in $\Sigma$-algebras behaving appropriately. An example for such desirable well-behaving $\Sigma$-algebra are initial $\Sigma$-algebras.

Let $K$ be a class of $\Sigma$-algebras. An element $A \in K$ is initial in $K$ if for every $B \in K$ there is a unique $\Sigma$-homomorphism $h\colon A \longrightarrow B$ [ST99]. The initial $\Sigma$-algebra does not always exist, but if it does, it is uniquely determined up to isomorphism [W90]. In the case of a sensible signature $\Sigma$, for a $\Sigma$-algebra $A$ it exists exactly one $\Sigma$-algebra-morphism $m^A\colon T(\Sigma)\longrightarrow A; t\mapsto t^A$ (see the entry 'evaluation'). Thus, in this case $T(\Sigma)$ is initial in $\mathrm{Alg}(\Sigma)$ [M89][W90].

• For $A\in K$ initial in a class $K$ of $\Sigma$-algebras it holds $$A\models t_1=t_2 \Longleftrightarrow \forall B\in K\colon (B\models t_1=t_2)$$ for ground terms $t_1,t_2\in T(\Sigma)$ [M89]. In an initial $\Sigma$-algebra, terms are identified if necessary. The initial $\Sigma$-algebra is the finest $\Sigma$-algebra [M89].
• If an element $A\in K$ of a class $K$ of $\Sigma$-algebras is term-generated and if it holds $$A\models t_1= t_2 \Longleftrightarrow \forall B\in K\colon (B\models t_1= t_2)$$ for all ground terms $t_1,t_2\in T(\Sigma)$ then $A$ is initial in $K$ [M89].

Terminal $\Sigma$-Algebras

Terminal $\Sigma$-algebras are the dual objects of initial $\Sigma$-algebras in the sense of category theory. This leads to the following definition based on the discussion of initial $\Sigma$-algebras given above. Let $K$ be a class of $\Sigma$-algebras. An element $A \in K$ is terminal in $K$ if for every $B \in K$ there is a unique $\Sigma$-homomorphism $h\colon B \longrightarrow A$ [ST99]. The terminal algebra does not always exist, but if it does, it is uniquely determined up to isomorphism [W90]. In the case of a sensible signature $\Sigma$, the terminal $\Sigma$-algebra $U\in \mathrm{Alg}(\Sigma)$ is the so-called unit algebra, where every carrier set consists of exactly one element [M89] [W90].

• For $A\in K$ terminal in a class $K$ of $\Sigma$-algebras it holds $$A\models t_1=t_2 \Longleftrightarrow \exists B\in K\colon (B\models t_1=t_2)$$ for ground terms $t_1,t_2\in T(\Sigma)$ [M89]. In a terminal $\Sigma$-algebra, terms are identified if possible. The terminal algebra is the coarsest algebra [M89].
• If $A\in K$ is an element of a class $K\subseteq \mathrm{Gen}(\Sigma)$ of term-generated $\Sigma$-algebras and if it holds $$A\models t_1= t_2 \Longleftrightarrow \exists B\in K\colon (B\models t_1= t_2)$$ for all ground terms $t_1,t_2\in T(\Sigma)$ then $A$ is terminal in $K$ [M89].

The very simple structure of the $\Sigma$-algebra $U$ terminal in $\mathrm{Alg}(\Sigma)$ makes it uninteresting both from a practical and theoretical point of view. As soon as the class $\mathrm{Alg}(\Sigma)$ of all $\Sigma$-algebras belonging to a signature $\Sigma$ is restricted to a subclass $K\subseteq \mathrm{Alg}(\Sigma)$, the situation changes, however. If $K$ still has a terminal $\Sigma$-algebra $T$, it has not necessarily a simple structure anymore. If $K$ is 'small' enough, $T$ and the initial $\Sigma$-algebra of $K$ may even be isomorphic. In such a case, $K$ is called monomorphic.

Such a subclass $K$ can be defined for example by a set $E$ of axioms characterizing the $\Sigma$-algebras $A\in K$ contained in $K$ as models of the theory given by $E$. This situation is typical for algebraic specifications.

Example of Initial and Terminal $\Sigma$-Algebras

Let $A,B$ be term-generated $\Sigma$-algebras and let $m\colon A\longrightarrow B$ be a $\Sigma$-algebra-morphism. In the class $K:=\{A,B\}$, the algebra $A$ is initial and $B$ terminal. The existence of a morphisms means, that elements distinguished in $A$ are eventually identified in $B$. As one can easily see in this example, initial and terminal $\Sigma$-algebras are typically not isomorphic.

Special Topics

Free $\Sigma$-Algebras

The idea of a free object (as a kind of generic structure) in the sense of category theory resp. universal algebra can be applied to $\Sigma$-algebras as well. For giving an explicit definition, let $K$ be a class of $\Sigma$-algebras. A $\Sigma$-algebra $A \in \mathrm{Alg}(\Sigma,X)$ with $A\in K$ is called free over $X$ in $K$, if it exists an assignement $u\colon X\longrightarrow A$ (serving as universal mapping) such that for every assignement $h\colon X\longrightarrow B$ to $B\in K$ it exists exactly one $\Sigma$-algebra-morphism $\bar h\colon A\longrightarrow B$ with $h=\bar h\circ u$ [EM85]. Due to the definition, two $\Sigma$-algebras $A_1, A_2\in K$ free over $X$ in $K$ are isomorphic $A_1\cong A_2$ to each other [EM85]. A $\Sigma$-algebra $I\in K$ is free over $\emptyset$ in $K$ iff $I$ is initial in $K$ [EM85].

$\Sigma$ Number Algebras

Let $\Sigma=(S,F)$ be a signature. A $\Sigma$-algebra is called a $\Sigma$ number algebra, if its carrier sets are recursive subsets of the natural numbers $\mathbb{N}$. It is called recursive if its functions are recursive [W90].

Reduct of $\Sigma$-Algebras

Every $\Sigma$-algebra $A$ is associated with a specific signature $\Sigma =(S,F)$. The so-called reduct offers the possibility, to adapt $A$ to a modification of $\Sigma$, if the modified signature $\Sigma'=(S',F')$ is related to $\Sigma$ via a signature morphism $m\colon \Sigma' \longrightarrow \Sigma$. Formally, the $m$-reduct $A':=A|_m$ of $A$ is a $\Sigma'$-algebra defined as follows [W90]: $A'$ has carrier sets $s^{A'} :=m(s)^A$ for each $s\in S'$ and operations $f^{A'}:=m(f)^A$ for each $f\in F'$. Similarly, for a $\Sigma$-algebra-morphism $h\colon A \longrightarrow B$ the $m$-reduct $h':=h|_m$ of $h$ is a $\Sigma'$-algebra-morphism $h'\colon A|_m \longrightarrow B|_m$ defined as $(h|_m)_s := h|_{m(s)}$ for each $s\in S'$ [W90]. Together, the mappings $A\rightarrow A|_m$ and $h\rightarrow h|_m$ form a functor $\cdot |_m\colon \mathrm{Alg}(\Sigma)\longrightarrow \mathrm{Alg}(\Sigma')$ [W90]. If $\Sigma'$ is a subsignature of $\Sigma$, then the $i$-reduct $A':=A|_i$ of $A$ (with $i \colon \Sigma' \longrightarrow \Sigma$ as canonical inclusion) is also written as $A|_\Sigma$. In this case, $A'$ is just $A$ with some carrier sets and/or functions removed [ST99].

References

[EM85]	H. Ehrig, B. Mahr: "Fundamentals of Algebraic Specifications", Volume 1, Springer 1985
[EM90]	H. Ehrig, B. Mahr: "Fundamentals of Algebraic Specifications", Volume 2, Springer 1990
[M89]	B. Möller: "Algorithmische Sprachen und Methodik des Programmierens I", lecture notes, Technical University Munich 1989
[ST99]	D. Sannella, A. Tarlecki, "Algebraic Preliminaries ", in Egidio Astesiano, Hans-Joerg Kreowski, Bernd Krieg-Brueckner, "Algebraic Foundations of System Specification", Springer 1999
[W90]	M. Wirsing: "Algebraic Specification", in J. van Leeuwen: "Handbook of Theoretical Computer Science", Elsevier 1990