Section 2.7: Interpretations Between Theories

Sometimes we want to show that a theory $T'$ in a language $L'$ is at least as powerful as a theory $T$ in a language $L$ . We can do this by “embedding” the theory $T$ with language $L$ into the theory $T'$ with language $L'$ . This is done by translating from $L$ to $L'$ in such a way that the sentences of $T$ are translated to the sentences of $T'$ . In fact, we are going to do just the opposite. The idea is that, given a translation $\pi$ of $L$ to $L'$ , for any model $\mathfrak{B}$ of $T'$ , there is a structure $^{\pi}\mathfrak{B}$ in $L$ with the universe being a subset of $\mathfrak{B}$ (defined by the translation of $\forall$ ), such that any $\phi$ in $L$ is true in $^{\pi}\mathfrak{B}$ (with some $s$ ) iff the corresponding translation $\phi^{\pi}$ is true in $\mathfrak{B}$ (with the same $s$ ). Given this fact, and the fact that the sentences in $T'$ are exactly those logically implied by $T'$ , we conclude that the set of sentences true in every $^{\pi}\mathfrak{B}$ (sentences in so-called $\pi^{-1}(T')=\mbox{Th}\{{}^{\pi}\mathfrak{B}|\mathfrak{B}\mbox{ models }\mbox{T'}\}$ ) are those that their translations are in $T'$ (because the translations are true in every model of $T'$ ). Note, that up to this point, we have not considered the theory $T$ itself, and everything is simply based on the translation of $L$ into $L'$ and $T'$ . So, at this point, we choose a translation $\pi$ of $L$ into $L'$ and $T'$ such that $T\subseteq\pi^{-1}(T')$ , or, even better, $T=\pi^{-1}(T')$ .

The flow of discussion is reorganized here compared to the text, as we develop the examples a) showing that $\mathfrak{Z}=(\mathbb{Z};+,\cdot)$ is as powerful as $\mathfrak{N}=(\mathbb{N};0,\mathbb{S})$ , and b) defining functions, following the general discussion.

Notation

Given a formula $\phi$ , by $\phi(t_{1},\ldots,t_{k})$ we mean $((\psi_{t_{1}}^{v_{1}})\ldots)_{t_{k}}^{v_{k}}$ where $\psi$ is an alphabetical variant of $\phi$ (see Section 2.4) such that all $t_{i}$ are substitutable for $v_{i}$ .

Interpretations of languages

An interpretation is a way in which $L$ is translated to $L'$ and $T'$ . We need to translate each parameter of $L$ to the language of $L'$ , and we need to consider a specific theory $T'$ because we must ensure that, for example, the translation of $\forall$ specifies a non-empty set, and the translation of a function symbol $f$ indeed specifies a function, i.e. there should be a sentence in $T'$ that says that our translation is indeed a function (in every model of $T'$ ).

An interpretation $\pi$ of $L$ into $T'$ is a function that assigns to each parameter $*$ of $L$ a formula $\pi_{*}$ of $L'$ such that the following requirements hold ( $\mbox{free}(\phi)$ is the set of free variables of $\phi$ ).

$\mbox{free}(\pi_{\forall})\subseteq\{v_{1}\}$ , and $T'\vDash\exists v_{1}\pi_{\forall}$ .
For an $n$ -place predicate symbol $P$ , $\mbox{free}(\pi_{P})\subseteq\{v_{1},\ldots,v_{n}\}$ .
For an $n$ -place function symbol $f$ , $\mbox{free}(\pi_{f})\subseteq\{v_{1},\ldots,v_{n},v_{n+1}\}$ , and $T'\vDash\forall v_{1}\ldots\forall v_{n}(\pi_{\forall}\rightarrow\pi_{\forall}(v_{2})\rightarrow\ldots\rightarrow\pi_{\forall}(v_{n})\rightarrow$ $\exists x(\pi_{\forall}(x)\wedge\forall v_{n+1}(\pi_{f}\leftrightarrow v_{n+1}=x)))$ .
For a constant symbol $c$ , $\mbox{free}(\pi_{c})\subseteq\{v_{1}\}$ , and $T'\vDash\exists x(\pi_{\forall}(x)\wedge\forall v_{1}(\pi_{c}\leftrightarrow v_{1}=x))$ .

1 says that whatever is a model $\mathfrak{B}$ of $T'$ , $\pi_{\forall}$ defines a non-empty subset of $|\mathfrak{B}|$ (the universe for our interpretation of $L$ ). 2 says that $\pi_{p}$ defines an $n$ -place relation (which can be further restricted to the universe defined in 1). 3 says that whatever is a model $\mathfrak{B}$ of $T'$ , $\pi_{f}$ defines an $(n+1)$ -place relation such that its restriction to the universe defined in 1 is a function (the last element is uniquely defined based on the all others). 4 is just a particular case of 3.

Structures defined by interpretations

Given an interpretation $\pi$ of $L$ into $T'$ , and a model $\mathfrak{B}$ of $T'$ , we define the structure $^{\pi}\mathfrak{B}$ for $L$ as follows.

$|{}^{\pi}\mathfrak{B}|=\{d\in|\mathfrak{B}||\vDash_{\mathfrak{B}}\pi_{\forall}[[d]]\}$ , i.e. the set defined in $\mathfrak{B}$ by $\pi_{\forall}$ .
$P^{^{\pi}\mathfrak{B}}=\{<d_{1},\ldots,d_{n}>\in|{}^{\pi}\mathfrak{B}||\vDash_{\mathfrak{B}}\pi_{P}[[d_{1},\ldots,d_{n}]]\}$ , i.e. the relation defined in $\mathfrak{B}$ by $\pi_{P}$ restricted to $|{}^{\pi}\mathfrak{B}|$ .
$f^{^{\pi}\mathfrak{B}}(d_{1},\ldots,d_{n})=d_{n+1}$ iff $\vDash_{\mathfrak{B}}\pi_{f}[[d_{1},\ldots,d_{n+1}]]$ , i.e. the function on $|{}^{\pi}\mathfrak{B}|$ defined in $\mathfrak{B}$ by $\pi_{f}$ .

Syntactical translations

Given an interpretation $\pi$ of $L$ into $T'$ , and a formula $\phi$ of $L$ , we define the syntactical translation $\phi^{\pi}$ of $\phi$ into $L'$ as follows.

For an atomic formula:
1. if $\phi=Px_{1}\ldots x_{n}$ , then $\phi^{\pi}=\pi_{P}(x_{1},\ldots,x_{n})$ ,
2. otherwise, if $g$ is the rightmost function symbol in $\phi$ , and $g$ starts the segment $gx_{1}\ldots x_{n}$ of $\phi$ , then $\phi^{\pi}=\forall y(\pi_{g}(x_{1},\ldots,x_{n},y)\rightarrow(\phi_{y}^{gx_{1}\ldots x_{n}})^{\pi})$ , where $y$ does not occur in $\phi$ , and $\phi_{y}^{gx_{1}\ldots x_{n}}$ is the formula obtained from $\phi$ by replacing the segment $gx_{1}\ldots x_{n}$ with $y$ .
$(\neg\phi)^{\pi}=(\neg\phi^{\pi})$ .
$(\phi\rightarrow\psi)^{\pi}=(\phi^{\pi}\rightarrow\psi^{\pi})$ .
$(\forall x\phi)^{\pi}=\forall x(\pi_{\forall}(x)\rightarrow\phi^{\pi})$ .

For any model $\mathfrak{B}$ of $T'$ and $s:V\rightarrow|^{\pi}\mathfrak{B}|$ , $\vDash_{^{\pi}\mathfrak{B}}\phi[s]$ iff $\vDash_{\mathfrak{B}}\phi^{\pi}[s]$ .

This is a good moment to stop for a second and think about what we have so far. If you understand and clearly see the picture of what is going on, it should be obvious for you, why the lemma holds. When we define an interpretation $\pi$ of $L$ into $T'$ , we, essentially, do two thing. First, for any model $\mathfrak{B}$ of $T'$ , we define a subuniverse of $|\mathfrak{B}|$ (by $\pi_{\forall}$ ) and all parameters of $L$ on this subuniverse, i.e. we define a structure $^{\pi}\mathfrak{B}$ for $L$ , so that for every formula $\phi$ of $L$ we can verify whether it is satisfied in $^{\pi}\mathfrak{B}$ with some $s:V\rightarrow|{}^{\pi}\mathfrak{B}|$ or not. Note that we use the relations defined by $\pi$ to define the subuniverse and a particular interpretation of the parameters of $L$ . At the same time, we can instead translate $\phi$ into $L'$ using the relations defined by $\pi$ in such a way, that every translation claims something in $L'$ about the points in $|{}^{\pi}\mathfrak{B}|$ only (as long as the range of $s$ is in $|{}^{\pi}\mathfrak{B}|$ ). What the lemma says is that the two methods to verify whether $\phi$ is satisfied coincide.

a) $\phi=Px_{1}\ldots x_{n}$ . Then, $\vDash_{^{\pi}\mathfrak{B}}\phi[s]$ iff $<s(x_{1}),\ldots,s(x_{n})>\in P^{^{\pi}\mathfrak{B}}$ iff (by definition of $P^{^{\pi}\mathfrak{B}}$ ) $\vDash_{\mathfrak{B}}\pi_{P}[[s(x_{1}),\ldots,s(x_{n})]]$ iff $\vDash_{\mathfrak{B}}\pi_{P}(x_{1},\ldots,x_{n})[s]$ , which is just $\vDash_{\mathfrak{B}}\phi^{\pi}[s]$ .

b) $\phi$ is atomic and has $m$ function symbols with the rightmost function symbol $g$ starting the segment $gx_{1}\ldots x_{n}$ . This is the only tricky point to understand, which we show by induction. Then, $\vDash_{^{\pi}\mathfrak{B}}\phi[s]$ iff $\vDash_{^{\pi}\mathfrak{B}}\mbox{\phi}_{y}^{gx_{1}\ldots x_{n}}[s(y|g^{^{\pi}\mathfrak{B}}(s(x_{1}),\ldots,s(x_{n})))]$ (by definition of satisfaction). Now, by definition of $g^{^{\pi}\mathfrak{B}}$ , $g^{^{\pi}\mathfrak{B}}(s(x_{1}),\ldots,s(x_{n}))=b$ where $b\in|{}^{\pi}\mathfrak{B}|$ is the unique element such that $\vDash_{\mathfrak{B}}\pi_{g}[[s(x_{1}),\ldots,s(x_{n}),b]]$ . So, we continue, iff

where $\mbox{\phi}_{y}^{gx_{1}\ldots x_{n}}$ has $m-1$ function symbols. By induction,

iff $\vDash_{\mathfrak{B}}(\mbox{\phi}_{y}^{gx_{1}\ldots x_{n}})^{\pi}[s(y|b)]$ iff $\vDash_{\mathfrak{B}}\forall y(\pi_{g}(x_{1},\ldots,x_{n},y)\rightarrow(\mbox{\phi}_{y}^{gx_{1}\ldots x_{n}})^{\pi})[s]$ , which is just $\vDash_{\mathfrak{B}}\phi^{\pi}[s]$ . This last “iff” follows from the fact that $b$ is the unique element in $|{}^{\pi}\mathfrak{B}|$ such that $\vDash_{\mathfrak{B}}\pi_{g}(x_{1},\ldots,x_{n},y)[s(y|b)]$ .

c) $\vDash_{^{\pi}\mathfrak{B}}\neg\phi[s]$ iff $\not\vDash_{^{\pi}\mathfrak{B}}\phi[s]$ iff $\not\vDash_{\mathfrak{B}}\phi^{\pi}[s]$ iff $\vDash_{\mathfrak{B}}\neg\phi^{\pi}[s]$ iff $\vDash_{\mathfrak{B}}(\neg\phi)^{\pi}[s]$ .

d) $\vDash_{^{\pi}\mathfrak{B}}\phi\rightarrow\psi[s]$ iff $\not\vDash_{^{\pi}\mathfrak{B}}\phi[s]$ or $\vDash_{^{\pi}\mathfrak{B}}\psi[s]$ iff $\not\vDash_{\mathfrak{B}}\phi^{\pi}[s]$ or $\vDash_{\mathfrak{B}}\psi^{\pi}[s]$ iff $\vDash_{\mathfrak{B}}\phi^{\pi}\rightarrow\psi^{\pi}[s]$ iff $\vDash_{\mathfrak{B}}(\phi\rightarrow\psi)^{\pi}[s]$ .

e) $\vDash_{^{\pi}\mathfrak{B}}\forall x\phi[s]$ iff for every $d\in|{}^{\pi}\mathfrak{B}|$ , $\vDash_{^{\pi}\mathfrak{B}}\phi[s(x|d)]$ iff for every $d\in|{}^{\pi}\mathfrak{B}|$ , $\vDash_{\mathfrak{B}}\phi^{\pi}[s(x|d)]$ iff for every $d\in|\mathfrak{B}|$ , $\vDash_{\mathfrak{B}}\pi_{\forall}(x)\rightarrow\phi^{\pi}[s(x|d)]$ iff $\vDash_{\mathfrak{B}}\forall x(\pi_{\forall}(x)\rightarrow\phi^{\pi})[s]$ iff $\vDash_{\mathfrak{B}}(\forall x\phi)^{\pi}[s]$ .

Interpretations of theories

Given the lemma, we can now introduce the largest theory of $L$ such that the interpretation of every sentence in the theory is in $T'$ .

We define the set $\pi^{-1}[T']$ of $L$ -sentences as follows, $\pi^{-1}[T']$ $=\{\sigma|\sigma\mbox{ is an }L\mbox{-sentence true in every structure }{}^{\pi}\mathfrak{B}\}$ $=\mbox{Th}\{^{\pi}\mathfrak{B}|\mathfrak{B}\mbox{ models }T'\}$ .

$\sigma\in\pi^{-1}[T']$ iff $\sigma^{\pi}\in T'$ .

An interpretation $\pi$ of $T$ into $T'$ is an interpretation of $L$ into $T'$ such that $T\subseteq\pi^{-1}[T']$ .

Alternatively, it just means that $\sigma\in T\Rightarrow\sigma^{\pi}\in T'$ .

An interpretation of $T$ into $T'$ is called a faithful interpretation iff $\sigma\in T\Leftrightarrow\sigma^{\pi}\in T'$ .

Alternatively, this means that $T=\pi^{-1}[T']$ .
If $T$ is complete and $T'$ is satisfiable, then any interpretation of $T$ into $T'$ is faithful.

Same language

If $L=L'$ , then there is the identity interpretation $\iota$ of $L$ into $T'$ such that $\iota_{\forall}=v_{1}=v_{1}$ , $\iota_{P}=Pv_{1}\ldots v_{n}$ , and $\iota_{f}=fv_{1}\ldots v_{n}=v_{n+1}$ . Accordingly, for every model $\mathfrak{B}$ of $T'$ , $|^{\pi}\mathfrak{B}|=|\mathfrak{B}|$ , $P^{^{\pi}\mathfrak{B}}=P^{\mathfrak{B}}$ , $f^{^{\pi}\mathfrak{B}}=f^{\mathfrak{B}}$ , and $c^{^{\pi}\mathfrak{B}}=c^{\mathfrak{B}}$ , i.e. $^{\pi}\mathfrak{B}=\mathfrak{B}$ . $\iota$ is an interpretation of $T$ into $T'$ iff $T\subseteq\mbox{Th}\{^{\pi}\mathfrak{B}|\mathfrak{B}\mbox{ models }T'\}$ $=\mbox{Th}\{\mathfrak{B}|\mathfrak{B}\mbox{ models }T'\}$ $=\mbox{Th}\mbox{Mod}T'=T'$ .

ℨ and 𝔑

We want to show that the theory of $\mathfrak{Z}$ is as powerful as the theory of $\mathfrak{N}$ . For this, we want to find an interpretation $\pi$ of the theory of $\mathfrak{N}$ into the theory of $\mathfrak{Z}$ .

$\pi_{\forall}$ . We want to find a formula such that for every model $\mathfrak{B}$ of the theory of $\mathfrak{Z}$ , it will define $|^{\pi}\mathfrak{B}|$ as the subset of non-negative integers. But we only have $+$ and $\cdot$ to define the subset. If it was the set of real numbers, we could have used something like $\exists xx\cdot x=v_{1}$ to define it. But for the set of integers we need to use something else. It is known (the Lagrange’s theorem) that an integer number is non-negative iff it is a sum of four squares. Hence, we can use the following formula, $\pi_{\forall}=\exists v_{2}\exists v_{3}\exists v_{4}\exists v_{5}v_{1}=v_{2}^{2}+v_{3}^{2}+v_{4}^{2}+v_{5}^{2}$ . Note, that $\vDash_{\mathfrak{B}}\pi_{\forall}[s]$ iff $s(v_{1})\ge0$ (here, $\ge$ means a non-negative integer number in our particular structure $\mathfrak{Z}$ ).
$\pi_{0}$ . This has to be defined as a $1$ -place relation. Consider $\pi_{0}=v_{1}+v_{1}=v_{1}$ . In $\mathfrak{Z}$ , $\vDash_{\mathfrak{B}}\pi_{0}[s]$ iff $s(v_{1})=0$ .
$\pi_{\mathbb{S}}$ . This $1$ -place function symbol has to be defined as a -place relation. Consider $\pi_{\mathbb{S}}=\forall v_{3}(v_{3}\cdot v_{3}=v_{3}\rightarrow v_{3}+v_{3}\neq v_{3}\rightarrow v_{2}=v_{1}+v_{3})$ . In other words, we just say that for every number assigned, if it is one, then $v_{1}$ plus this number is equal to $v_{2}$ . Alternatively, it seems, we could have used $\pi_{\mathbb{S}}=\exists v_{3}(v_{3}\cdot v_{3}=v_{3}\wedge v_{3}+v_{3}\neq v_{3}\wedge v_{2}=v_{1}+v_{3})$ , which says there exists $1$ and $v_{2}=v_{1}+1$ .

Then, $\pi$ is a faithful interpretation of $\mathfrak{N}$ into $\mathfrak{Z}$ . Indeed, $^{\pi}(\mathbb{Z};+,\cdot)=(\mathbb{N};0,\mathbb{S})$ , and $\vDash_{(\mathbb{N};0,\mathbb{S})}\sigma$ iff $\vDash_{^{\pi}(\mathbb{Z};+,\cdot)}\sigma$ iff $\vDash_{(\mathbb{Z};+,\cdot)}\sigma^{\pi}$ .

Defining Functions

...definitions are unlike theorems and unlike axioms. Unlike theorems, definitions are not things we prove... unlike axioms, we do not expect definitions to add substantive information. A definition is expected to add to our convenience, not to our knowledge.

Consider a theory $T$ not yet containing the 1-place function symbol $f$ . Let $\delta=\forall v_{1}\forall v_{2}(fv_{1}=v_{2}\leftrightarrow\phi),$ where $\phi$ is a wff (not containing $f$ ), in which only $v_{1}$ and $v_{2}$ may occur free. Then, the following are equivalent:

(a) (the definition is non-creative) For every $\sigma$ not containing $f$ , if $T;\delta\vDash\sigma$ , then $T\vDash\sigma$ .

(b) ( $f$ is well-defined) The sentence $\epsilon=\forall v_{1}\exists!v_{2}\phi$ is in $T$ (see Exercise 21 of Section 2.2 for the meaning of the $\exists!$ quantifier), i.e. $T\vDash\epsilon$ .

Here the idea is that we want to show that the original theory $T$ in the language $L$ is as powerful as the theory $T;\delta$ in the augmented language $L^{+}=L;f$ . In other words, definitions do not create additional knowledge.

The interpretation of $L^{+}$ into $T$ we consider is $\pi$ which is the identity interpretation for all parameters except $f$ , where $\pi_{f}=\phi$ . Then, $T\vDash\epsilon$ ensures that $\pi$ is indeed an interpretation. Moreover, for every model $\mathfrak{B}$ of $T$ , by definition, $^{\pi}\mathfrak{B}$ is the structure $\mathfrak{B};F$ of $T;\delta$ where for every $a\in|\mathfrak{B}|=|^{\pi}\mathfrak{B}|$ , $F(a)=b$ for the unique $b$ such that $\vDash_{\mathfrak{B}}\phi[[a,b]]$ .

Now, $\sigma\in\pi^{-1}[T]$ iff $\sigma$ is true in $^{\pi}\mathfrak{B}$ for every model $\mathfrak{B}$ of $T$ iff $\sigma$ is true in $\mathfrak{A}$ for every model $\mathfrak{A}$ of $T;\delta$ iff $\sigma\in\mbox{Cn}(T;\delta)=\mbox{Th}\mbox{Mod}(T;\delta)$ . Hence, $\pi$ is a faithful interpretation of $\mbox{Cn}(T;\delta)$ into $T$ .

Additionally, we can show that the definition is eliminable.

(a) $T;\delta\vDash(\sigma\leftrightarrow\sigma^{\pi})$ .

(b) $T;\delta\vDash\sigma$ iff $T\vDash\sigma^{\pi}$ .

Subpages

Section 2.7: Interpretations Between Theories

Section 2.7: Interpretations Between Theories

Notation

Interpretations of languages

Structures defined by interpretations

Syntactical translations

Interpretations of theories

Same language

ℨ and 𝔑

Defining Functions