# Section 2.7: Problem 2 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Let $L_{0}$ be the language with equality and the two-place function symbols $+$ and $\cdot$ . Let $L_{1}$ be the same, but with three-place predicate symbols for addition and multiplication. Let $\mathfrak{N}_{i}=(\mathbb{N};+,\cdot)$ be the structure for $L_{i}$ consisting of the natural numbers with addition and multiplication ($i=0,1$ ). Show that any relation definable by an $L_{0}$ -formula in $\mathfrak{N}_{0}$ is also definable by an $L_{1}$ -formula in $\mathfrak{N}_{1}$ .
Suppose an non-empty $n$ -place relation $R$ is definable by an $L_{0}$ -formula $\phi$ in $\mathfrak{N}_{0}$ (for the empty relation the conclusion is obvious). Consider $\pi$ from the set of parameters of $L_{0}$ into the set of formulas of $L_{1}$ such that $\pi_{\forall}=v_{1}=v_{1}$ , $\pi_{+}=+v_{1}v_{2}v_{3}$ and $\pi_{\cdot}=\cdot v_{1}v_{2}v_{3}$ . Since $\exists v_{1}v_{1}=v_{1}$ , $\forall v_{1}\forall v_{2}\exists x\forall v_{3}+v_{1}v_{2}v_{3}\leftrightarrow v_{3}=x$ , and $\forall v_{1}\forall v_{2}\exists x\forall v_{3}\cdot v_{1}v_{2}v_{3}\leftrightarrow v_{3}=x$ are true in $\mathfrak{N}_{1}$ , $\pi$ is an interpretation of $L_{0}$ into $\mbox{Th}\mathfrak{N}_{1}$ , and $\mathfrak{N}_{1}$ is a model of $\mbox{Th}\mathfrak{N}_{1}$ . Then, $|{}^{\pi}\mathfrak{N}_{1}|=\mathbb{N}$ , $a+^{^{\pi}\mathfrak{N}_{1}}b=c$ iff $+^{\mathfrak{N}_{1}}abc$ iff $a+b=c$ , and $a\cdot^{^{\pi}\mathfrak{N}_{1}}b=c$ iff $\cdot^{\mathfrak{N}_{1}}abc$ iff $a\cdot b=c$ , implying that $^{\pi}\mathfrak{N}_{1}=\mathfrak{N}_{0}$ . But then, for every $s:V\rightarrow\mathbb{N}$ , $\vDash_{\mathfrak{N}_{0}}\phi[s]$ iff $\vDash_{^{\pi}\mathfrak{N}_{1}}\phi[s]$ iff $\vDash_{\mathfrak{N}_{1}}\phi^{n}[s]$ (Lemma 27B), implying that $R$ is definable in $\mathfrak{N}_{1}$ by $\phi^{n}$ .