I never quite got the difference between an "interpretation" and a "structure" in logic. To me, they always sound like the same thing: a function from elements of a language to a particular universe.

The "Structure (mathematical logic)" page on Wikipedia says:

Formally, a structure can be defined as a triple $\mathcal A=(A, \sigma, I)$ consisting of a domain $A$, a signature $\sigma$, and an interpretation function $I$ that indicates how the signature is to be interpreted on the domain.

From that, an interpretation is merely a component of a structure. However, I would say the function $I$ necessarily contains information about its domain (as in "function domain", a different sense of "domain" as used in the quote above) and its codomain, which must be $\sigma$ and $A$, respectively, so there is always a one-to-one correspondence between structures and interpretations.

Can anyone clarify what I am missing here? Thanks.


It's a technicality, but the intepretation doesn't contain all the information needed to recover the structure in all cases: consider the signature $\sigma = (R^2)$ with a single binary relation symbol $R$ and the structure $(A, \sigma, I)$ where $A = \Bbb{N}$ and $I(R) = \emptyset$. I.e., we've taken the universe of the structure to be the natural numbers and interpreted $R$ as the relation which is always false. You can't recover $A$ or $\sigma$ from $I$ (which doesn't tell you that $A = \Bbb{N}$ or that $R$ is a binary relation).

  • $\begingroup$ Makes sense, thanks. I was assuming that a function always "carries" information about its domain and codomain, even if it is a function like the one you defined. By talking about functions "carrying" information, I am perhaps giving away my background in computer science :-) But yes, if a function is just a relation, which is just a set, then such information is not really available. $\endgroup$ – user118967 Feb 27 '16 at 0:11

I think the term "interpretation function" might be misleading you a bit. It's really better to think of a family of interpretation functions indexed by arity and whether they are interpreting function symbols or relation symbols. We just use the same symbol for all of these as an abuse of notation. We could write $I_r^n : \{ s \in \sigma\ |\ \text{ar}(s) = n\text{ and } s\text{ is a relation}\}\to 2^{A^n}$ and $I_f^n : \{ s \in \sigma\ |\ \text{ar}(s) = n\text{ and } s\text{ is a function}\}\to A^{A^n}$ which get lifted to arbitrary terms and expressions compositionally. While we could say the elements of $\sigma$ are essentially triples from a set like $\{r,f\}\times\mathbb{N}\times|\sigma|$ and thus write $I : \{r,f\}\times\mathbb{N}\times|\sigma|\to\ ?$ but it's not clear what to put in the codomain short of unioning together a bunch of function and relation types. If we capture the connection between the domain and codomain we get a family (essentially a dependently typed function).

From the categorical perspective of Lawvere theories, the interpretation function is represented by a (finite-product preserving) functor from a category that essentially represents the signature. From this perspective (which doesn't immediately handle relation symbols, but that's an easy generalization), $I$ is a functor, $I : \sigma \to \mathbf{Set}$, such that $I(1) = A$, where $1$ here just represents an object of $\sigma$ and $n$ is an $n$-fold product of $1$. Now since $I$ preserves finite products, $I(n) = A^n$. A function symbol, $\mathtt{f}$, with arity $n$ is represented by an arrow $\mathtt{f} : n \to 1$ in $\sigma$. Then the normal action of functors on arrows takes $\mathtt{f}$ to $I(\mathtt{f}) : A^n \to A$. (Actually, for technical reasons usually the opposite category of $\sigma$ is used so $n$ becomes the $n$-fold coproduct of $1$ which makes more sense notationally.)


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.