This question may be easy and indicative of my ignorance about the failure of the axiom of choice. If so, I apologize. Below assume $\mathsf{DC}$ but not $\mathsf{AC}$. Suppose we have a partial order $A = (A, \leq)$ satisfying the following:

  1. $A$ is uncountable in the sense that there is no surjection of $\omega$ onto it.

  2. $\leq$ is a transitive partial order so that for any $a \in A$ the set of $b \leq a$ is linearly ordered

  3. $\leq$ is well founded: there is no infinite $ \leq$-descending sequence

  4. There is no uncountable $\leq$-linearly ordered subset of $A$

  5. For each $a \in A$, the set of $b\in A$ for which there is an order isomorphism between $\{c \; | \; c < b\}$ and $\{ c\; | \; c < a\}$ is countable.

Of course if choice holds then we call such an object an Aronszajn tree. What I want to know is whether, under simply $\mathsf{DC}$, this is still acceptable. Specifically, do the above conditions guarantee the existence of a rank function into $\omega_1$ so that we can make sense of "the $\alpha^{\rm th}$ level of $T$" ?

More to the point is the following. It's a well known theorem of Solovay that under $\mathsf{AD}$ $\omega_1$ is measurable and hence there are no Aronszajn trees under $\mathsf{AD}$. Does this suffice to rule out the existence of the partial order $A$ described above?


1 Answer 1


Is it acceptable? Sure. In some sense, it is an Aronszajn tree.

The condition of being well-founded, which in the presence of $\sf DC$ is the same as saying there are no decreasing sequences, is equivalent to having a rank function. So much is true in $\sf ZF$.

So you can make sense of this tree having height $\omega_1$. Even more, if you just combine 2 and 3 by saying that the predecessors of each node is a well-ordered set, then you don't even need $\sf DC$ to make sense of this $A$ being a tree of height $\omega_1$.

But here comes the thing that will haunt your nightmares.1 Not everything is well-ordered in the universe.

Start with a model of $\sf AD$ which has enough structure (e.g. $L(\Bbb R)$ inside some model of $\sf ZFC$). Now force (or rather, take a symmetric extension) over this model to add some sets well above $\Theta$, so you do not add any set of rank $<\Theta$, so that the new sets form a copy of an Aronszajn tree in some sense. If you do it well, every set of ordinals will be given by some "small" part of this tree and will not interfere with $\sf AD$, which still holds as you did not add reals or sets of reals.

And $\sf DC$ will hold because if you chose your weapons appropriately the forcing is at least $\sigma$-closed.

If you want to think about this in a more "hands-on" kind of way, force an Aronszajn tree, use it to force your new sets up beyond the clouds of $\Theta$, and then look at $L(\Bbb R,T^\omega)$ where $T$ is this copy of the tree. And again, if you were wise enough, you will get the promised model.

The key point here is that:

  1. Not everything is a set of ordinals.
  2. Not everything is below $\Theta$.

1. Or not, I'm not a witch.

  • 1
    $\begingroup$ This is very helpful, thanks! Are there restrictions on this tree you add besides the fact that its universe can't be well orderable? For instance, suppose that $\mathsf{AD}$ holds in $L(\mathbb R)$ and, in $V$ there is some particular Aronszajn tree $T$ I like. Can I add a a tree $T'$ using the forcing you're describing so that (in $V$) $T$ and $T'$ are isomorphic? $\endgroup$ Commented Jan 2, 2020 at 18:29
  • $\begingroup$ Sure. Why not? You can do anything to anything. See the very last section of my paper "Preserving Dependent Choice". (dx.doi.org/10.4064/ba8169-12-2018 or arxiv.org/abs/1810.11301) $\endgroup$
    – Asaf Karagila
    Commented Jan 2, 2020 at 18:30
  • $\begingroup$ Great thanks so much. $\endgroup$ Commented Jan 2, 2020 at 18:31
  • $\begingroup$ See you in a week or so. You can thank me in person. $\endgroup$
    – Asaf Karagila
    Commented Jan 2, 2020 at 18:31

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.