0
$\begingroup$

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 ?

$\endgroup$
7
  • $\begingroup$ Could you describe more precisely what the formula $\psi_n$ says? $\endgroup$
    – Dániel G.
    Commented Nov 26, 2016 at 19:36
  • $\begingroup$ I edited and clarified it. $\endgroup$
    – user343207
    Commented Nov 26, 2016 at 19:38
  • 1
    $\begingroup$ It seems to me that "$v$ is reachable from $w$" might be problematic - how do you express that? $\endgroup$
    – Dániel G.
    Commented Nov 26, 2016 at 19:39
  • $\begingroup$ ok, so lets drop it. $\phi_n: v$ is reachable from $w$ with using not less that $n$ edges. Or, better: $w,v$ are reachable each other with at least $n$ edges. $\endgroup$
    – user343207
    Commented Nov 26, 2016 at 19:42
  • 1
    $\begingroup$ Your $\phi_n$ doesn't exist. In fact, you can use the same argument as in your post to show this, with $\psi_k$ expressing the fact that there's no path of length $k$ between $v$ and $w$. Then for a fixed $n$ you could satisfy $\phi_n, \psi_1, ... , \psi_k$, for any $k$, but you can't satisfy all of them simultaneously. $\endgroup$
    – Dániel G.
    Commented Nov 26, 2016 at 19:57

1 Answer 1

1
$\begingroup$

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?

$\endgroup$
0

You must log in to answer this question.