# Relationship between fragments of the axiom of choice and the dependent choice principles

The dependent choice principle ${\rm DC}_\kappa$ states that if $S$ is a nonempty set and $R$ is a binary relation such that for every $s\in S^{\lt\kappa}$, there is $x\in S$ with $sRx$, then there is a function $f:\kappa\to S$ such that for every $\alpha<\kappa$, $f\upharpoonright\alpha R f(\alpha)$. The axiom of choice fragment ${\rm AC}_\kappa$ states that every family of size $\kappa$ has a choice function. There are several classical theorems (see Jech's "Axiom of Choice", chapter 8) concerning the relationship between the dependent choice principles and fragments of the axiom of choice.

Theorem 1: Over ${\rm ZF}$, ${\rm AC}$ is equivalent to $\forall\kappa\,{\rm DC}_\kappa$.

Theorem 2: Over ${\rm ZF}$, $\forall \kappa\,{\rm AC}_\kappa$ implies ${\rm DC}_\omega$.

Theorem 3: It is consistent with ${\rm ZF}$ that $\forall \kappa\,{\rm AC_\kappa}$ holds but ${\rm DC_{\omega_1}}$ fails (theorem 8.9).

Theorem 4: It is consistent with ${\rm ZF}$ that ${\rm AC}_\kappa$ holds for some cardinal $\kappa>>\omega$ but ${\rm DC}_\omega$ fails (theorem 8.12).

Jech proves theorems 3 and 4 using permutation models (and then discusses how to obtain ${\rm ZF}$-models with the same properties). But I am wondering whether there are direct symmetric model constructions for these two results. Either a reference for the arguments or the arguments themselves would be appreciated.

• The references seem to be interchanged: 3 corresponds to Theorem 8.9 and 4 to Theorem 8.12 Aug 13, 2014 at 14:54
• I think that you can do it in a "similar way" by using a Cohen forcing. This is essentially adding sufficiently many Cohen sets, and defining atom-like names (meaning they all have the same properties over the ground model), and use the same type of automorphisms and filters. The argument should translate relatively smoothly. I will sit and verify that after I had some sleep. But my experience with translating permutation models to symmetric models says that it has a good chance of working. Aug 13, 2014 at 15:06
• Thanks, Asaf! This is exactly what I dreaded having to do :). Aug 13, 2014 at 15:08
• Well, I have been wanting to sit and do it for two years now. This seems like a good excuse to do it. Aug 13, 2014 at 15:09
• I've just checked Howard-Rubin and it seems that at least for result 3 it can be done as Asaf says; Feferman/Solovay model does the trick. You have to add $\omega_1$ generic reals to the base model without collecting them in a set. For result 4, however, it seems the only available model is Jech's permutation model... Aug 13, 2014 at 15:24

The idea is to mimic the permutation models as given in Jech. One can then ask, "Well, in Jech he chooses some set of objects in the full universe, and shows it has a support. But in forcing we don't have a simple access to names like that, since they might not be "sufficiently determined" for us to collect them into a symmetric name!"

To counter the effects of this problem here is a generalized formulation of The Continuity Lemma, as Felgner called it (for the basic Cohen model). $$\newcommand{\PP}{\Bbb{P}}\newcommand{\dom}{\operatorname{dom}}\newcommand{\fix}{\operatorname{fix}}\newcommand{\sym}{\operatorname{sym}}\newcommand{\forces}{\Vdash}$$

Suppose that $$\PP$$ is a Cohen type forcing, with $$p\colon A\times\kappa\to2$$ such that the domain of $$p$$ is $$<\kappa$$, ordered by reverse inclusion. We write $$s(p)$$ as the projection of the $$\dom p$$ onto $$A$$.

Let $$\scr G$$ be a group of permutations of $$A$$ acting on $$\PP$$ naturally: $$\pi p(\pi a,\alpha)=p(a,\alpha)$$. And let $$I$$ be an ideal on $$A$$ which is closed under $$\scr G$$, and $$s(p)\in I$$ for all $$i\in I$$. Moreover, assume that whenever $$X,Y\in I$$ there is a permutation in $$\scr G$$ such that $$\pi\upharpoonright(X\cap Y)=\operatorname{id}$$ and $$\pi''(X\setminus Y)$$ is disjoint from $$Y$$.

Then whenever $$\dot x_1,\ldots,\dot x_n$$ are symmetric names with respect to the filter generated by $$\{\fix(E)\mid E\in I\}$$ and $$E\in I$$ such that $$\fix(E)$$ is a subgroup of $$\sym(\dot x_i)$$ for each $$i$$, and $$p\forces^{\sf HS}\varphi(\dot x_1,\ldots,\dot x_n)$$ then $$p\upharpoonright(E\times\kappa)\forces^{\sf HS}\varphi(\dot x_1,\ldots,\dot x_n)$$.

(If you are uncomfortable with the notion of $$\forces^{\sf HS}$$ you can instead require $$\varphi$$ to be $$\Delta_0$$, and replace the relativized quantifiers by names one at a time.)

Okay let me explain this for a second, since there are plenty of conditions and plenty of more conditions in the consequences. The idea is that if $$p$$ forces that something happens in the symmetric model, about concrete symmetric names, then we can restrict $$p$$ to something whose support is in the ideal, and already this decides the same value for the same statement with the same names. In our two examples, all the conditions will be easy to verify.

## Theorem I:

Let $$\kappa$$ be a successor cardinal, then it is consistent that $$\sf DC_{<\kappa}$$ holds, $$\sf W_\kappa$$ fails, and $$(\forall \lambda\in\rm Ord)\sf AC_\lambda$$

### Proof.

We take $$\PP$$ to be functions from $$\kappa\times\kappa\to2$$ with domain smaller than $$\kappa$$. $$\scr G$$ here is the group of all permutations of $$\kappa$$ and $$I$$ is $$[\kappa]^{<\kappa}$$. So the conditions easily hold, and just to remind you here our filter of subgroups is the one generated by $$\{\fix(E)\mid E\in I\}$$, and it is normal since $$I$$ is closed under the operation of $$\scr G$$, and $$\cal F$$ is $$\kappa$$-complete since $$I$$ is $$\kappa$$-complete.

If $$G$$ is a generic filter, we let $$a_\alpha=\{\beta\mid\exists p\in G: p(\alpha,\beta)=1\}$$, and $$\dot a_\alpha$$ is going to be the canonical name for this set. Additionally, $$A$$ is the set of all these $$a_\alpha$$ and $$\dot A$$ will be its canonical name. Let $$N$$ be a symmetric model defined by $$\cal F$$ given above, then by standard arguments $$A$$ is in $$N$$.

First off, if both the forcing and the filter are $$\kappa$$-closed, then $$\sf DC_{<\kappa}$$ holds in the symmetric model. This much is easy to verify (you can look it up in my thesis, or in some of the written notes in my homepage). So we have this for almost free.

Secondly, $$\sf W_\kappa$$ fails since $$|A|$$ and $$\kappa$$ are incomparable. This is a standard proof, like the one in Cohen's first model with the Dedekind-finite set of real numbers.

The big trick is to show that given a function $$X\colon\lambda\to N\setminus\{\varnothing\}$$ then we want to find a function $$g$$ with domain $$\lambda$$ such that $$g(i)\in X(i)$$. Suppose that $$p\in G$$ and $$\dot X$$ is a hereditarily symmetric name for $$X$$ such that $$p$$ forces $$\dot X$$ has the above properties.

Let $$E\in I$$ be a support for $$\dot X$$, namely if $$\pi\in\fix(E)$$ then $$\pi\dot X=\dot X$$. Without loss of generality $$s(p)\subseteq E$$ and $$|E|^+=\kappa$$. Pick some $$E'$$ disjoint to $$E$$ and $$|E'|=|E|$$. We will find a choice function with support $$E\cup E'$$.

For each $$\gamma<\lambda$$ let $$q\leq p$$ such that for some symmetric $$\dot y_\gamma$$ we have that $$q\forces\dot y_\gamma\in\dot X(\check\gamma)$$. Let $$F$$ be a support for $$\dot y_\gamma$$, now we can find some $$\pi\in\fix(E)$$ such that $$\pi''F\subseteq E\cup E'$$, define $$\dot x_\gamma=\pi\dot y_\gamma$$. Now we have that $$\pi q\leq p$$ (since $$\pi p=p$$), $$E\cup E'$$ is a support for $$\dot x_\gamma$$, and $$\pi q\forces\dot x_\gamma\in\dot X(\check\gamma)$$. So $$\pi q\upharpoonright(E\cup E'\times\kappa)$$ also forces that.

For each $$\gamma<\lambda$$ pick a maximal antichain below $$p$$ of conditions as above (and we can assume they all have domain within $$E\cup E'\times\kappa$$), $$D_\gamma$$ and names $$\dot x_\gamma(q)$$ as above. Then $$\{(q,(\check\gamma,\dot x_\gamma(q))^\bullet)\mid q\in D_\gamma,\gamma<\lambda\}$$ is a choice function and $$E\cup E'$$ is clearly a support for it. $$\square$$

## Theorem II:

If $$\kappa$$ is uncountable, then it is consistent that $$\sf DC$$ fails, $$\sf W_{<\kappa}$$ and $$\sf AC_{<\kappa}$$ both hold.

## Proof.

Let me skimp out on most of the details. We take $$A$$ in this case to be $$\kappa^{<\omega}$$ (you can replace $$\omega$$ here by the least cardinal for which you want $$\sf DC$$ to fail). Our automorphism group is going to be the automorphisms of the tree $$\kappa^{<\omega}$$ and the ideal of supports is the ideal of subtrees of cardinality less than $$\kappa$$ with no branches (in the case of $$\sf DC$$ these are really the subtrees which are well-founded).

For $$t\in\kappa^{<\omega}$$ define $$a_t$$ as the Cohen set defined when fixing $$t$$ and $$A$$ as the set of all $$a_t$$'s. Then the structure of $$\kappa^{<\omega}$$ is fixed trivially by the automorphisms, so $$A$$ has a tree structure but no branches (since a branch would require a support with an unbounded tree). Therefore $$\sf DC$$ fails.

To show that $$\sf W_\lambda$$ or $$\sf AC_\lambda$$ hold, for $$\lambda<\kappa$$, we perform a trick similar to the previous proof. However here we need to be slightly more careful. But we can also notice that the union of trees whose intersection is without branches is also without branches. Therefore the union of any less than $$\kappa$$ "almost disjoint" supports is a support.

So here we take a name and by induction we construct a sequence of conditions and names which witness $$\sf W_\lambda$$ or $$\sf AC_\lambda$$. Simply by ensuring that the next name we take has a support which extends the previously chosen names "sideways" and not "up". This will guarantee that the union of the symmetric names for the functions at limit steps is a function. And again the generalized continuity lemma ensures we can always restrict back to smaller conditions as we progress, to ensure that their support is in the ideal.

• Yes, maybe I went a bit too far with the length of this answer... :-) Aug 20, 2014 at 6:15
• @AsafKaragila Please add the definition of $\mathsf W_\kappa$ to your answer. Apr 24, 2020 at 6:31
• @AsafKaragila Thank you, but anyway, it is better to have all notions appearing in formulations of theorem defined, just for convenience of readers. Unfortunately I do not have Jech's book on Axioms of Chice (only his funcdamental "Set Theory"). Apr 24, 2020 at 6:36
• @Taras: You can find the proof in Jech's "Axiom of Choice", I am sure. Here are two ways to prove it. (1) The Ultrafilter Lemma is equivalent to the compactness theorem for FOL, given a set $A$, look at the language of $\{<,c_a\}_{a\in A}$ and the axioms stating that $<$ is linear and that each $c_a$ is distinct from the others, easily compactness apply here and we have a model. (2) We show the Order Extension Property (then apply it to the discrete order), and you can find a proof of that in math.stackexchange.com/a/271012/622 if you want a "proper cite-able reference", let me know. Apr 30, 2020 at 7:14
• @Taras: Yes. That is correct. $\sf DC\to AC_\omega\to CUT\to AC_\omega^{fin}$, and none of the implications are reversible. Note that some authors switch the subscript and superscript in the notation. But I prefer this way. Apr 30, 2020 at 10:48