The issue here is with the terminology. You can express reachability in first-order logic; for example you can express it in the language of set theory by quantifying over paths in the graph, and set theory is a first-order theory.
You cannot express reachability in the particular language where the only relations available are the incidence relation on the graph and equality, and where quantification is only permitted over elements of the graph. So the issue actually has very little to do with "first order logic", and everything to do with the particular language that is being allowed. Tradition says that this situation is phrased as "reachability cannot be expressed in first order logic", even though that phrase could be interpreted in other ways.
Ignoring terminological issues, it can be genuinely useful to know that reachability cannot be expressed without quantifying over sets or paths in some way. For example, that fact means that if your graph is stored in an SQL database in a natural way then it will be more difficult to code an SQL query that tells whether an arbitrary pair of nodes has a path than it would be if that relation could be phrased in the limited language mentioned above.
By the way,here is how you show there is no formula $\phi(a,b)$ expressing reachability. Take the language of graph theory mentioned above and add two new constants $C$ and $D$. Take the infinite set of axioms "there is no path of length $1$ from $C$ to $D$", "there is no path of length two from $C$ to $D$", ... Then any finite set of these axioms is consistent with $\phi(a,b)$, as can be seen by looking at a graph with an infinitely long path and taking $C$ and $D$ to be far enough apart. Thus by the compactness theorem the set of all those axioms is consistent with $\phi(C,D)$. But if all those axioms are true in a graph, there is no path from $C$ to $D$ in that graph, so $\phi$ did not express that property correctly.
First, you mention "infinite cycles". Let's agree that a cycle in a graph is a path which starts and ends at a vertex $v$ and otherwise does not visit any vertex more than once. By this definition, every cycle is finite, since an infinite path fails to have a starting point or fails to have an ending point or both.
Your sentence $\phi(n)$ almost expresses "there exists a cycle of length $n+2$". I say almost because you've forgotten to require that $v_1$ and $v_2$ are distinct from the $p_i$ as well. So for example the graph $$a\sim b\sim c$$ satisfies $\varphi(2)$, setting $v_1 = a$, $v_2 = b$, $p_1 = b$, $p_2 = c$. But this graph does not have a cycle (of any length).
Ok, let's say we've fixed this problem, and now we have a family of sentences $\phi(n)$ where $\phi(n)$ expresses "there exists a cycle of length $n+2$". Now we want to axiomatize the acyclic graphs. Your theory $$T = \{\varphi(n)\mid n>0\}\cup \text{Graph Axioms}$$
axiomatizes the class of graphs which do contain a cycle of every possible length. Do you see what you need to do to fix this axiomatization?
Once you've fixed that problem, you'll be convinced it's possible to axiomatize the class of acyclic graphs. But you've asked about finite acyclic graphs.
The class of finite ayclic graphs is not elementary. Usually, if you want to show that some class is not elementary, you use the compactness theorem. Let $\psi_n$ be the sentence asserting "there are at least $n$ distinct elements". Suppose for contradiction that there was some theory $T$ axiomatizing the finite acyclic graphs. Consider $T' = T \cup \{\psi_n\mid n\in \mathbb{N}\}$. By compactness, $T'$ is consistent: if $\Delta \subseteq T'$ is a finite subset, let $N$ be maximum such that $\psi_n\in \Delta$. Then any finite acyclic graph of size greater than $N$ is a model of $\Delta$ (for example, take a large graph with no edges). So $T'$ has a model $M$. But then $M\models T$ is a finite acyclic graph, but $M\models \psi_n$ for all $n$, so $M$ is infinite. Contradiction.
The exact same argument shows that if $K$ is any class of finite structures containing arbitrarily large finite structures, $K$ is not elementary. So usually, you cannot axiomatize the class of "finite X".
The exercise in Marker you refer to asks you to show that the class of trees is elementary. Unfortunately, there are many definitions of "tree" in mathematics. I think the definition that Marker has in mind is the one from order theory: a tree is a partially ordered set $T$ with a minimal element such that for each element $v\in T$, the set of predecessors of $v$, ${\downarrow}v = \{u\in T\mid u\leq v\}$, is linearly ordered.
Here are some other common definitions of "tree" which are not elementary (and it's a good exercise to try to prove this in each case by compactness):
- A tree is a connected acyclic graph.
- A tree is a partially ordered set with a minimal element, such that for each element, the set of predecessors of that element is well-ordered.
- A tree is a directed graph with a specified vertex (the root), such that each vertex other than the root has exactly one outgoing edge, and the path formed by following these outgoing edges from each vertex eventually leads to the root.
You can find lots of relevant questions on this site by searching for "not elementary" or "not axiomatizable".
Best Answer
Finite directed cycle
Your attempt is wrong. In short, your attempt is "$\forall x,y\ ( E(x,y) \to \neg E(y,x) ) \land \forall x\ \exists! y\ ( E(x,y) )$", which asserts "for every (directed) edge there is no backward edge, and for every vertex there is a unique outgoing edge". The second part does force the graph to have an infinite chain, because it ensures that you can keep stepping to the (unique) next vertex. But nothing forces that chain to loop back on itself.
Have you considered that it is impossible? If not, you may want to think about it before looking below.
Finite X
In general, even if one uses infinitely many sentences, one cannot force the structure to be finite if one must accept arbitrarily large instances and there is no global constraint, roughly speaking. In the case of graphs, all you can express are local constraints, namely the edges. So if there is a set $S$ of axioms that are satisfied by only cycles of all finite sizes, then you can construct a separate set $T$ of sentences, one for each natural $k$ that asserts "there is a chain with at least $k$ distinct vertices". Then there is a structure that satisfies any finite subset of $S \cup T$ (prove it yourself), and hence by compactness there is a structure that satisfies $S \cup T$. But any such structure must be a finite cycle (by definition of $S$) and hence cannot satisfy $T$; contradiction. Therefore such $S$ does not exist.