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.