View source for Term-generated Sigma-algebra

{{MSC|68P05}} 

{{TEX|done}}

The  [[Term-Algebra|ground term-algebra]] $T(\Sigma)$ is the most important  example of a [[Sigma-algebra (Computer Science)|$\Sigma$-algebra]]  belonging to a [[Signature (Computer Science)|signature $\Sigma$]]. This  is caused by several reasons. 
* The set $T(\Sigma)$ is [[Computable function|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 <i>term-generated</i>  $\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 <i>term-generated  $\Sigma$-subalgebra</i> $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$ {{Cite|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 {{Cite|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 {{Cite|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 <i>term-generated</i> or  <i>reachable</i>, 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|category]] {{Cite|W90}}.


Term-generated $\Sigma$-algebras are a very important subclass of $\Sigma$-algebras. According to the definition, they consist of elements representable as terms. This means, that 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 function|computable]] operations {{Cite|M89}}. This does not hold in the general. Consider for example the signature $\Sigma_F$ of algebraic [[Field|fields]]. The $\Sigma_F$-algebra of [[Rational number|rational numbers]] is term-generated, whereas the $\Sigma_F$-algebra of [[Real number|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 {{Cite|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 {{Cite|ST99}}).
* $A$ is generated by $\emptyset$.
Between two term-generated $\Sigma$-algebras, it exists at most one $\Sigma$-algebra-morphism {{Cite|W90}}.

===References===

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