many-sorted structure

Let $L$ be a many-sorted language and $S$ the set of sorts. A many-sorted structure $M$ for $L$, or simply an $L$-structure consists of the following:

1. for each sort $s\in S$, a non-empty set $A_s$,

2. for each function symbol $f$ of sort type $(s_1,\mathrm{\dots },s_n)$:

   • if $n>1$, a function $f_M:A_{s_1}\times \mathrm{\cdots }\times A_{s_{n-1}}\to A_{s_n}$

   • if $n=1$ (constant symbol), an element $f_M\in A_{s_1}$

3. for each relation symbol $r$ of sort type $(s_1,\mathrm{\dots },s_n)$, a relation (or subset)

   $$r_M\subseteq A_{s_1}\times \mathrm{\cdots }\times A_{s_n}.$$

A many-sorted algebra is a many-sorted structure without any relations.

Remark. A many-sorted structure is a special case of a more general concept called a many-sorted interpretation, which consists all of items 1-3 above, as well as the following:

• an element $x_M\in A_s$ for each variable $x$ of sort $s$.

Examples.

1. A left module over a ring can be thought of as a two-sorted algebra (say, with sorts $\{s_1,s_2\}$), for there are

   • there are two non-empty sets $M$ (corresponding to sort $s_1$) and $R$ (corresponding to sort $s_2$), where

   • $M$ has the structure of an abelian group (equipped with three operations: $0,-,+$, corresponding to function symbols of sort types $(s_1),(s_1,s_1)$, and $(s_1,s_1,s_1)$)

   • $R$ has the structure of a ring (equipped with at least four operations: $0,-,+,\times$, corresponding to function symbols of sort types $(s_2),(s_2,s_2)$ and $(s_2,s_2,s_2)$ for $+$ and $\times$, and possibly a fifth operation $1$ of sort type $(s_2)$)

   • a function $\cdot :R\times M\to M$, which corresponds to a function symbol of sort type $(s_2,s_1,s_1)$. Clearly, $\cdot$ is the scalar multiplication on the module $M$.

   For a right module over a ring, one merely replaces the sort type of the last function symbol by the sort type $(s_1,s_2,s_1)$.

2. A deterministic semiautomaton $A=(S,\mathrm{\Sigma },\delta )$ is a two-sorted algebra, where

   • $S$ and $\mathrm{\Sigma }$ are non-empty sets, corresponding to sorts, say, $s_1$ and $s_2$,

   • $\delta :S\times \mathrm{\Sigma }\to S$ is a function corresponding to a function symbol of sort type $(s_1,s_2,s_1)$.

3. A deterministic automaton $B=(S,\mathrm{\Sigma },\delta ,\sigma ,F)$ is a two-sorted structure, where

   • $(S,\mathrm{\Sigma },\delta )$ is a semiautomaton discussed earlier,

   • $\sigma$ is a constant corresponding to a nullary function symbol of sort type $(s_1)$,

   • $F$ is a unary relation corresponding to a relation symbol of sort type $(s_1)$.

   Because $F$ is a relation, $B$ is not an algebra.

4. A complete sequential machine $M=(S,\mathrm{\Sigma },\mathrm{\Delta },\delta ,\lambda )$ is a three-sorted algebra, where

   • $(S,\mathrm{\Sigma },\delta )$ is a semiautomaton discussed earlier,

   • $\mathrm{\Delta }$ is a non-empty sets, corresponding to sort, say, $s_3$,

   • $\lambda :S\times \mathrm{\Sigma }\to \mathrm{\Delta }$ is a function corresponding to a function symbol of sort type $(s_1,s_2,s_3)$.