A structure is defined as the triple $ (S, \sigma, I)$ where S is the domain, $\sigma$ is the signature which is basically a set of function & relation symbols, & the interpretation function I which assigns arity to each function or relation symbol. If $ \sigma = (+)$ then $ I_S(+) \ : S \ \times \ S \ \rightarrow \ S$. That all makes sense to me.

My questions are about a two-sorted structure in light of the above considerations. The working definition of a two-sorted structure I've been given, my example being a vector space, is the following (from Ebbinghaus et al. - Mathematical Logic):

$ \mathfrak B \ = \ (F, \ V, \ +^F, \ \cdot^F, \ 0^F, \ 1^F, \ \bigoplus^V, \ e^V, \ \bigotimes^{FV})$,

needless to say this isn't of the form wikipedia offers. Wikipedia defines a structure formally as a triple. In my above definition of a vector space I see some of the components will fit into a signature, but I have two sets in that structure, not one set like the wiki definition.

1: I'd like to know how you write a two-sorted structure in the form $ (S, \sigma, I)$, which wikipedia calls the formal definition of a structure. I mean there are two sets F & V in this definition, not just one set S.

My thinking is that you can still write $ (S, \sigma, I)$ & indicate that both F & V are subsets of S. However, it could be that the domain S is just so general that it allows many independent sets. This is what I don't really know. All I'm sure of is that the domain contains an alphabet of symbols with no meaning, the meaning being ascribed by the interpretation function in concert with function symbols from the signature (I think!).

2: I'd like to know how the interpretation function works in a two-sorted structure. If you check the wikipedia page they have formed $ ( \mathbb{Q}, \sigma, I)$ & by this notation made it clear that, say +, is constrained to $ \mathbb{Q} $ by: $ I_\mathbb{Q} \ : \mathbb{Q}\ \times \ \mathbb{Q} \ \rightarrow \ \mathbb{Q}$.

My thinking is that if $ \mathbb{Q}$ is the set that + applies to but your structure is something of the form $ (S, \sigma, I)$ you can highlight that a function applies to some subset $ \mathbb{Q}$ of S with the subscript on the I, i.e. $ I_\mathbb{Q}$. That assumes sets like $ \mathbb{Q}$ are actually subsets of the domain of the structure & not independent members of the domain. In any case I think that the interpretation function clearly states what set it's working in via the subscript but I'd just like clarification or further explanation if it's not so simple.

Basically just trying to understand a vector space in terms of logic in light of the varying forms of notation I've given in this post. Would really appreciate some input on this subject, thanks!

  • $\begingroup$ Extend the definition of structure to many-sorted (multisorted) structure. (Sort=domain.) BTW, for vector spaces/modules you need another trick: a vector space has 1 sort $V$ and $\forall k\in F$ it has an 1-ary function which multiplies a vector by $k$. Then homomorphisms of these structures are linear transformations of vector spaces. $\endgroup$ – beroal Apr 16 '11 at 16:38

There are various tricks that will work. For example, if the language has no function symbols, one can introduce two additional unary relation symbols, $T_1$ and $T_2$ ("Type $1$" and "Type $2$"). Any sentence of the two-sorted language can be simulated in this way by relativizing the quantifiers suitably.

With function symbols, there is always the possibility of replacing $n$-ary function symbols by $(n+1)$-ary relation symbols, and using the trick of the first paragraph. If function symbols are really desired, one can introduce a constant symbol to be the target of the interpretation of the function symbols on objects of the wrong type, or of mixed types.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy