Consider a signature containing only a two—place predicate equality symbol and a two-place predicate symbol R, interpretations are sets with binary relations (oriented graphs). Is it possible to express the following graph properties/relations with first-order formulas: acyclicity; connectivity?
I would like to use formulas of countable power to prove both facts like: $\land\exists x_1, ... , x_n \forall x \forall y (R(x,x_1)\land R(x_1, x_2)\land ... \land R(x_n,y))$ for connectivity and similar for acyclicity but is that correct?
I realized that this is an incorrect formula and now I don't know what to do
Acyclicity is not expressible with just one formula, but is expressible with countably infinitely many formulas. More precisely, for all $n$, “There is no cycle of length $n$“ is clearly expressible as a first-order sentence.
Conversely, a standard compactness theorem argument will show that connectivity is not a first-order property. For suppose we have a set $S$ of first-order sentences equivalent to connectivity. Add constant terms $a, b$ and, for each $i$, the axiom $\phi_i$ = “There is no path of length $i$ from $a$ to $b$”, and apply compactness in the obvious way to get a contradiction.