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?



How many well orderings of $\aleph_0$ are there?
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.


