Past exam of the logic and set theory course of the University of Oxford / 2009 / B / 5 / vii / Solution

For the cardinality of total orders on a countably infinite set, a total order on $\mathbb{N}$ is a subset of $\mathbb{N}\times \mathbb{N}$, so there are at most $2^{{\aleph }_0}=\mathfrak{c}$ such orders. To obtain the lower bound, associate to every binary sequence $(b_n)$ an order by placing the two-element blocks $\{2n,2n+1\}$ in increasing order of $n$. Inside block $n$, use $2n<2n+1$ when $b_n=0$ and reverse them when $b_n=1$.

This is a total order for every sequence. Distinct sequences differ on the comparison of some adjacent pair and therefore produce distinct relations. Thus binary sequences inject into the order set, provingThe construction counts distinct orders on the labelled set, even though the resulting order types are all isomorphic to the usual natural-number order.