Term-generated Sigma-algebra

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

The ground term-algebra $T(\Sigma)$ is the most important example of a $\Sigma$-algebra belonging to a signature $\Sigma$. This is caused by several reasons.

• The set $T(\Sigma)$ is computational.
• It is possible to construct $T(\Sigma)$ canonically.

Additionally, $T(\Sigma)$ is --- according to the definition of a $\Sigma$-algebra --- in a certain sense an essential part of every $\Sigma$-algebra $A$. To be more precisely, the required interpretability of $A$ in the context of the signature $\Sigma$ leads immediately to the existence of a $\Sigma$-algebra-morphism $m\colon T(\Sigma) \longrightarrow A$. Thus, $A$ contains the image of $T(\Sigma)$ under $m$ as $\Sigma$-subalgebra. This subalgebra is called a term-generated $\Sigma$-algebra. The ground term algebra is an example of a term-generated $\Sigma$-algebra.

Definition of Term-generated $\Sigma$-Subalgebras

Let $\Sigma=(S,F)$ be a signature and let $A$ be a $\Sigma$-algebra. As usual, the interpretation of a function symbol $f\in F$ in the algebra $A$ may be designated as $f^A$. Then the term-generated $\Sigma$-subalgebra $A^T\subseteq A$ of $A$ is inductively defined as follows

• $f^A\in A^T$ for all $f\in F$ with ar$(f)=0$
• $f^A(t_1^A,\ldots,t_n^A)\in A^T$ for all $f\in F$ with arity ar$(f)=n$ and with type$(f)= s_1\times\cdots\times s_n \longrightarrow s$ and for all terms $t_i\in T_{s_i}(\Sigma)$.

As it can be shown, $A^T$ is indeed a $\Sigma$-algebra and it exists an embedding mapping $i_A\colon A^T \longrightarrow A$ [M89].

Characterization of Term-generated $\Sigma$-Subalgebras

The term-generated $\Sigma$-subalgebra $A^T$ of $A$ can be characterized using the following approach given in [M89]:

• $G_0:=\{f^A\in A^T\mid f\in F, \mathrm{ar}(f)=0\}$
• $G_{i+1}:=G_i\cup \{f^A(a_1,\ldots,a_n)\in A^T\mid f\in F, \mathrm{ar}(f)=n, \mathrm{type}(f)= s_1\times\cdots\times s_n \longrightarrow s, a_i\in s^A\cap G_i\}$.

It holds $\bigcup_{i\in\mathbb{N}} G_i =A^T$. The proof is based on the fixpoint theorem.

Again according to [M89], it holds $A^T=\{ a\in A \mid \exists t\in T(\Sigma)\colon t^A=a\}$ as well. This is caused by the equality $f(t_1,\ldots,t_n)^A= f^A(t_1^A,\ldots,t_n^A)$ for a term $t\in T(\Sigma)$ of the form $t=f(t_1,\ldots,t_n)$.

Definition of Term-generated $\Sigma$-Algebras

A $\Sigma$-algebra $A$ is called term-generated or reachable, if $A=A^T$. In other words, for each element $a\in A$ of $A$ exists a term $t\in T(\Sigma)$ with $a=t^A$. The class of all term-generated $\Sigma$-algebras over a signature $\Sigma$ is designated as $\mathrm{Gen}(\Sigma)$. Together with the $\Sigma$-algebra-morphisms, $\mathrm{Gen}(\Sigma)$ is a category [W90].

Term-generated $\Sigma$-algebras are a very important subclass of $\Sigma$-algebras. According to the definition, they consist of elements representable as terms. The structure of the $\Sigma$-algebra determines, which (ground) terms $t_1,t_2\in T(\Sigma)$ are identified in the representation based on equations like $t_1^A=t_2^A$. All elements of term-generated $\Sigma$-algebras can be composed from elementary objects (constants and function symbols) and decomposed again. Consequently, the creation and manipulation of these elements are typically computable operations [M89]. This leads to the designation of term-generated $\Sigma$-algebras as computation structures.

Consider for example the signature $\Sigma_F$ of algebraic fields. The $\Sigma_F$-algebra of rational numbers is term-generated, whereas the $\Sigma_F$-algebra of real numbers is not.

Characterization of Term-generated $\Sigma$-Algebras

Let $A\in\mathrm{Alg}(\Sigma)$ be a $\Sigma$-algebra. Then the following statements are equivalent [W90]:

• $A$ is term-generated, i.e. $A\in\mathrm{Gen}(\Sigma)$
• It exists a surjective $\Sigma$-algebra-morphism $m\colon T(\Sigma) \longrightarrow A$.
• The (unique) morphism $h \colon T(\Sigma)\longrightarrow A$ is surjective ($h$ has to be understood as the extension of the interpreting mapping of the function symbols $f\in F$ in the $\Sigma$-algebra $A$ to terms $t\in T(\Sigma)$).
• $A$ has no proper $\Sigma$-subalgebra (It follows that every $\Sigma$-algebra has a unique term-generated $\Sigma$-subalgebra [ST99]).
• $A$ is generated by $\emptyset$.

Between two term-generated $\Sigma$-algebras, it exists at most one $\Sigma$-algebra-morphism [W90].

This characterization leads to some interesting properties. For example, if a class $K$ of $\Sigma$-algebras is closed under $\Sigma$-subalgebras (i.e. if $K$ contains all $\Sigma$-subalgebras $B\subseteq A$ of an $A\in K$) and if $K\neq\emptyset$, then a $\Sigma$-algebra $A\in K$ initial in $K$ is term-generated [EM85].

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