Why are $n$-ary function symbols interpreted as $n$-ary operations and not general $n$-ary functions?

165 Views Asked by At

I would appreciate if someone here could check the correctness of my reasoning about the following. I'm new to logic.

Let $\mathfrak{M} = \langle M,\mathfrak{I} \rangle$ be a structure for some signature $\mathfrak{L}$. In model theory the interpretation function is defined so that it maps any $n$-ary function symbol to an $n$-ary operation on $M$. Why not map more generally to some $n$-ary function (not necessarily an operation)? This more general function would be defined on subsets of $M$, for example, on $M_1 \times M_2 \times \cdots \times M_n$ into $M_{n+1}$, where $M_i$ is a subset of $M$ for $i=1,2,3,\ldots$.

My understanding is that this can cause problems with the law of excluded middle as follows. Suppose $f$ is some 3-ary function symbol, and $a,b,c$ are constant symbols. Then map $f$ to some general 3-ary function $f^\mathfrak{M}$ on $M_1 \times M_2 \times M_3$ such that $a^\mathfrak{M}$ is not an element of $M_1$. Then we run into the following problem: does $\mathfrak{M}$ satisfy the formula $f(a,b,c) = f(a,b,c)$?

The interpretation of $f(a,b,c)$ is not defined so we cannot say anything about $f(a,b,c) = f(a,b,c),$ which goes against the law of the excluded middle.

Thanks!

1

There are 1 best solutions below

3
On BEST ANSWER

I think the reason is simplicity. When you have a partial function, you have to talk about its domain, and this may be inconvenient.

On the other hand, given a partial function $f\colon D\to M$ with $D\subseteq M^n$, you can extend $f$ to the whole $M^n$ without increasing its epressive power, for example by setting $f(a_1,\ldots,a_n)=a_1$ if $(a_1,\ldots,a_n)\notin D$. Now if we have in our language symbols for this extended $f$ and for $D$, we essentially have the original partial $f$ we started with, but without the hassle of adding more layers to the metalanguage.

On the other hand sometimes (actually, very often in more advanced contexts), we consider many-sorted structures. These are mostly the same as the "normal" structures, except they have many (disjoint) domains, called sorts.

In such a structure, when we write a formula, all variables and quantifiers are restricted to a single sort, and with some experience, you can see that it is not very different from just adding predicates for those sorts as definable sets in a one-sorted structure.

For example, one might consider a vector space to be a structure $((F,+,\cdot,0,1),(V,+),\cdot)$, where $F$ is a field sort and $V$ is a vector space sort, and the last dot is scalar multiplication, and indeed, the field operations are only defined on the field sort, while scalar multiplication is a function from $F\times V$ to $V$.

Similarly, valued fields are usually considered as three-sorted structures with sorts for base field, residue field and value group (though versions with infinitely many sorts are also not uncommon).

Multi-sorted structures are, as far as I know, usually not taught right away in introductory courses, I suspect partly because they are less classical, and partly for pedagogical reasons. But all the properties of one-sorted structures generally also hold for many-sorted structures.