Namespaces
Variants
Actions

Difference between revisions of "Sigma-algebra (Computer Science)"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (Criterion added for a mapping being a morphism)
 
(3 intermediate revisions by the same user not shown)
Line 6: Line 6:
 
$\Sigma$-Algebras  are the [[Semantics|semantical]] counterpart to the [[Signature  (Computer Science)|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  are the [[Semantics|semantical]] counterpart to the [[Signature  (Computer Science)|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$.
  
===Definition of $\Sigma$-Algebras===
+
===$\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 <i>carrier sets</i> $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$.
 
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 <i>carrier sets</i> $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===
+
 
 +
====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
 
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)= 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$.
 
*  $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$.
The class of $\Sigma$-algebras together with the $\Sigma$-algebra-morphisms forms a [[Category|category]] {{Cite|W90}}.
+
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|category]] {{Cite|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))$  {{Cite|M89}}.
 
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))$  {{Cite|M89}}.
  
===Definition of $\Sigma$-Subalgebras===
+
===$\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 Specification|algebraic specifications]], which can restrict  the set of admissable $\Sigma$-algebras by additional [[Axiom|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.
 
One  can easily imagine that typically many different $\Sigma$-algebras  exist for the same signature $\Sigma$. This holds even in the case of  [[Algebraic Specification|algebraic specifications]], which can restrict  the set of admissable $\Sigma$-algebras by additional [[Axiom|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.
Line 27: Line 32:
 
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}$.
 
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===
+
====Properties of $\Sigma$-Subalgebras====
  
 
(Carriers of) $\Sigma$-Subalgebras are closed  under [[Intersection of sets|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$.
 
(Carriers of) $\Sigma$-Subalgebras are closed  under [[Intersection of sets|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$.
Line 35: Line 40:
 
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  {{Cite|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  {{Cite|ST99}}.
  
===Initial $\Sigma$-Algebras===
+
===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.
 
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 {\em initial} in $K$ if for every $B \in K$ there is a unique $\Sigma$-homomorphism $h\colon A \longrightarrow  B$ {{Cite|ST99}}.  The initial $\Sigma$-algebra does not always exist, but if it does, it is uniquely determined up to isomorphism {{Cite|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$. Thus, in this case $T(\Sigma)$ is initial in $\mathrm{Alg}(\Sigma)$ {{Cite|M89}}{{Cite|W90}}.
+
Let $K$ be a class of $\Sigma$-algebras. An element $A \in K$ is <i>initial</i> in $K$ if for every $B \in K$ there is a unique $\Sigma$-homomorphism $h\colon A \longrightarrow  B$ {{Cite|ST99}}.  The initial $\Sigma$-algebra does not always exist, but if it does, it is uniquely determined up to isomorphism {{Cite|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|evaluation]]'). Thus, in this case $T(\Sigma)$ is initial in $\mathrm{Alg}(\Sigma)$ {{Cite|M89}}{{Cite|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)$ {{Cite|M89}}.  In an initial $\Sigma$-algebra, terms are identified if necessary.  The initial $\Sigma$-algebra is the finest $\Sigma$-algebra {{Cite|M89}}.
 
* 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)$ {{Cite|M89}}.  In an initial $\Sigma$-algebra, terms are identified if necessary.  The initial $\Sigma$-algebra is the finest $\Sigma$-algebra {{Cite|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$ {{Cite|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$ {{Cite|M89}}.
  
===Terminal $\Sigma$-Algebras===
+
====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 {\em terminal} in $K$ if for every $B \in K$ there is a unique $\Sigma$-homomorphism $h\colon B \longrightarrow  A$ {{Cite|ST99}}.  The terminal algebra does not always exist, but if it does, it is uniquely determined up to isomorphism {{Cite|W90}}. In the case of a sensible signature $\Sigma$, the terminal $\Sigma$-algebra $U\in \mathrm{Alg}(\Sigma)$ is the so-called {\em unit algebra}, where every carrier set consists of exactly one element {{Cite|M89}} {{Cite|W90}}.
+
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 <i>terminal</i> in $K$ if for every $B \in K$ there is a unique $\Sigma$-homomorphism $h\colon B \longrightarrow  A$ {{Cite|ST99}}.  The terminal algebra does not always exist, but if it does, it is uniquely determined up to isomorphism {{Cite|W90}}. In the case of a sensible signature $\Sigma$, the terminal $\Sigma$-algebra $U\in \mathrm{Alg}(\Sigma)$ is the so-called <i>unit algebra</i>, where every carrier set consists of exactly one element {{Cite|M89}} {{Cite|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)$ {{Cite|M89}}.  In a terminal $\Sigma$-algebra, terms are identified if possible.  The terminal algebra is the coarsest algebra {{Cite|M89}}.
 
* 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)$ {{Cite|M89}}.  In a terminal $\Sigma$-algebra, terms are identified if possible.  The terminal algebra is the coarsest algebra {{Cite|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$ {{Cite|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$ {{Cite|M89}}.
  
===Example of Initial and Terminal $\Sigma$-Algebras===
+
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 <i>monomorphic</i>.
 +
 
 +
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.  
 
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.  
  
===Free $\Sigma$-Algebras===
+
===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 <i>free over $X$ in $K$</i>, 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$ {{Cite|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 {{Cite|EM85}}. A $\Sigma$-algebra $I\in K$ is free over $\emptyset$ in $K$ iff $I$ is initial in $K$ {{Cite|EM85}}.
  
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 {\em 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$ {{Cite|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 {{Cite|EM85}}. A $\Sigma$-algebra $I\in K$ is free over $\emptyset$ in $K$ iff $I$ is initial in $K$ {{Cite|EM85}}.
+
====$\Sigma$ Number Algebras====
  
===Reduct of $\Sigma$-Algebras===
+
Let $\Sigma=(S,F)$ be a signature. A $\Sigma$-algebra is called a <i>$\Sigma$ number algebra</i>, if its carrier sets are recursive subsets of the natural numbers $\mathbb{N}$. It is called <i>recursive</i> if its functions are recursive {{Cite|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 {{Cite|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'$ {{Cite|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')$ {{Cite|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 {{Cite|ST99}}.
+
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 <i>$m$-reduct</i> $A':=A|_m$ of $A$ is a $\Sigma'$-algebra defined as follows {{Cite|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'$ {{Cite|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')$ {{Cite|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 {{Cite|ST99}}.
  
 
===References===
 
===References===

Latest revision as of 14:56, 21 April 2013

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
How to Cite This Entry:
Sigma-algebra (Computer Science). Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sigma-algebra_(Computer_Science)&oldid=29463