Axiom of dependent choice and $\aleph_1$

Question

Assume we have to make a construction on countable sets, which requires choice. If we need to repeat the same construction up to cardinal $\aleph_1$ (for example to construct a chain of elementary embeddings for all ordinals $< \aleph_1$) do we need the axiom of choice or the axiom of dependent choice (DC) suffices?

Answer 1

No.

The usual construction of an Aronszajn tree, which is a tree on $\omega_1$ whose height is $\omega_1$, and every level is countable, but there is no branch in tree, requires more than $\sf DC$.

The construction is by using embedding of countable ordinals in to the rational numbers, and carefully choosing the limit points which we allow in limit stages. However this construction requires that we have a sequence of embedding from every countable ordinal into $\Bbb Q$. While each embedding exists in $\sf ZF$, it requires more than $\sf DC$ in order to assert the existence of a full sequence (well, not exactly more, but $\sf DC$ itself is not enough).

In fact, that would be an even simpler example. We can construct an embedding from every countable ordinal into the rational numbers without any appeal to the axiom of choice. However in order to construct a sequence of embedding we need to choose an embedding for every ordinal and $\sf DC$ is just not enough for that.

Answer 2

Dependent choice does not suffice.

For example, in Solovay's model, where dependent choice holds, there is no ladder sequence on $\omega_1$, that is, no sequence $(C_\alpha\mid\alpha<\omega_1)$ such that, for each limit $\alpha$, the set $C_\alpha$ is cofinal in $\alpha$ and has order type $\omega$.

Similarly, in that model there is no sequence $(f_\alpha\mid0<\alpha<\omega_1)$ where each $f_\alpha:\alpha\to\omega$ is injective.

In Solovay's model all sets of reals are "nice" (Lebesgue measurable, have the perfect subset property, etc), so none of the transfinite constructions producing "pathological" sets of reals go through, there is no injection of $\omega_1$ into $\mathbb R$ (though of course $\mathbb Q$ has copies of all countable ordinals), etc.

If we look at models of determinacy (that are closely related to Solovay's model in several nontrivial ways) then, even in those models where dependent choice holds, the club filter is an ultrafilter, so there are no stationary-co-stationary sets. (Hence, in particular, nothing resembling Ulam matrices is present.) To illustrate the close relation: Under appropriate large cardinals, $L(\mathbb R)$ is a model of determinacy where $\mathsf{DC}$ holds, and is (elementarily equivalent to) a Solovay model.

For a different source of examples, most of the interesting combinatorics on $\omega_1$-trees is missing in these determinacy models. (Several people, including Philipp Schlicht, have some very general negative results on the possibilities for Aronszajn or Kurepa trees, not just on $\omega_1$.)