manysorted language
A manysorted language is a variation of the classical firstorder language. Whereas structures^{} of a firstorder language consist of a single universe^{}, structures of a manysorted language may contain many “universes”, where each universe is “named” by a symbol called “sort”, hence the name “manysorted”.
To formalize the notion of a manysorted language, we start with a nonempty set $S$ whose elements we call sorts. Let ${S}^{+}$ be the set of all (finite) nonempty words over $S$. Elements of ${S}^{+}$ are called sort types and are written as tuples. So instead of writing ${s}_{1}{s}_{2}\mathrm{\cdots}{s}_{n}\in {S}^{+}$, it is written $({s}_{1},{s}_{2},\mathrm{\cdots},{s}_{n})\in {S}^{+}$.
The next item to be defined is the underlying signature^{} of a manysorted language. A signature $\mathrm{\Sigma}$ consists of

•
a nonempty set $S$ of sorts,

•
a set $F$ of function symbols, and

•
a set $R$ of (nonlogical) relation symbols,
such that each element in $F\cup R$ corresponds to a sort type. In other words, there is a function $t:F\cup R\to {S}^{+}$, and for every $r\in F\cup R$, $t(r)$ is its sort type. An element $c\in F$ such that $t(c)\in S$ is called a constant symbol (of sort $t(c)$).
In addition^{} to the signature $\mathrm{\Sigma}$, we introduce additional symbols:

•
the set $V$ of variables^{}, such that each sort $s\in S$ corresponds to a countably infinite^{} subset ${V}_{s}\subseteq V$ of variables. In other words, there is a function $v:V\to S$, such that for each $s\in S$, ${v}^{1}(s)$ is countably infinite. For each variable $x\in V$, its sort is defined to be $v(x)$.

•
logical predicates^{}: $\vee ,\mathrm{\neg},\forall $

•
the equality relation symbol: $=$, and

•
the left and right parentheses: $(,)$
Using $\mathrm{\Sigma}$ and the additional symbols above, we can build terms inductively as follows:

•
each variable $x\in V$ is a term of sort $v(x)$

•
if $f\in F$ is a function symbol of sort type $({s}_{1},\mathrm{\dots},{s}_{n})$, and for each $i=1,\mathrm{\dots},n1$, ${t}_{i}$ is a term of sort ${s}_{i}$, then $f({t}_{1},\mathrm{\dots},{t}_{n1})$ is a term of sort ${s}_{n}$.

•
all the terms are built this way.
Finally, from the terms, we inductively define formulas^{}:

•
if ${t}_{1}$ and ${t}_{2}$ are terms of the same sort, then $({t}_{1}={t}_{2})$ is a formula

•
if $r\in R$ is a relation symbol of sort type $({s}_{1},\mathrm{\dots},{s}_{n})$, and for each $i=1,\mathrm{\dots},n$, ${t}_{i}$ is a term of sort ${s}_{i}$, then $r({t}_{1},\mathrm{\dots},{t}_{n})$ is a formula

•
if $\alpha $ is a formula, then so is $(\mathrm{\neg}\alpha )$

•
if $\alpha ,\beta $ are formulas, then so is $(\alpha \vee \beta )$

•
if $\alpha $ is a formula and $x\in V$ is a variable, then so is $(\forall x(\alpha ))$

•
all the formulas are formed this way.
The signature $\mathrm{\Sigma}$, additional symbols, and terms and formulas subsequently defined constitute what is known as the manysorted language $L=L(\mathrm{\Sigma})$ on $\mathrm{\Sigma}$.
As in first order language, the outer most parentheses may be eliminated without causing much harm, so that $(\mathrm{\neg}\alpha )$ becomes $\mathrm{\neg}\alpha $. In addition, we may introduce other familiar logical symbols $\wedge ,\to ,\leftrightarrow $, and $\exists $ in terms of $\vee ,\mathrm{\neg}$, and $\forall $. The specifics of how this is done can be found in the entry on first order language.
From this definition, we see at once that the classical first order language is a onesorted language^{} ($S=1$). Sort types are identified with their lengths. Thus, the sort type of a function or a relation symbol is its arity.
Remark. It is not hard to show that a manysorted language is not much different from a firstorder language. Provided that $V$ is countably infinite, a manysorted language $L$ can be “converted” into a firstordered language ${L}_{1}$. Basically, all the function and relation symbols in $L$ are in ${L}^{\prime}$, as well as the additional symbols such as variables and logical symbols. For each sort $s\in S$, we introduce a new unary relation symbol ${P}_{s}$ in ${L}_{1}$. For any formula that contains a subformula of the form $\forall x\varphi (x)$, we replace each occurrence of such a subformula by a formula of the form $\forall x({P}_{s}(x)\to \varphi (x))$, where $x$ is a variable of sort $s$ and $\varphi $ is some formula in which $x$ occurs as a free variable^{}. The result is that ${L}_{1}$ becomes a onesorted language.
Title  manysorted language 
Canonical name  ManysortedLanguage 
Date of creation  20130322 17:44:40 
Last modified on  20130322 17:44:40 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  12 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03B70 
Classification  msc 03C07 
Classification  msc 03B10 
Synonym  many sorted language 
Synonym  manysorted logic 
Defines  sort 
Defines  sort type 