Cardinality of order types in $\mathbb{N}$

Question

Let be the next equivalence relation on $B= \{R \subseteq \mathbb{N}\times\mathbb{N} \ | \ R \ is \ a \ well-order \ on \ \mathbb{N}\}$ : $$"R \equiv R' \leftrightarrow \ (\mathbb{N},R) \cong (\mathbb{N},R') \ are \ well-ordering \ sets \ isomorphic" $$

Which is the cardinality of $B/\equiv$?

Firstly, we can notice that each well-ordering set is isomorphic to an ordinal $\alpha \ $such that $\alpha < \aleph_{1}$, and so it is enough to count how many ordinals are isomorphic to a subset of $\mathbb{N}$. For example, if we consider $A$ the set of the even numbers and $B$ the set of odd numbers with the usual order relation, $A \oplus B$ is isomorphic to $\omega + \omega$. Another example could be: if we consider the order of $\mathbb{N}$ that we use in Sharkowski Theorem, that order is isomorphic to $ \omega^{2} + \omega$. Working with prime numbers we could build also $\omega^{n} \ \forall n \in \mathbb{N}$, and so $\omega^{\omega}$ and maybe something bigger. However, we know that each countable ordinal is isomorphic to a subset of $\mathbb{Q}$, but I bet that the same result is not true for $\mathbb{N}$ because it is "too small".

What can I do?

Answer 1

This is just $\aleph_1$. The point is that even a very large countable ordinal is still countable, and we can always just "push forwrad" the ordering onto $\mathbb{N}$ - the fact that the carrier set looks large initially is irrelevant.

---

Suppose $\alpha$ is an infinite countable ordinal. Let $f:\alpha\rightarrow\mathbb{N}$ be a bijection (which exists since $\alpha$ is countable and infinite) and let $\triangleleft$ be the induced order on $\mathbb{N}$: $$x\triangleleft y\iff f^{-1}(x)<f^{-1}(y)$$ (where we use the usual order on $\alpha$). Then $\triangleleft$ is a well-order on $\mathbb{N}$.

So every countable ordinal is represented by some element of $B/\equiv$, and obviously every element of $B/\equiv$ corresponds to a unique countable ordinal. So there's a bijection between $B/\equiv$ and $\omega_1$ (remember that each ordinal literally is the set of all smaller ordinals), so $B/\equiv$ has cardinality $\aleph_1$.

OK fine, strictly speaking what we have is a bijection between $B/\equiv$ and the infinite elements of $\omega_1$. But that still has cardinality $\aleph_1$.

Answer 2

Theorem (ZF). Any well-ordering is isomorphic to the $\in$-order of a unique ordinal.

In set theory a binary relation $R$ on a set $S$ is some (any) subset of $S\times S,$ but we often write $xRy$ rather than $(x,y)\in R.$ (If $S$ is a set of real numbers and $R$ is "$<$" then $x<y$ means $(x,y)\in <,$ which looks a little odd at first.)

Axiom (ZF). Power. $\forall x\,\exists y=P(x)\,\forall z\,(z\in y\iff z\subset x).$

Let $S$ be the set of all members of $P(\omega\times \omega)$ that are countably infinite well-orders. ($S$ exists by Power and by an instance of the axiom schema of Comprehension.) Now for each $w\in S$ there is a $unique$ ordinal $f(w),$ ordered by $\in,$ that is isomorphic to $w,$ so by the axioms of Replacement and Comprehension there exists $T=\{f(w):w\in S\}.$

$T$ is a set of countably infinite ordinals.

If $x$ is a countably infinite ordinal then $w=\{(z,y):z\in y\in x\}\in S$ so $f(w)\in T. $ But the ordinal $x,$ ordered by $\in ,$ cannot be isomorphic to the ordinal $f(w), $ ordered by $\in,$ unless $x=f(w).$ So $x=f(w)\in T.$

So $T$ contains every countably infinite ordinal. So $T\cup \omega$ is the set of all countable ordinals, which $is$ $\omega_1.$

There is a bijection $b:T\to \omega_1.$ E.g. let $b|_{(\omega + \omega)\setminus \omega} \to \omega +\omega$ be bijective and let $b(x)=x$ for $\omega + \omega \le x\in T.$

We can identify $\Bbb N$ with $\omega$ (as set-theorists are wont to do) or with $\omega \setminus \{0\}$, but in either case, each well-order on $\Bbb N$ is isomorphic to the $\in$-order on a unique member of $T.$ And each member of $T$ is isomorphic to a well-order on $\Bbb N.$ And no two members of $T$ (ordered by $\in$) are isomorphic to each other.

Remark: The first part above shows how (in ZF) we use the axioms of Infinity and Power to produce the uncountable ordinal $\omega_1.$ By the same method, if $k$ is any infinite ordinal, there exists $k^+,$ the least (cardinal) ordinal greater than $k$ that's not bijective with $k.$