I am asked to solve the following excercise:
- Show that the theory of acyclic graphs is axiomatizable at the first order.
- Call a graph connected if any two vertexes are connected are linked by a finite path. Show that the theory of connected graphs is not axiomatizable at the first order.
So, I fix a first order language $\mathscr{L}=\{E\}$.
For the first point I simply thought to exploit an infinite axiom schema:
$\lnot Ax(n)\; n\in\omega$="there does not exist a closed path of length n" which I would formalize with
$Ax(n)=\exists x_1\exists x_2...\exists x_n(\bigwedge_{i,j=1}^{n-1}\lnot(x_i=x_j)\wedge (x_n=x_1)\wedge (x_iEx_{i+1}))$
Is this correct?
I am a bit clueless about the second point. I understand that we should add two logical constants, ro be interpreted in $v_1,v_2$ and an infinite axiom schema assuring this two vertexes are distinct and not linked by a finite path, but I cannot find such a system of axioms.
Thanks in advance for help.
You first point is correct. For the second point, you need to use compactness theorem.
Assume for contradiction that there's a theory $T$ whose models are precisely the connected graphs. Then, for each $n$, the graph $G_n$ with vertices $\{v_1,\dots,v_n\}$ and edges $\{(v_i,v_{i+1}) \big| 1\leqslant i < n\}$ is a model of $T$.
Now add two constant symbols $b$ and $c$ to your language : $\mathscr{L}':=\{E,b,c\}$. For each $n>2$, interpret $b$ by $v_1$ and $c$ by $v_n$ in $G_n$. Then $$G_n \models (b \neq c)\wedge \neg E(b,c) \wedge \bigwedge_{k < n-2} \Big(\underbrace{\neg \exists x_2,\dots x_{k+1} \big(E(b,x_2) \wedge \bigwedge_{i=2}^{k}E(x_i,x_{i+1})\wedge E(x_{k+1},c)}_{=:\varphi_k}\big) \ \Big)$$
In an ultraproduct $G$ of the $G_n$s by a non trivial ultrafilter of subsets of $\mathbb{N}\setminus \{0,1,2\}$, you get $G\models T$, but $b$ and $c$ are not connected since for every $n$, you have $G\models (b \neq c)\wedge \neg E(b,c) \wedge \varphi_n$.
That's a contradiction : no such $T$ exists.