« 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 $\forall$ , $P$ , $c$ , and $d$ , where $P$ is a two-place predicate symbol and $c$ and $d$ are constant symbols. Show that there is no set $\Sigma$ of sentences with the property that a structure $\mathfrak{A}$ is a model of $\Sigma$ iff the pair $$ belongs to the transitive closure of the relation $P^{\mathfrak{A}}$ . Suggestion: Consider the set consisting of $\Sigma$ together with sentences saying that there is no short $P$ -path from $c$ to $d$ .
This problem is similar to Exercise 8. The difference is that in that exercise we considered a particular structure $\mathfrak{A}$ , while here we specify a criterion for $\mathfrak{A}$ to be a model of some set of sentences $\Sigma$ .
Suppose such $\Sigma$ exists. For each $n$ , consider a sentence $\tau_{n}$ which is $\tau_{n}$ says that there is no path from $c^{\mathfrak{A}}$ to $d^{\mathfrak{A}}$ of length $n$ or less. Then, as in Exercise 8, $\mathfrak{A}_{ij}$ is a model of $\tau_{n}$ iff $|i-j|>n$ . Moreover, in $\mathfrak{A}_{ij}$ , $$ belongs to the transitive closure of the relation $P^{\mathfrak{A}_{ij}}$ . Therefore, $\mathfrak{A}_{ij}$ is a model of $\Sigma$ . This implies, that there is a model for every finite subset of $\overline{\Sigma}=\Sigma\cup\{\tau_{n}\}_{n\in\mathbb{N}}$ , and, hence, by the compactness theorem, there is a model $\mathfrak{B}$ of $\overline{\Sigma}$ , and, hence, $\Sigma$ . But in this model there is no finite path from to $d^{\mathfrak{B}}$ , i.e. $$ does not belong to the transitive closure of the relation $P^{\mathfrak{B}}$ . The contradiction shows that there is no such $\Sigma$ .