You are here
Homemanysorted structure
Primary tabs
manysorted structure
Let $L$ be a manysorted language and $S$ the set of sorts. A manysorted structure $M$ for $L$, or simply an $L$structure consists of the following:
1. for each sort $s\in S$, a nonempty 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_{{n1}}}}\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 manysorted algebra is a manysorted structure without any relations.
Remark. A manysorted structure is a special case of a more general concept called a manysorted interpretation, which consists all of items 13 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 twosorted algebra (say, with sorts $\{s_{1},s_{2}\}$), for there are

there are two nonempty 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 twosorted algebra, where

$S$ and $\Sigma$ are nonempty 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 twosorted 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 threesorted algebra, where

$(S,\Sigma,\delta)$ is a semiautomaton discussed earlier,

$\Delta$ is a nonempty 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).
Mathematics Subject Classification
03B70 no label found03B10 no label found03C07 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections