Let $\mathcal{L} := \{ R \}$ be a language with $R$ a binary relation. Let $T := \{ \forall x \forall y (x R y \to y R x) \}$ be the theory of undirected graphs in the language $\mathcal{L}$.
For $x, y$ we call a path of length $n$ a sequence $x = a_0, a_1, ..., a_n = y$ with $a_i R a_{i + 1}$ for $i = 0, ..., n-1$. A graph is called disconnected if there are $x, y$ such that there is no path of length $n$ between them for all $n \geq 1$. The diameter of a graph is the length of the longest shortest path between two vertices (or $\infty$ if the graph is disconnected).
The exercise now asks me to do the following:
For any theory $T' \supset T$ exactly one of the following cases holds:
- there is a model of $T'$ that is disconnected;
- there is an integer $N \geq 1$ such that all models $G$ of $T'$ are of diameter at most $N$.
It is easy to show that one of the two assertions excludes the other. But I have a bit of trouble to show that any theory must satisfy one of the cases.
My first idea was to find a set of formulas that describe disconnected graphs and then use the compactness theorem to prove that a model exists. But it seems rather unlikely to me that such a set of formulas exists.
My second idea was then to show that if 2. fails there is a graph of the form $0 < 1 < 2 < ... < -2 < - 1 $ (here the vertex set is $\mathbf{Z}$ and all negative integers are strictly greater than the nonnegative integers, while edges exist between successors). Such a graph could maybe extracted by taking vertices $a_n, b_n$ in a model of $T'$ such that the shortest path between them is of length $n$ and then find "limit vertices". But I'm not quite sure how to do that.
Can anyone help me on that?
Thanks!
Adjoin two new constant symbols $a$ and $b$ to the language, and consider the theory $T''$ consisting of your $T'$ plus, for each $n$, the sentence saying there's no path of length $n$ from $a$ to $b$. If this theory $T''$ has a model, then that's a disconnected model of $T'$, because $a$ and $b$ are in different components. If $T''$ has no model, then by compactness, there's $N$ such that $T'$ plus the additional axioms for $n\leq N$ has no model. In this case, all models of $T'$ have diameter at most $N$.