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

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?

-
I actually answered this question on math.SE before. math.stackexchange.com/questions/165010/… – Asaf Karagila Nov 17 '12 at 7:32
The set of infinite binary sequences has size continuum. Each of that sequences determine uniquely a well ordering of N: let A and B, the inverse image of {0} and {1} respectively; let the set AUB whith the usual order in A and in B, and m < n if m is in A and n is in B. So there are continuum many well-orderings of N that include the types w (if A is finite), all the w+n (if B is finite) and w+w (otherwise). How to assign a different type of order to each sequence with A and B infinite? Freddy William Bustos, 20 de enero de 2013 – user30793 Jan 20 '13 at 7:06
Since there are $2^{\aleph_0}$ pairs $(A,B)$ of the sort you describe, since there are $\aleph_1$ order-types of countable well-orderings, and since it's consistent with ZFC that $2^{\aleph_0}>\aleph_1$, there is no way to assign a different order type of well-orderings of $\mathbb N$ to each pair $(A,B)$ without assuming some additional axioms (at least the continuum hypothesis). – Andreas Blass Jan 20 '13 at 18:59

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.

-

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

-

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)$!

-
Another example (in the same model) of more equivalence classes than elements is "Vitali's revenge". Vitali produced a non-measurable set as a choice set for the partition of $\mathbb R$ into cosets modulo $\mathbb Q$. In Solovay's model (or any model where all sets of reals are Lebesgue measurable), Vitali's construction is blocked, there is no choice set, but the partition comes back with the even more counterintuitive property of having strictly more pieces in this partition of $\mathbb R$ than there are elements in $\mathbb R$. – Andreas Blass Nov 17 '12 at 14:54
@Andreas: That's a great one too! The argument that I know (due to Sierpinski) directly produces a non-measurable set from an injection $\mathbb{R}/\mathbb{Q}\to\mathbb{R}$. Do you know whether $\aleph_1 \preceq \mathbb{R}/\mathbb{Q}$ is provable in ZF? – François G. Dorais Nov 17 '12 at 17:42
I think saying "has more pieces" is set theoretical fasttalk rather than revealing the source of the counter to intuition. It would be (to me) pedagogically more satisfying to talk about reasons for failure of things like the pigeonhole principle, or to say that there is no map in the model that witnesses an injection from the underlying set into "the pieces" of that set. Gerhard "Ask Me About Talking Fast" Paseman, 2012.11.17 – Gerhard Paseman Nov 17 '12 at 17:46
@Francois: I don't think $\aleph_1\preceq\mathbb R/\mathbb Q$ in the Solovay model (or in models of AD). If you had $\aleph_1$ cosets of $\mathbb Q$, their union would be uncountable, so it would include a perfect set, so the continuum would be the union of $\aleph_1$ countable sets $C_\alpha$ ($\alpha<\omega_1$). But then you could get a nonmeasurable set by a Fubini argument; the binary relation "$x$ is in an earlier $C_\alpha$ than $y$" would be a nonmeasurable subset of the plane. – Andreas Blass Nov 17 '12 at 18:03
Francois, $\mathbb R/\mathbb Q$ is in Solovay's model a successor of $\mathbb R$, so it cannot embed $\aleph_1$, because then it (rather, its cardinality) would have to equal $\mathbb R+\aleph_1$, which is easy to show is different from it. (Andreas's argument, of course, is a more direct argument.) – Andrés Caicedo Nov 17 '12 at 18:33

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

-