We say that a relationship $R$ has property $S$ when for $R \subset A \times A$ if for every $a \in A$ every path starts in $a$ has finite length.

Prove that it doesn't exist the such sentence $\phi$ in FO that $(A, E) \models \phi$ when $E$ has property $S$.

My solution:

Let assume that a such $\phi$ exists. Then, $\mathfrak{A} \models \neg \phi \iff $ there exists infinite path starts in $a$ for any $a \in A$. Therefore we can differ two graphs:

enter image description here

The first one is finite "line".

The second one is infinite long line.

We can prove that it is not possible to differ them with Ehrenfeucht's game.

For $k$-round game we take the first one graph and the second one of lenght $2^k+1$.


By Compactness theorem:

Let $\phi$ be an expected sentence. Let $\Delta = \{\phi \} \cup \Gamma$ . $\Gamma = \{e(c_i, c_{i+1} | i \in \mathbb{N}\} $ . Let's take finite $\Delta_0 \subset \Delta$. It is satisfable- it is easy to point a model: $M = (A, \Sigma, E), \Sigma = \{ e, c_1, c_2, ...\}, A = \{ v_1, v_2, ..\}$ where $A$ is set of vertexes, $c_i $ are constant where $c_i = v_i$. Just take a graph:

* * * * * * * 

And add to it edges by the following rule:

$e(v_i, v_j) \in E \iff e(c_i, c_j) \in \Delta_0$.

$\phi$ is satisfied because there is only finite number of edges so there exists only finite lenght path. $\Delta_0 \cap \Gamma$ is also satisfied- it is a result from a construction of graph.

By compactness theorem $\Delta$ is satisfable. Contradiction. $\phi $ ensures that threre is no infinite length while $\Gamma$ enforces path: $v_1 \to v_2 \to v_3 ...$.

So, I proved it by showing that this property isn't axiomatizable. So, especially it is not definable. But, I would like to see how to show this more directly- I mean the situation when any property is axiomatizable but not definable. ( Do you know a such example as exercise?).


Your EF-solution does not work: spoiler can win in two moves (HINT: pick an endpoint of the long-but-finite line).

Compactness is the way to go here. Suppose $\varphi$ is true of exactly the relations with property $S$. Now, you want to build a model of $\varphi$ with an infinite path - do you see how to do this? HINT: think about adding lots of new constant symbols $c_1, c_2, c_3, . . . $ and writing some sentences about them . . .

  • $\begingroup$ you obviously right. I edited. Now, I'll try to solve it using Compactness Theorem. $\endgroup$ – user376326 Feb 11 '17 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy