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?


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


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.