2
$\begingroup$

It's known that the class of well-founded linear orders is not axiomatizable in FO logic. But I can't understand the relation between the aforesaid argument and the compactness theorem.

Let $\mathcal{A}$ be a well-founded linear order (which means it contains no infinite descending chain for $a_1, a_2, ...$ such that $... <^{\mathcal{A}} a_3<^{\mathcal{A}} a_2<^{\mathcal{A}} a_1$). To show the truthfulness of the stated argument, one can say that there is no set of sentences like $\Sigma$ such that:

$\mathcal{A} \models \Sigma \Leftrightarrow \mathcal{A}$ is well-founded.

How can one use compactness theorem for this case? Any reference will be welcome.

$\endgroup$

1 Answer 1

3
$\begingroup$

You just add to $\Sigma$ the assertions $c_{n+1}<c_n$, where these are new constant symbols. Any finite collection of the resulting theory is consistent, since there are well-orders with a finite descending sequence of any particular finite length, but there can be no well-order realizing all of these statements. So this would violate the compactness theorem if $\Sigma$ were true in all and only the well orders.

$\endgroup$
2
  • $\begingroup$ but there can be no well-order realizing all of these statements. Could you explain a little bit about this part of the answer? I mean, how can we claim that there is no such realization? $\endgroup$
    – User
    Mar 23, 2017 at 1:31
  • $\begingroup$ The new theory explicitly asserts that there is an infinite descending sequence, namely, the sequence $c_0>c_1>c_2$ and so on, and so any model of that theory is definitely not a well order. $\endgroup$ Mar 23, 2017 at 1:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.