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