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.
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Just the well-orderings alone give at least $\aleph_1$ unique orderings. $\endgroup$– Thomas AndrewsCommented Apr 12, 2023 at 15:16
-
$\begingroup$ Cantor proved there are at least $2^{\aleph_0}$ linear orderings on $\omega$ (probably early 1880s) and Bernstein proved there are at most $2^{\aleph_0}$ linear orderings on $\omega$ (1901) -- see this mathoverflow answer. Worth mentioning is that there are $\aleph_1$ many well orderings on $\omega,$ this being one of only a handful of relatively natural (and not highly technical) cases when a set is uncountable but not provably (in ZFC) of cardinality continuum. (Another in this last category are distinct Borel classes in the Borel set hierarchy.) $\endgroup$– Dave L. RenfroCommented Apr 12, 2023 at 15:17
-
1$\begingroup$ Related. $\endgroup$– Anne BauvalCommented Apr 12, 2023 at 15:19
-
$\begingroup$ @AnneBauval when $(\omega,\le_1)$ and $(\omega,\le_2)$ are isomorphic, how can I check it ? $\endgroup$– user122424Commented Apr 12, 2023 at 15:30
-
2$\begingroup$ It is dangerous to talk about orderings of $\omega,$ because $\omega$ is an ordered set already. I assume you want countable linear orders? $\endgroup$– Thomas AndrewsCommented Apr 12, 2023 at 16:50
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
answered Apr 12, 2023 at 15:49