# Relationship with special property.

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:

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$.

Right?

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?).

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 . . .