Interpretable structure

In model theory, a structure "N" is called interpretable in "M" if all the components (universe, functions, relations etc.) of "N" can be defined in terms of the components of "M". In particular, the universe of "N" is represented as a definable subset of some power of the universe of "M"; sometimes a definable quotient of the universe of "M" is employed instead of the universe itself. Interpretability entails that every formula in the language of "N" can be translated into corresponding formula in the language of "M" that essentially expresses the same content.

One of the goals of set theory in early 20th century was to build a set-theoretic universe in which all mathematical structures could be interpreted Fact|date=July 2007.

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

Example: Valued Fields

Let $L\_\{RING\}$ be a language with two binary function symbols $+,\; imes$, a unary function symbol $-$, two constant symbols $0,1$. We call this the language of rings. Let $L$ be an extension of $L\_\{RING\}$ by the unary predicate symbol $V$.

Suppose that $F$ is a field, and $D$ is a Valuation ring of $F$.

Suppose we make $F$ into an $L$-structure by interpreting $+,\; imes,-,0,1$ via the field on $F$, and so that for each $a\; in\; F$, $F\; models\; V(a)$ iff $a\; in\; D$.

Now, the maximal ideal $M$ of $D$ is definable (without parameters) via the formula $V(x)\; land\; forall\; y\; (yx=1\; ightarrow\; lnot\; v(y)$.

In this way one can show that the residue field $D/M$ as a structure in the language of rings is interpretable in $F$.

Similarly, the units $F^*$of $F$ and the units $D^*$ of $D$ are definable, and one can interpret the quotient as an ordered group.

Note that in general there are many more structures interpretable in a valued field.