information:highlighting, linguistic:paraphrasing, linguistic:voice_change, information:filtering
Many-sorted structures

Structures as defined above are sometimes called one-sorted structure s to distinguish them from the more general many-sorted structure s. A many-sorted structure can have an arbitrary number of domains. The sorts are part of the signature, and they play the role of names for the different domains. Many-sorted signatures also prescribe on which sorts the functions and relations of a many-sorted structure are defined. Therefore, the arities of function symbols or relation symbols must be more complicated objects such as tuples of sorts rather than natural numbers.

Vector spaces, for example, can be regarded as two-sorted structures in the following way. The two-sorted signature of vector spaces consists of two sorts V (for vectors) and S (for scalars) and the following function symbols:

If V is a vector space over a field F, the corresponding two-sorted structure V {\displaystyle {\mathcal {V}}} consists of the vector domain | V | V = V {\displaystyle |{\mathcal {V}}|_{V}=V}, the scalar domain | V | S = F {\displaystyle |{\mathcal {V}}|_{S}=F}, and the obvious functions, such as the vector zero 0 V V = 0 ∈ | V | V {\displaystyle 0_{V}^{\mathcal {V}}=0\in |{\mathcal {V}}|_{V}}, the scalar zero 0 S V = 0 ∈ | V | S {\displaystyle 0_{S}^{\mathcal {V}}=0\in |{\mathcal {V}}|_{S}}, or scalar multiplication × V: | V | S × | V | V → | V | V {\displaystyle \times ^{\mathcal {V}}:|{\mathcal {V}}|_{S}\times |{\mathcal {V}}|_{V}\rightarrow |{\mathcal {V}}|_{V}}.

Many-sorted structures are often used as a convenient tool even when they could be avoided with a little effort. But they are rarely defined in a rigorous way, because it is straightforward and tedious (hence unrewarding) to carry out the generalization explicitly.

In most mathematical endeavours, not much attention is paid to the sorts. A many-sorted logic however naturally leads to a type theory. As Bart Jacobs puts it: "A logic is always a logic over a type theory." This emphasis in turn leads to categorical logic because a logic over a type theory categorically corresponds to one ("total") category, capturing the logic, being fibred over another ("base") category, capturing the type theory.