Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Note that $n$-ary functions are $n+1$-ary predicates. – Asaf Karagila Jul 21 '13 at 12:28
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.