6
$\begingroup$

Hodges in his Shorter Model Theory promises to show "in what sense the finite linear orderings 'tend to' the rationals rather than, say, the ordering of the integers" (p. 160). After going through his proof of Fraissé's Theorem I did understand that there is a unique "Fraissé limit", but nonetheless I could not see that it is the ordering of the rationals instead of the integers.

Could anyone please help me to see why the Fraissé limit of the finite linear orderings is the ordering of the rationals?

$\endgroup$
1
  • $\begingroup$ The rationals obviously satisfy the extension property of Fraisse' limits. This, and the fact that they are countable, should be enough! $\endgroup$
    – damiano
    Aug 3, 2010 at 10:54

3 Answers 3

11
$\begingroup$

The reason that the finite linear orders don't tend to an order isomorphic to the integers is the following: Given a finite linear $A$ order with at least two elements, there are linear orders extending $A$ that have additional elements between two elements of $A$. This is (essentially) why the order that you get in the limit is dense rather than scattered as the integers.
Similarly, the limit won't have endpoints. And it will be countable. This implies that it is isomorphic to the rationals.

$\endgroup$
0
3
$\begingroup$

First, some books (maybe Hodge's, I don't have it right now) call the class of all finite structures embeddable in a structure, $\mathcal M,$ the Age of $\mathcal M.$ Sometimes this definition is changed to finitely generated rather than finite, like if say you wanted to talk about abelian groups. But, since your language is relational, that does not matter. Any Age satisfies some model theoretic properties, which are likely in Hodge's book, Hereditary and Joint Embedding (in fact Fraisse proved that these were necessary and sufficient conditions for being an Age). If the class you are considering is an Age and also has the amalgamation property, then it is true that there is a unique countable homogeneous model with that Age.

So, we should get back to your question. It is clear that the class of finite linear orderings has the amalgamation property. By the previous paragraph, you need only show that the rationals are a countable structure with the Age being the class of all finite linear orderings and that the rationals are homogeneous. So, the only potentially difficult thing is to prove homogeneity. To do this, you need only show that given a finite partial map $f: \mathbb Q \rightarrow \mathbb Q$ which respects the order can be extended to an isomorphism.

$\endgroup$
2
  • $\begingroup$ (Typo in the last line: "... given a finite partial map ...") $\endgroup$ Aug 3, 2010 at 18:34
  • $\begingroup$ Oh right, that should be a finite partial map... edited for the typo, thanks. $\endgroup$ Aug 4, 2010 at 7:31
0
$\begingroup$

$DLO$, the first order theory of dense linear ordering without endpoints, is $\omega$-categorical. So once you prove that the Fraisse limit, say $M_{0},$ of all finite linear ordering is a model of $DLO$, you already have proved that $M_{0}$ is isomorphic to$\langle\mathbb{Q},<\rangle,$ since $DLO$ is the same as $Th(\langle\mathbb{Q},<\rangle).$ This can be done using the universality and the homogeneity of the Fraisse limit.

The fact that $DLO=Th(\langle\mathbb{Q},<\rangle)$ is obtained using Vaught's test and the facts that $DLO$ has no finite models and is categorical in an infinite cardinal. The argument for the $\omega$-categoricity of $DLO$ is a back-and-forth argument on two countable models that is interesting for its part.

Also, to see more directly why the Fraissé limit of finite linear orders is the ordering of the rationals rather than that of the integers, note that the only difference between these orders is that the rationals are dense, i.e. for any two distinct elements of $\mathbb{Q}$ there is another element laying in between. To show that the order of that Fraissé limit is the ordering of the rationals you need to use the universality or richness of a Fraissé limit.

Supose that $F$ is the Fraissé limit of the class $\langle\mathcal{K},\subseteq\rangle$ in a language $\mathcal{L}$. $F$ is universal or rich in the following sense:

For any finite $A\subseteq F$ and any $B\in\mathcal{K}$ containing $A$ as a substructure, there is an $\mathcal{L}$-embedding (order-preserving in the case of linear orders) of $B$ into $F$ that extends the identity map over $A$.

Now, for given distinct elements in $F,$ say $a_{1}$ and $a_{2}$. w.l.g. we may assume that $a_{1}<a_{2}$ (we presumed we have proved that $F$ is linearly ordered). By taking $A:=\{a_{1},a_{2}\}$, there is a 3-element linear order containing $A$ with an extra element $b$ that lives in the class $\mathcal{K}$ and have the following order

$a_{1}<b<a_{2}.$

Now, using richness of $F$, there exists such element inside $F$. This proves that the limit $F$ is dense.

$\endgroup$

Your Answer

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

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