8
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I actually answered this question on math.SE before. math.stackexchange.com/questions/165010/… $\endgroup$
    – Asaf Karagila
    Nov 17, 2012 at 7:32
  • $\begingroup$ 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 $\endgroup$
    – user30793
    Jan 20, 2013 at 7:06
  • $\begingroup$ 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). $\endgroup$ Jan 20, 2013 at 18:59

4 Answers 4

10
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I don't understand why this doesn't prove that the ordinal $\omega_1$ hasn't a size equal to the continuum $\endgroup$ Mar 25, 2018 at 15:26
  • $\begingroup$ For the same reason that, although there are continuum many well-orderings of $\omega $ in order-type $\omega $, this obviously does not mean that $\omega $ is the continuum. The point is that when counting order-types you count equivalence classes rather than the size of the classes themselves. $\endgroup$ Mar 25, 2018 at 15:31
  • $\begingroup$ Wait, I said $\omega_1$, not $\omega$, which we know is the first uncountable ordinal but isn't of size continuum without assuming CH. However, what I think that is happening is that many of the continuum well-orderings of $\omega$ are isomorphic and the set collapses when you see them as ordinals. $\endgroup$ Mar 26, 2018 at 16:10
  • $\begingroup$ I understood what you said and my use of $\omega$ was intentional. Anyway, yes, the issue is that many well-orderings coincide. $\endgroup$ Mar 26, 2018 at 16:16
  • $\begingroup$ I'm sorry, now I understood what you meant. Thank you! $\endgroup$ Mar 26, 2018 at 22:09
17
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
7
  • 3
    $\begingroup$ 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$. $\endgroup$ Nov 17, 2012 at 14:54
  • $\begingroup$ @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? $\endgroup$ Nov 17, 2012 at 17:42
  • $\begingroup$ 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 $\endgroup$ Nov 17, 2012 at 17:46
  • 2
    $\begingroup$ @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. $\endgroup$ Nov 17, 2012 at 18:03
  • 1
    $\begingroup$ 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.) $\endgroup$ Nov 17, 2012 at 18:33
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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