Logic: difference between "interpretation" and "structure"

Question

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.

Answer 1

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).

Answer 2

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.)