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 be the language with equality and the two-place function symbols and . Let be the same, but with three-place predicate symbols for addition and multiplication. Let be the structure for consisting of the natural numbers with addition and multiplication ( ). Show that any relation definable by an -formula in is also definable by an -formula in .
Suppose an non-empty -place relation is definable by an -formula in (for the empty relation the conclusion is obvious). Consider from the set of parameters of into the set of formulas of such that , and . Since , , and are true in , is an interpretation of into , and is a model of . Then, , iff iff , and iff iff , implying that . But then, for every , iff iff (Lemma 27B), implying that is definable in by .