# Term-generated Sigma-algebra

2010 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.

## Contents

### 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 |

**How to Cite This Entry:**

Term-generated Sigma-algebra.

*Encyclopedia of Mathematics.*URL: http://www.encyclopediaofmath.org/index.php?title=Term-generated_Sigma-algebra&oldid=29455