MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

(This question has been unanswered at stackexchange for a long time.)

share|cite|improve this question
up vote 15 down vote accepted

Hi Martin.

I learned what follows in J.M. Plotkin, ed., Hausdorff on Ordered sets, AMS, History of Mathematics 25, 2005.

The result for countable ordered sets is due to Cantor. More precisely, Cantor produced continuum many countable order types:

Assign to each $x\in 2^\omega$ the type $x_0+(\omega^*+\omega)+x_1+(\omega^*+\omega)+x_2+\dots$

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, Untersuchungen aus der Mengenlehre. That there are at most continuum many types was also found independently by Hausdorff (June 27, 1901, according to his Nachlass, during a Summer course on Set theory at the University of Leipzig); it is referred to as the "Cantor-Bernstein theorem" in Hausdorff's Über eine gewisse Art geordneter Mengen, Gesellschaft der Wissenschaften zu Leipzig, Mathematisch-Physische Classe 53 (1901), 460-475. (See pg. 460)

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.)

Bernstein gives two proofs of the upper bound. The first goes by identifying an ordered set $M$ with a function $f:M^2\to\{-1,0,1\}$:

$f(a,b)=-1$ iff $a\lt b$, $f(a,b)=0$ iff $a=b$, and $f(a,b)=1$ iff $a\gt b$.

One then just has to count such functions for $M=\mathbb N$.

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$.

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$.

The lower bound is argued as follows: Given an infinite linearly ordered set $M$ of size $\mathfrak m=|M|$, call it graded 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$.

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.)

share|cite|improve this answer
Very nice and complete, thank you! – Goldstern Nov 3 '12 at 18:37

Your Answer


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.