Which countable linear orders are $\aleph_0$-categorical? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T09:53:04Z http://mathoverflow.net/feeds/question/67581 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/67581/which-countable-linear-orders-are-aleph-0-categorical Which countable linear orders are $\aleph_0$-categorical? Richard Rast 2011-06-12T14:19:30Z 2011-06-12T15:05:23Z <p>The question is: Which countable linear orders are $\aleph_0$-categorical?</p> <p>I have a bit of progress on this:</p> <p>Define a <i>discrete tuple</i> 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.</p> <p>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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/67581/which-countable-linear-orders-are-aleph-0-categorical/67584#67584 Answer by Ali Enayat for Which countable linear orders are $\aleph_0$-categorical? Ali Enayat 2011-06-12T14:53:35Z 2011-06-12T15:05:23Z <p>In the paper below Rosenstein gives a <em>complete characterization</em> of $\aleph_0$-categorcial theories of linear order.</p> <p>Rosenstein, Joseph G. $\aleph _0$-categoricity of linear orderings. Fund. Math. 64 1969 1–5. </p> <p>You can also find the result, and many other gems, in Rosenstein majestic <a href="http://books.google.com/books?id=y3YpdW-sbFsC&amp;printsec=frontcover&amp;source=gbs_ge_summary_r&amp;cad=0#v=onepage&amp;q&amp;f=false" rel="nofollow">text on linear orders</a>.</p>