Number of linear orders - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T11:16:58Z http://mathoverflow.net/feeds/question/111283 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111283/number-of-linear-orders Number of linear orders Goldstern 2012-11-02T15:24:38Z 2012-11-03T20:49:31Z <p>It is well known that for every infinite cardinal $\kappa$ the number of non-isomorphic total orders of cardinality $\kappa$ is $2^\kappa$. Who first proved this, and in what context? Was it proved for $\kappa=\aleph_0$ first, and then for uncountable $\kappa$, or for all $\kappa$ right away? </p> <p>(This question has been unanswered at <a href="http://math.stackexchange.com/questions/111225" rel="nofollow">stackexchange</a> for a long time.) </p> http://mathoverflow.net/questions/111283/number-of-linear-orders/111286#111286 Answer by Andres Caicedo for Number of linear orders Andres Caicedo 2012-11-02T16:22:15Z 2012-11-03T20:49:31Z <p>Hi Martin. </p> <p>I learned what follows in J.M. Plotkin, ed., <strong>Hausdorff on Ordered sets</strong>, AMS, History of Mathematics <strong>25</strong>, 2005.</p> <p>The result for countable ordered sets is due to Cantor. More precisely, Cantor produced continuum many countable order types: </p> <blockquote> <p>Assign to each $x\in 2^\omega$ the type $x_0+(\omega^*+\omega)+x_1+(\omega^*+\omega)+x_2+\dots$ </p> </blockquote> <p>Bernstein proved (by March, 1901 or earlier) that there can be no more than continuum many. The result (both parts) appears in his 1901 dissertation, <em>Untersuchungen aus der Mengenlehre</em>. That there are at most continuum many types was also found independently by Hausdorff (June 27, 1901, according to his <em>Nachlass</em>, during a Summer course on Set theory at the University of Leipzig); it is referred to as the "Cantor-Bernstein theorem" in Hausdorff's <em>Über eine gewisse Art geordneter Mengen</em>, Gesellschaft der Wissenschaften zu Leipzig, Mathematisch-Physische Classe <strong>53</strong> (1901), 460-475. (See pg. 460) </p> <p>It is probably worth remarking that this shows Bernstein's and Hausdorff's comfort with using choice in their arguments from the beginning, as clearly this gives us a "natural" example showing that $\omega_1\le 2^{\aleph_0}$. (On the other hand, Hausdorff remains unsure at this time on whether $\mathbb R$ can be well-ordered.)</p> <p>Bernstein gives two proofs of the upper bound. The first goes by identifying an ordered set $M$ with a function <code>$f:M^2\to\{-1,0,1\}$</code>: </p> <blockquote> <p>$f(a,b)=-1$ iff $a\lt b$, $f(a,b)=0$ iff $a=b$, and $f(a,b)=1$ iff $a\gt b$. </p> </blockquote> <p>One then just has to count such functions for $M=\mathbb N$. </p> <p>The second proof uses Cantor's result that $\mathbb Q$ is universal for countable linear orders, so one only has to count subsets of $\mathbb Q$.</p> <hr> <p>The general result is due to Hausdorff, in his 1901 paper, with the published upper bound the same argument as Bernstein's first proof. (There seem to be no records of Hausdorff's original argument, or of whether it was different.) He doesn't quite use that $M$ is well-orderable, but rather that $\mathfrak m=|M|$ satisfies $\mathfrak m^2=\mathfrak m$. </p> <p>The lower bound is argued as follows: Given an infinite linearly ordered set $M$ of size $\mathfrak m=|M|$, call it <em>graded</em> iff no two distinct initial segments of $M$ are order isomorphic. Assume $M$ admits a graded ordering (which is clearly the case if $\mathfrak m$ is an aleph). For $m\in M$, denote by $A_m$ the set of predecessors of $m$. </p> <p>Given a set $S\subseteq M$ of size $\mathfrak m$, assign to it the ordered sum $L_S$ of the sets $\mathbb Q+A_s$, $s\in S$, and note that if $S\ne S'$ then $L_S$ and $L_{S'}$ are not order isomorphic. The result follows if $[\mathfrak m]^{\mathfrak m}=2^{\mathfrak m}$ which, again, holds if $\mathfrak m$ is an aleph. (Plotkin remarks that Hausdorff could have elaborated a bit more on why the sets $L_S$ are not isomorphic.) </p>