0
$\begingroup$

We conisder structure: $X=\langle A,\le\rangle$. Thinnish linear order is such order that for each $x,y$ that $x<y$ there exists only finitely many $z\in A$ such that $x<z<y$. Prove that there is no such set $\Delta$ of first order formulas that $\Delta\models X$ $\leftrightarrow X$ is thinnish linear order.

I should use here compacntess theorem.

When it comes to my approach I state that thinnish linear order is equivalent to directed chain (finite or infinite). It is because each linear order may be depicted as directed chain. Similarly, each thinnish linear order may be represented as directed chain.
So the problem is equivalent: prove that there is no $\Delta$ such that $\Delta\models G\leftrightarrow G$ is directed chain.

I am not sure If so far I have benn corrected. However, I try to show version with graph.

Lets assume that such $\Delta$ exists. Then, we extend our signature by constans $a,b$ representing nodes. Then we state:
$\phi_i:$ $a$ and $b$ are not reachable each other with $i$ edges(no matter direction).
Now, lets get $\Delta\cup\{\phi_i:i\in\mathbb{N}\}$. Let's consider finite arbritrary subset of this set. It is easy to see that it is satisfable, because in infinite chain we easily assign to $a,b$ nodes in such way that $a$ and $b$ are from each other farther than the selected set max $\phi$.

Thanks to compactness theorem we conclude that $\Delta\cup\{\phi_i:i\in\mathbb{N}\}$ is satisfable. However, it is not possible to interpret $a,b$ such that for each $\phi_i$ it will be satisfied.

What do you think about this solution ? Is it correct ? If not, how to solve it ?

$\endgroup$
4
$\begingroup$

I don't understand why you're passing to the language of graphs; it's much easier to argue directly as follows: suppose to the contrary that such a $\Delta$ exists, and consider the expansion of the language of linear orders by new constant symbols $d, e, c_1, c_2, c_3, . . . $. Look at the theory $\Gamma$ consisting of $\Delta$ together with $$\{d<e\}\cup\{d<c_i\wedge c_i<e: i\in\mathbb{N}\}\cup\{c_i<c_{i+1}: i\in\mathbb{N}\}.$$ $\Gamma$ is finitely satisfiable, so it has a model $N$. The reduct $N'$ of $N$ to the language of linear orders satisfies $\Delta$, so must be a thinnish linear order; but the elements of $N'$ corresponding to $d$ and $e$ have infinitely many points in between them.


If you do want to switch languages, you need to be much more careful: you need to argue explicitly that if $\Delta$ is a set of sentences in the language of linear orders which characterize thinnish linear orders, then we can get from $\Delta$ a new set $\Delta'$ of sentences in the language of graphs which characterizes the directed chains. Then, showing that no such $\Delta'$ exists finishes the problem.

The issue here is that this translation is far from obvious! How do I translate an arbitrary formula involving "$\le$" into one involving only the edge relation? The "natural" translation would be to replace each instance of "$\le$" with "is connected by finitely many edges," but the latter isn't first-order in the language of graphs!

To give a somewhat trivial, but hopefully illuminating, example of why we have to be careful with such translation issues: consider the language of linear order, versus the empty language. Now there is of course a sentence $\varphi$ in the language of linear order characterizing the dense linear orders. However, the underlying set of such a linear order must be infinite, and conversely every infinite set is the underlying set of a dense linear order - and there is no sentence in the empty language which is true in exactly the infinite sets! So looking at the latter language, we might incorrectly conclude that the sentence $\varphi$ can't exist.

Formally, what you have is a class of structures $\mathcal{A}$ (thinnish linear orders) which interprets a class of structures $\mathcal{B}$ (directed chains), and you know the latter is not an elementary class. However, this does not imply that the former is not an elementary class.

Indeed, in your case I don't immediately see a way to prove this translation result; your claimed solution is incomplete, and (unless I'm missing something) not easily fixable.

$\endgroup$
  • $\begingroup$ I write "$x<y$" as an abbreviation for the formula "$x\le y \wedge \neg y\le x$," by the way. $\endgroup$ – Noah Schweber Nov 19 '16 at 19:08
  • $\begingroup$ Thanks you very much! Keep in mind other my threads in logic ! $\endgroup$ – user343207 Nov 19 '16 at 21:07

Your Answer

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