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.


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.

  • 2
    $\begingroup$ Here is a link to the paper - matwbn.icm.edu.pl/ksiazki/fm/fm64/fm6411.pdf $\endgroup$ – François G. Dorais Jun 12 '11 at 15:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Andreas Blass Jun 12 '11 at 21:08
  • $\begingroup$ François and Andreas: thank you for your comments. $\endgroup$ – Ali Enayat Jun 12 '11 at 21:22

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.