Relation $E\subseteq A\times A$ has a property: for each $a\in A$ each path starting in $a$ is finite length. Prove that there is not exist sentence in first-order logic $\phi$ such that $(A,E)\models \phi$ if only and only $E$ has mentioned above property.
My trial:
Let suppose that such $\phi$ exists. Then lets extends language by two constants: $v,w$ and our formula:
$\phi'=\phi\wedge \psi_n$, where $\psi_n$ asserts that $v,w$ are reachable with using at least $n$ edges, $n\in\mathbb{N}$.
$\phi_n$ : it is not possible to reach $w$ from $v$ using less than $n$ edges, but $v$ is reachable from $w$.
Of course each finite subset of $\phi'$ is satisfable - for example by respectively long chain. However, it is contradiction with compactness theorem - it is not possible that $\phi'$ is satisfable - we won't manage to assign nodes to $v,w$ - after all, each path must be finite.
Tell me please, Is it ok ? Maybe there exists other solution ? Some game ?
Well, "is reachable from" isn't expressible in first-order logic. This is an easy consequence of the compactness theorem, and a good exercise.
So what can you do? Well, think about what you want: given a sentence $\varphi$ which is true in every graph with your property (which I'll call "$(*)$"), you want to find a graph $G$ in which $\varphi$ is true but $(*)$ fails. And, of course, we'll use the compactness theorem to do this.
Well, we want $G$ to have an infinite path. This means that we want $G$ to have a sequence of vertices $a_1, a_2, a_3, . . .$ such that
$a_1Ea_2,$
$a_2Ea_3$,
$a_3Ea_4$,
etc.
Do you see how to get such a $G$, via the Compactness theorem? HINT: what's a natural way to expand the language to describe an infinite path?