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

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?

## 2 Answers

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

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

• Apology for using both $w$ and $\omega$ in the same post. – DanielWainfleet Jun 6 at 9:31