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,\ldots, s_n)$ :
   • if $n>1$ , a function $f_M: A_{s_1}\times \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,\ldots,s_n)$ , a relation (or subset) $$r_M\subseteq A_{s_1}\times \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:

4.

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 $\lbrace s_1,s_2\rbrace$ ), 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,\Sigma,\delta)$ is a two-sorted algebra, where
   • $S$ and $\Sigma$ are non-empty sets, corresponding to sorts, say, $s_1$ and $s_2$ ,
   • $\delta: S\times \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,\Sigma,\delta,\sigma,F)$ is a two-sorted structure, where
   • $(S,\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,\Sigma,\Delta,\delta,\lambda)$ is a three-sorted algebra, where
   • $(S,\Sigma,\delta)$ is a semiautomaton discussed earlier,
   • $\Delta$ is a non-empty sets, corresponding to sort, say, $s_3$ ,
   • $\lambda: S\times \Sigma \to \Delta$ is a function corresponding to a function symbol of sort type $(s_1,s_2,s_3)$ .

Bibliography

1

J. D. Monk, Mathematical Logic, Springer, New York (1976).