« Section 2.5: Problem 9 Solution

Section 2.5: Problem 10-A 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
(Additional) Assume the language (with equality) has just the parameters , , , and , where is a two-place predicate symbol and and are constant symbols. Show that there is no set of sentences with the property that a structure is a model of iff the pair belongs to the transitive closure of the relation . Suggestion: Consider the set consisting of together with sentences saying that there is no short -path from to .
This problem is similar to Exercise 8. The difference is that in that exercise we considered a particular structure , while here we specify a criterion for to be a model of some set of sentences .
Suppose such exists. For each , consider a sentence which is says that there is no path from to of length or less. Then, as in Exercise 8, is a model of iff . Moreover, in , belongs to the transitive closure of the relation . Therefore, is a model of . This implies, that there is a model for every finite subset of , and, hence, by the compactness theorem, there is a model of , and, hence, . But in this model there is no finite path from to , i.e. does not belong to the transitive closure of the relation . The contradiction shows that there is no such .