Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The question is: Which countable linear orders are $\aleph_0$-categorical?

I have a bit of progress on this:

Define a discrete tuple to be a set of elements, ordered discretely, such that if $a$ and $b$ are in the tuple, and $c$ is between $a$ and $b$ in the structure, then $c$ is part of the tuple.

Then if there are only finitely many discrete tuples (which may contain beginning or ending points of the structure), each of which has finite length, then it's fairly clear that the structure is $\aleph_0$-categorical (and finitely axiomatizable) with a back-and-forth argument.

If there is a discrete tuple of infinite length, then the structure is not $\aleph_0$-categorical, as there are infinitely many distinct formulas with two free variables (saying there are precisely $n$ elements between $x$ and $y$, for example, are all mutually exclusive and satisfied on the structure). More generally, if there are discrete tuples of arbitarily large finite length, it's still not $\aleph_0$-categorical.

I know there are models which fit neither characterization; for example $\mathbb{Q}\times 2$, with the dictionary ordering, has infinitely many discrete tuples, all with length 2. By a quick back-and-forth argument this is still $\aleph_0$-categorical, so the characterizations aren't inclusive enough.

share|improve this question
add comment

1 Answer

up vote 10 down vote accepted

In the paper below Rosenstein gives a complete characterization of $\aleph_0$-categorcial theories of linear order.

Rosenstein, Joseph G. $\aleph _0$-categoricity of linear orderings. Fund. Math. 64 1969 1–5.

You can also find the result, and many other gems, in Rosenstein majestic text on linear orders.

share|improve this answer
2  
Here is a link to the paper - matwbn.icm.edu.pl/ksiazki/fm/fm64/fm6411.pdf –  François G. Dorais Jun 12 '11 at 15:42
1  
If you read the paper and come to the place where Rosenstein defines "refinement" to be the converse of what it usually means, don't just assume it's a typo, interchanging $N$ and $N_1$. He really means the definition as he stated it. –  Andreas Blass Jun 12 '11 at 21:08
    
François and Andreas: thank you for your comments. –  Ali Enayat Jun 12 '11 at 21:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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