Show that there is no formula of first-order logic which expresses "$(a, b)$ is in the transitive closure of $R$", even on finite structures.
I know how to prove the result for infinite structures using the compactness theorem. My idea for the finite case: use Ehrenfeucht-Fraisse games to show that for each $n \in \omega$ no formula of quantifier depth $n$ expresses transitive closure. Concretely, add constants $a, b$ to the language and find pairs of (finite) graphs $G_n^1, G_n^2$ such that
- $a$ is connected to $b$ in $G_n^1$.
- $a$ is not connected to $b$ in $G_n^2$.
- Player II (the duplicator) has a winning strategy in the EF-game $\mathcal{G}_n(G_n^1, G_n^2)$ of length $n$.
The problem is that I cannot find such graphs.