"A symmetric graph is connected" is not first-order axiomatizable

Question

For the first-order language with vocabulary $(E)$ (the binary relation $E$ which holds if two vertices have an edge) together with a set $G$ of vertices, I've been told that the property "a symmetric graph is connected" cannot be axiomatized by any set of first-order sentences.

I think the proof involved taking two constants, let's say $x,y \in G $ and building an infinite set of sentences $T$ that states "there is no path of length $n$ between $x$ and $y$" for each $n$ (where a path is, for some vertices $(v_1,...,v_n) \in G$, $[E(x, v_1) \wedge ... \wedge E(v_n, y)]$). By compactness, I see that $T$ is satisfiable. However, I don't see how $T$ shows the impossibility of constructing another set of sentences $T'$ which is satisfied by connected graphs.

I do understand the use of compactness to show that a theory whose models have arbitrarily large domains also has a model with an infinite domain, but I don't understand its use here. I don't have any experience with ultraproducts, so answers using that concept may be lost on me.

Answer 1

Your description of $T$ is not complete; here's what it should be. Suppose there exists a first order axiomatization $T_0$ of connected graphs. Now let $T$ be the union of $T_0$ and your sentences "there is no path of length $n$ between $x$ and $y$" for each $n$. Any finite subset of this $T$ has a model, since you can find a connected graph with points $x$ and $y$ satisfying any finite subset of your sentences. Therefore $T$ is satisfiable. A model of $T$ is then a connected graph (because it satisfies $T_0$) with elements $x$ and $y$ with no path of any length between them. This is a contradiction. Therefore the set $T_0$ cannot exist, and there is no first order axiomatization of connected graphs.

Answer 2

Suppose out language is $(V,E,a,b)$ where $V$ is the set of vertices; $E(\cdot,\cdot)$ is the edge relation, and $a$ and $b$ are distinct constants.

Let each $T_n$ encode "There is no path of length $n$ between $a$ and $b$"

And suppose conversely there is a sentence $T$ that encodes "The graph is connected".

Consider the set of sentences $T,T_1,T_2,\ldots$ . It's an exercise to show every finite subset is modeled by some finite graph with some large number of edges that are arranged along a straight line. The bigger you make your finite subset the bigger the graph needs to be. But that's okay for the hypotheses of the compactness theorem.

By compactness there is a model $\mathcal M$ for the entire set of sentences $T,T_1,T_2,\ldots$ . That model is a connected graph with the property for each $n$ that "There is no path of length $n$ between $a$ and $b$". Contradiction.