4

I tried to solve this exercises, proposed in 'A Mathematical Introduction to logic' by Enderton §2.7 exercises 1.

Assume that $L_0$ and $L_1$ are languages with the same parameters except that $L_0$ has an $n$-place function symbol $f$ not in $L_1$ and $L_1$ has an $(n+1)$-place predicate symbol $P$ not in $L_0$. Show that for any $L_0$-theory $T$ there is a faithful interpretation of $T$ into some $L_1$-theory.

But I can't solve this problem. Thanks to for any help.

Edited : I add a definition of faithful theory.

Let $T_0$ and $T_1$ are theories (in a possible different language) and $\pi$ is interpretation of $T_0$ into $T_1$ then $\pi$ is faithful iff $\pi$ satisfies $$\sigma\in T_0 \iff \sigma^\pi \in T_1$$ where $\sigma^\pi$ is formula interpreted by $\pi$.

Hanul Jeon
  • 27,376
  • Note that $n$-ary functions are $n+1$-ary predicates. – Asaf Karagila Jul 21 '13 at 12:28
  • 2
    I would like to suggest that you also write Enderton's definition of a faithful interpretation in your question. That might give a hint for how to proceed, and it would help people unfamiliar with the book. – Carl Mummert Jul 21 '13 at 12:32
  • @CarlMummert I added the definition of faithful interpretation. – Hanul Jeon Jul 21 '13 at 12:43
  • The interpretation $\pi$ is usually defined by recursion on formulas. The main issue will be how to interpret atomic formulas, because an atomic formula such as $f(f(x)) = y$ will not be in $L_1$. So the issue is how to replace that atomic formula with an equivalent one in $L_1$. – Carl Mummert Jul 21 '13 at 13:06

1 Answers1

1

Suppose $T$ is a $L_0$-theory. Now consider the interpretatio $\pi$ for $L_0$-formulas in $L_1$-formulas such that every occurrence of $f(\overline{x}) = y$ becomes $P(y, \overline{x})$. Furthermore, the following axiom would force $P$ to behave like a function: $$A := \forall \overline{w} (\exists z (P(z, \overline{w}) \land \forall y (P(y, \overline{w}) \rightarrow y = z)))$$ Then we consider the theory $T'=\{\varphi^\pi \mid \varphi \in T\} \cup \{A\}$. Naturally $\pi$ is an interpretation of $T$ in $T'$. We should only show that if $\varphi^\pi$ is a theorem of $T'$, then $T$ proves $\varphi$.

So suppose $T'\vdash \varphi^\pi$. Note that if you apply the inverse interpretation $\pi^{-1}$ in $A$, replacing $P(y, \overline{x})$ for $f(\overline{x}) = y$, you will obtain a theorem $A^{\pi^{-1}}$ of $T$. Thus, if you apply $\pi^{-1}$ to the formulas occurring in the proof $T'\vdash \varphi^\pi$, then this will be a proof in $T$ of $\varphi$. Therefore, $T \vdash \varphi$ as wanted.

Alfredo Roque Freire
  • 11