I am trying to understand why directed graph reachability cannot be expressed in first-order logic.
In Papadimitriou's "Computational Complexity" book this is proven by contradiction. Assume that there is a first-order formula $\phi(x,y)$ that does express reachability between two vertices $x$ and $y$ in a directed graph represented by binary edge relation $G$. Then consider the following formula $\psi$ built out of $\phi(x,y)$:
$$ \forall x \forall y \; \phi(x,y) \\ \wedge \forall x \; \exists z \; \Bigl(G(x,z) \wedge ( \forall w \; G(x,z) \wedge G(x,w) \Rightarrow z = w )\Bigr) \\ \wedge \forall x \; \exists z \; \Bigl(G(z,x) \wedge ( \forall w \; G(z,x) \wedge G(w,x) \Rightarrow z = w )\Bigr), $$
In English, this says that every vertex is reachable from every other vertex and each vertex has both indegree and outdegree 1.
Papadimitriou argues that every finite interpretation of $G$ making it a cycle is a model of $\psi$, because every vertex is reachable from every other, and indegrees and outdegrees are always 1. Because there are arbitrarily large cycles (each being a model of $\psi$), by the Löwenheim–Skolem theorem we can affirm that there is an infinite model for $\psi$ as well. However, this is a contradiction because there are no infinite cycles. Therefore, there can be no such formula $\phi(x,y)$.
Now, it seems to me we can express graph reachability with first-order logic by writing the theory
$$R(x,y) \Leftrightarrow G(x,y) \vee \exists z \; G(x,z) \wedge R(z,y).$$
How can we reconcile this with Papadimitriou's proof?
PS: answer by Reese below shows that the above definition is not correct. However, it seems to me that Papadimitriou's definition of "cannot defined in first-order logic" as "there is no formula $\phi(x,y)$" is too restrictive, because it seems that in principle we could define concepts in FOL using a circularly-defined predicate like that, or at least we would need to prove that no circular definitions will work either.
This can be reconciled by noting that the theory using $R$ is not providing a formula $\phi(x,y)$ as requested by Papadimitriou.
What are the options for using this theory and providing $\phi(x,y)$? We could make $\phi(x,y)$ be $R(x,y)$, but then we would not be providing $R$'s definition. We cannot define $\phi(x,y)$ to be the circularly-defined $G(x,y) \vee \exists z \; G(x,z) \wedge \phi(z,y)$, either.
Ultimately, the paradox can be clarified by noting that Papadimitriou's definition of the phrase "expressing graph reachability with first-order logic" is a narrower one than a definition that allows the use of a first-order theory to do so.