Interpretable structure

In model theory, interpretable structure in a structure M is the name given to various quotients of powers of M with structure inherited via the quotient from M.

Definition

Suppose that $L_{1},L_{2}$ are two first order languages. Let $M$ be an $L_{1}$-structure and $N$ be an $L_{2}$-structure.

Let $n$ be a natural number. Suppose we have chosen the following

• A $L_{1}$-formula $\psi _{D}$ which has $n$ free variables.
• A $L_{1}$-formula $\psi _{E}$ which has $2n$ free variables.
• For each constant symbol $c$ of $L_{2}$ a $L_{1}$-formula $\psi _{c}$ with $n$ free variables.
• For each $m$-ary function symbol $f$ of $L_{2}$ a $L_{1}$-formula $\psi _{f}$ with $(m+1)n$ free variables.
• For each $m$-ary relation symbol symbol $R$ of $L_{2}$ a $L_{1}$-formula $\psi _{R}$ with $mn$ free variables.

Suppose that $\psi _{E}$ defines an equivalence relation $E$ on the set defined by $\psi _{D}$. Suppose that $\sigma$ is a bijection from the equivalence classes of $E$ to the domain of $N$.

The intuition behind the following definition is that the interpretation of each symbol in $L_{2}$ is controlled by the sets defined by the corresponding formula we chose above.

Then we say that $(\psi _{D},\psi _{E},\{\psi _{c}:c\in L_{2}\},\{\psi _{f}:f\in L_{2}\},\{\psi _{R}:R\in L_{2}\},\sigma )$ is an interpretation of $N$ in $M$ iff the following all hold:

• For each constant symbol $c\in L_{2}$ and every $a\in M^{n}$, we have that $\sigma (a/E)=c^{N}\Leftrightarrow M\models \psi _{c}(a)$.
• For each $m$-ary function symbol $f\in L_{2}$ and every $a_{1},\ldots ,a_{m},b\in M^{n}$, we have that $f^{N}(\sigma (a_{1}/E),\ldots ,\sigma (a_{m}/E))=\sigma (b/E)\Leftrightarrow M\models \psi _{f}(a_{1},\ldots ,a_{m},b)$.
• For each $m$-ary relation symbol $R\in L_{2}$ and every $a_{1},\ldots ,a_{m}\in M^{n}$, we have that $R^{N}(\sigma (a_{1}/E),\ldots ,\sigma (a_{m}/E))\Leftrightarrow M\models \psi _{R}(a_{1},\ldots ,a_{m})$.