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