How many well orderings of $\aleph_0$ are there?

Question

What is known about the set of well orderings of $\aleph_0$ in set theory without choice? I do not mean the set of countable well-order types, but the set of all subsets of $\aleph_0$ which (relative to a pairing function) code well orderings. And I would be interested in an answer in, say, ZF without choice. My actual concern is higher order arithmetic.

I would not be surprised if ZF proves there are continuum many. But I don't know.

At the opposite extreme, is it provable in ZF that there are not more well orderings of $\aleph_0$ than there are countable well-order types?

Answer 1

Colin, there are continuum many, as you suspect.

In fact, there are continuum many well-orderings of type $\omega$. The set of infinite binary sequences has size continuum. Given such a sequence $x=(x_0,x_1,\dots)$, let $i\in\{0,1\}$ be least such that $x_n=i$ infinitely often. Consider the enumeration of the naturals $a=(a_0,a_1,\dots)$ that begins with $a_0=i$. Having defined $a_n$, let $a_{n+1}$ be the first natural number not used so far, if $x_n=i$, and let $a_{n+1}$ be the second number not used so far, otherwise.

Since there are infinitely many $k$ such that $x_k=i$, the $a_n$ enumerate all naturals. Since from the sequence we can easily recover $x$, this assignment $x\mapsto a$ is injective. The ordering $a_0\lt a_1\lt a_2\lt\dots$ is a well-ordering of the naturals in type $\omega$.

It follows immediately that, for any countable infinite $\alpha$, there are continuum many well-orderings of the naturals in type $\alpha$. This is because one can simply fix a bijection between $\alpha$ and $\omega$, and use it to "transfer" the procedure just described.

Answer 2

There are two answers already, but I think this argument is simpler than both of the previous answers.

Any two permutations of $\omega$ give two different wellorderings of order type $\omega$. We show that there are $2^{\aleph_0}$ permutations of $\omega$. Given a function $f:\omega\to 2$ let $\sigma_f$ be the permutation that for all $n\in\omega$ exchanges $2n$ and $2n+1$ iff $f(n)=1$. It is clear that $f\mapsto\sigma_f$ is 1-1. Hence there are at least $2^{\aleph_0}$ wellorderings of order type $\omega$ on $\omega$.

As Andres pointed out, this transfers to every countable order type $\alpha$.

Answer 3

This is an aside that I mentioned elsewhere long ago but deserves mention here since it homes in on the counterintuition that probably led Colin to doubt the answer.

As Colin pointed out, every $R \subset \omega$ can be interpreted as a binary relation on $\omega$ through a pairing function. This leads to a partition $\mathcal{B}$ of $\mathcal{P}(\omega)$ into isomorphism classes of binary relational structures $(\omega,R)$. Every countable infinite ordinal $\alpha$ has its own isomorphism class $B_\alpha \in \mathcal{B}$ and therefore $\aleph_1 \preceq \mathcal{B}$. We can also see that $2^{\aleph_0} \preceq \mathcal{B}$ in a multitude of ways. For example, we can map each $X \subseteq \omega$ to the isomorphism class of the directed graph consisting of one directed cycle of length $n+1$ for each $n \in X$ and infinitely many isolated points to fill space. In fact, we see that $\aleph_1 + 2^{\aleph_0} \preceq \mathcal{B}$ since the ranges of these two maps are disjoint. This is all provable without the axiom of choice.

There are models of ZF in which $2^{\aleph_0}$ and $\aleph_1$ are incomparable cardinals. Solovay's model where all sets of reals are Lebesgue measurable is such an example. In such models, $\mathcal{B}$ must have cardinality strictly greater than $2^{\aleph_0}$... Yes, that's right: $\mathcal{B}$ is a partition of $\mathcal{P}(\omega)$ that has more pieces than there are elements in $\mathcal{P}(\omega)$!

Answer 4

Consider the tree of finite partial attempts to build a well-ordering, and notice that it has size continuum.

More rigorously, let:

$$T = \{ f : n \to \omega\ |\ n \in \omega, f \mbox{ injective } \}$$

ordered by extension. This is clearly an $\omega$ branching tree of height $\omega$, and its branches are precisely the injections $\omega \to \omega$. But we're interested in the set of well-orderings of $\omega$. Now, those injections which are bijections give us distinct well-orderings, but perhaps there are too few of them. What about the branches that aren't surjections? We can create distinct well-orderings out of them too: if a branch $b$ is not surjective and $X$ is the set of naturals missed by its range, consider the well-ordering obtained by taking $b$, then concatenating on to its end the numbers in $X$, ordered naturally.

So the branches of our tree are in bijection with a set of well-orderings of $\omega$, and there are continuum many branches, so there are continuum many well-orderings. Note that the set of well-orderings we get is not even the set of all well-orderings. In particular every well-ordering we get has order type $\leq \omega + \omega$.