# Section 2.7: Problem 1 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

Assume that
and
are languages with the same parameters except that
has an
-place function symbol
not in
and
has an
-place predicate symbol
not in
. Show that for any
-theory
there is a faithful interpretation of
into some
-theory.

We will use the following fact:
, by definition, is
, which is translated to
, and, by definition, the latter is just
.

First, we define a function
from the set of parameters of
into the set of formulas of
. For every parameter except
, let
be the identity interpretation (
itself is not an interpretation, as no theory in
was defined so far, but we can still use the definition of the identity interpretation to define the function
). Now, we define
.

Second, given
, for every formula
of
, we can define
as before (the definition of
does not depend on the theory in
).

Finally, we define a set
of formulas of
as follows,
where
. In other words,
contains all interpretations of the sentences of
, plus a sentence
that ensures that
defines a function on the universe defined by
with the range in the universe. A few words why we need to add this additional sentence. The way we define translations of wffs containing function symbols is such they do not ensure the existence of any value of the function, but only says something about the value if it exists. For example, even a sentence something like
is translated to
, which is literally translated as “for every
in the universe there is
in the universe such that for every

*if*is a value of the function then ”, not ensuring the existence at all. So, we need to add explicitly. Now, it can be shown by the definition, that if is a sentence of , then is a sentence of . Hence, consists of sentences.
is not a theory. Indeed, if
were a theory, then
would be equal to
(see Exercise 3 of Section 2.6). At the same time, the latter contains all valid sentences, some of which, such as
, are neither translations of any sentences of
nor
. So, we need to consider a larger set of formulas of
, namely,
.
is a theory. We show that
is an interpretation of
into
. For all parameters of
except for
, the definition of
as the identity interpretation ensures that equations (i) and (ii) hold, see pages 167-168. For example,
, which is
, is valid, and, hence, is in
. Now, for
,
is exactly the sentence that ensures the correct definition of the interpretation.

iff
iff
. As we said,
is not a theory, otherwise we would conclude “iff
iff
, as
is not a translation”. However, we already know that if
, then
,
, and
, implying that
, and
is an interpretation of
into
. To show that it is faithful, we need to show the opposite inclusion, i.e.
, which holds iff
implies
(that is the “theory” property holds for translations), or, equivalently,
.

If
is inconsistent, then, obviously,
holds. So, assume
is consistent. Then,
is consistent as well. Indeed, if
is a model of
, then we can consider a structure
in
which agrees with
on all parameters except that instead of
we have
defined as
iff
. Then, all parameters of
agree with those of
, except for
which needs additional verification.
iff
iff
iff
, i.e.
agrees with
as well. In other words,
, and for every
,
is true in
, implying that
is true in
. Further,
is true in
as well (this follows from the fact that
is defined via a function). Therefore,
is a model of
.

Now, suppose
. Then,
, and
is consistent. Then,
is consistent, implying that
, and, by the above argument,
. The contraposition of this is that, if
then
, exactly what we need.