I'm wondering why we can't express graph reachability in first order logic in pretty much exactly the same way we express it in second order existential logic. For SOL, one definition is :

1 . L is a linear order on a subset of the vertices : 

$$\begin{align} \psi\_1 = &\forall u \neg L(u,u) \\
 &\wedge \forall u\forall v (L(u,v) \Rightarrow \neg L(v,u)) \\
 & \wedge \forall u\forall v \forall w(L(u,v) \wedge L(v,w) \Rightarrow L(u,w)) 
\end{align} $$

2 . Any two consecutive vertices in the order must be joined by an edge in G:

$$\begin{align} \psi\_2 = &\forall u\forall v ((L(u,v) \ \wedge \forall w(\neg L(u,w) \vee \neg L(w,v))) \\
& \Rightarrow E(u,v)).
\end{align} $$

3 . The first vertex in the order is x and the last is y *and* x, y are in the order:

$$\begin{align} \psi\_3 = &(\forall u\ \neg L(u,x)) \wedge (\forall v\ \neg L(y,v)) \ \wedge L(x,y)
\end{align} $$

and finally the expression for reachability is 

4 . $\phi(x,y) =\exists L (x=y) \vee (\psi\_1 \wedge \psi\_2 \wedge \psi\_3))$

But why can't we use the same thing in *first order logic* (i.e. no existential quantification over L) :

$\phi(x,y) =(x=y) \vee (\psi\_1 \wedge \psi\_2 \wedge \psi\_3))$

This would be interpreted over the vocabulary with models M having two binary relations : E (edge) and L (reachable), and the universe of all nodes. Surely any model which satisfies the expression 5 above will have its L relation expressing a linear ordering of the nodes, with any two consecutive elements being adjacent in E - in other words, it will be the "Reachable" relation, (and the model will map the free variables x and y to nodes N1 and N2, with (N1,N2) in L, meaning N2 is reachable from N1).

Why doesn't this work? Specifically, would the proof of non expressibility of reachability fail for it?

The proof of non expressibility of reachability in FOL goes like this : 

---

Assume that an FOL expression p, with free variables x and y exists, expressing reachability.

We have $s\_1 \equiv \forall x \forall y \ p$ stating that all nodes are reachable from all nodes, i.e. the graph is strongly connected. 

Then we add two sentences about E, $s\_2$ (saying that every node of the graph has outdegree one), and $s\_3$ (that every node has indegree one). The conjunction of the above three sentences 

$s\_4 = s\_1 \wedge \ s\_2 \wedge \ s\_3$,

then states that the graph is strongly connected and all nodes have indegree and outdegree one - i.e. it's a cycle.

Since there are finite cycles with as many nodes as desired, s4 has arbitrary large finite models. Therefore by Lowenheim-Skolem theorem, it also has an infinite model. But infinite cycles do not exist, and so our assumption that there exists a p expressing reachability is contradicted.

---

If our FOL expression (5) is taken as the p expression in the proof, all the steps of the proof can be carried out the same, and we will be led to the same result, namely that (5) does not express reachability. But why not? It certainly has all the elements..