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

for each sort $s\in S$, a non-empty set $A_{s}$,

2. 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. 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. 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. 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. 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. 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})$.

## References

• 1 J. D. Monk, Mathematical Logic, Springer, New York (1976).
 Title many-sorted structure Canonical name ManysortedStructure Date of creation 2013-03-22 17:45:17 Last modified on 2013-03-22 17:45:17 Owner CWoo (3771) Last modified by CWoo (3771) Numerical id 9 Author CWoo (3771) Entry type Definition Classification msc 03B70 Classification msc 03B10 Classification msc 03C07 Synonym many sorted structure Synonym many sorted algebra Defines many-sorted interpretation Defines many-sorted algebra