how many linear orderings on $\omega$ the are and how can we identify when 2 of them are in fact isomorphic.

Question

how many linear orderings on $\omega$ the are and how can we identify when 2 of them are in fact isomorphic. I think that by instability argument there are $2^{\aleph_0}$ of them, but I do not know when exactly 2 of them are in fact isomorphic. So the first order logic language is $(\omega,<)$ or $(\omega,<,S,0)$. I do not know which one is a better language.

Answer 1

The standard trick is to encode a set of size $2^{\aleph_0}$ as provably non-isomorphic linear orders.

Here, we will use $\mathcal P(\mathbb N).$

Let $S\subseteq \mathbb N.$

Define: $$P_{S}=\{(n,m)\in\mathbb N\times\mathbb Z\mid m\geq 0\lor n\notin S\}$$ with the lexical order: $(n,m)\leq (n',m')$ if $n<n'$ or $n=n'$ and $m\leq m'.$

Define the equivalence relation $\sim$ on $P_S$ as $x\sim y$ iff there are finitely many elements between $x$ and $y.$

We can determine $n$ from $x\in P_S$ by asking "How many equivalence classes have all elements less than $x?$" If $n$ is the answer, then $x=(n,m)$ for some $m,$ and this is entirely determined by the order.

An equivalence class corresponds to an element $n\in S$ if it has a minimal element. So we can determine $S$ back just from the order.

So we have $2^{\aleph_0}$ countable linear orders distinct up to isomorphism.

It is interesting that they are all a sub-order of $\mathbb N\times\mathbb Z$ with the lexical order.