There exists no zero-order or first-order theory for connected graphs

Question

Prove that no zero-order theory (i.e. propositional calculus, without quantification) or first-order theory can describe the "connected graph" (i.e. from any point one can reach each other point in finite steps).

The only weapon I know in these situations is the compactness theorem: so I would like to prove that

1) such a theory is satisfiable (obvious)

2) enlarged with some (possibly infinite) additional formulas, it is finitely satisfiable, hence satisfiable

3) these adjoint formulas, when satisfied, give a contradiction.

But I do not think that this way works, since, on the contrary, good connectedness properties increase (and don't decrease) if the graph is bigger, i.e. if one writes more points and arcs. So this doesn't seem, heuristically, a good way.

Can someone tell me about some other solutions or possible attempts?

Thank you in advance.

Answer 1

Assume you have a first-order theory $T$ in the language of graphs such that the models of $T$ are precisely the connected graphs. (The language of graphs has one two-place relation symbol $R,$ where $R(x,y)$ is intended to mean that there is an edge between node $x$ and node $y.)$

Add two new constant symbols $c$ and $d$ to the language.

For each natural number $n\ge 2,$ let $\psi_n(x,y)$ be the following formula with two free variables: $\lnot(\exists z_1)\dots(\exists z_n)\big( (z_1=x) \wedge (z_n=y) \wedge \bigwedge_{1\le k \lt n} (z_k\,R\,z_{k+1})\big).$

Let $T'$ be the theory $T\cup\{c\ne d\}\cup\{\psi_n(c,d) \mid n\ge 2\}.$

We can see that $T'$ is finitely satisfiable, as follows. If $\Sigma$ is any finite subset of $T',$ let $m$ be the least natural number greater than $0$ and greater than or equal to every $n$ for which $\psi_n\in\Sigma.$ Define a graph $H$ by specifying that $H$ has $m+1$ nodes, which we'll number from $0$ to $m,$ with an edge connecting node $k$ to node $k+1$ (for $0\le k \le m-1),$ and with no other edges. The constant symbol $c$ is interpreted as node $0,$ and the constant symbol $d$ is interpreted as node $m.$ $H$ is a connected graph, so it is a model of $T.$ Since $m+1\ge 2,$ $H\models c\ne d.$ Finally, every connected path from node $0$ to node $m$ has at least $m+1$ nodes in it (including the endpoints), so $H\models\psi_n$ for all $n\le m,$ and hence $H\models\psi_n$ for all $\psi_n\in\Sigma.$ It follows that $H$ is a model of $\Sigma.$

Since $T'$ is finitely satisfiable, compactness tells us that $T'$ is satisfiable. Let $G$ be a model of $T'.$ Since $T'$ contains $T,$ $G$ must be a connected graph. But the interpretations of $c$ and $d$ in $G$ cannot be connected by a path of any finite length $n,$ because $G$ satisfies $\psi_n.$