# 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 regular 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^+]^{\leq\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 is $$\kappa^+$$-c.c. and the filter is $$\kappa^+$$-complete, then $$\sf DC_\kappa$$ holds in the symmetric model, and this is the case here assuming suitable $$\sf GCH$$. This much is easy to verify (see my paper "Preserving Dependent Choice" for that). 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 $$\alpha<\lambda$$, find a maximal antichain below $$p$$, $$D=\{q_\gamma\mid\gamma<\kappa\}$$, such that there is a hereditarily symmetric name $$\dot y_\gamma$$ for which $$q_\gamma\forces\dot y_\gamma\in\dot X(\check\alpha)$$. Let $$E_\gamma$$ be such that $$s(q_\gamma)\subseteq E_\gamma$$ and $$\fix(E_\gamma)\subseteq\sym(\dot y_\gamma)$$.

Now, find $$\pi\in\fix(E)$$ such that $$\pi\colon\bigcup_{\gamma<\kappa}E_\gamma\to E\cup E'$$ (it need not be surjective between the two sets, just a permutation of $$\kappa^+$$ mapping the points outside of $$E$$ into $$E'$$). Note that $$\{\pi q_\gamma\mid\gamma<\kappa\}$$ remain a maximal antichain below $$p$$. But now, $$\sym(\pi\dot y_\gamma)$$ contains $$\fix(E\cup E')$$.

Finally, let $$\dot x_\alpha$$ denote the name mixed over the $$\pi q_\gamma$$ from the $$\pi\dot y_\gamma$$. Namely, $$\pi q_\gamma\forces\dot x_\alpha=\pi\dot y_\gamma$$. This can be done in a way that ensures that $$\dot x_\alpha$$ is hereditarily symmetric, since all the $$\pi\dot y_\gamma$$ and the $$\pi q_\gamma$$ have a common support, namely $$E\cup E'$$.

Now define $$\dot g=\{(p,(\check\alpha,\dot x_\alpha)^\bullet)\mid\alpha<\lambda\}$$, and it is easy to see that $$p\forces\dot g(\check\alpha)\in\dot X(\check\alpha)$$ and that $$\dot g$$ is hereditarily symmetric as wanted. $$\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

In the comments of Asaf' answer I explain why there is a problem in his proof of Theorem 1. In this answer I try to correct them by slightly modifying his argument. I'll keep the same notation of his answer.

## Theorem I

Let $$\kappa$$ be a successor cardinal, then it is consistent that $$\text{DC}_{<\kappa}$$ holds, $$\text{W}_\kappa$$ fails and $$(\forall \lambda \in \text{Ord})\ \text{AC}_\lambda$$ holds

## Proof.

Let $$\mathbb{P}$$, as before, to be the functions from $$\kappa\times\kappa \rightarrow 2$$ with domain smaller than $$\kappa$$. If $$G$$ is a generic filter, $$\alpha \in \kappa$$ and $$s\subset\kappa$$ has cardinality less than $$\kappa$$, we let $$a_{\alpha, s} = \{\beta \mid \exists p \in G : (p(\alpha, \beta) = 1 \text{ and } \beta \not\in s) \text{ or } (p(\alpha, \beta) = 0 \text{ and } \beta \in s)\}$$ with $$\dot{a}_{\alpha, s}$$ being its canonical name, and for each $$\alpha \in \kappa$$ we let \begin{align*}a_\alpha &= \{a_{\alpha, s} \mid s \subset \kappa \text{ with } |s|<\kappa\}\\A &=\{a_\alpha \mid \alpha\in\kappa\} \end{align*} with $$\dot{a}_\alpha, \dot{A}$$ being their canonical names.
At this point, for every $$X$$ subset of $$\kappa\times\kappa$$, $$|X|< \kappa$$ we let $$\sigma_X$$ be the automorphism of $$\mathbb{P}$$ that interchanges 0's and 1's at every point of $$X$$, i.e. if $$p \in \mathbb{P}$$ then $$(\sigma_X p) (\alpha, \beta) = 1-p(\alpha, \beta)$$ if $$(\alpha,\beta) \in X$$ and $$(\sigma_X p) (\alpha, \beta) = p(\alpha, \beta)$$ otherwise.

We let our automorphism group $$\cal G$$ be generated by $$\{\sigma_X \mid X\subset \kappa\times\kappa, |X|<\kappa\}$$ and by the group of all permutations of $$\kappa$$ (the ones in Asaf' answer).
Then we let $$\cal F$$ be the filter on $$\cal G$$ generated by $$\{\text{fix}(E) \mid E\subset \kappa, |E|<\kappa\}$$ with $$\text{fix}(E)=\{\pi \in \mathcal{G} \mid \pi (\dot{a}_{\alpha, s}) = \dot{a}_{\alpha, s} \text{ for all } s \text{ and }\alpha \in E\}$$

Let $$N$$ be the symmetric model defined by $$\cal F$$ above, then by standard arguments all $$a_{\alpha, s}$$'s, all $$a_\alpha$$'s and $$A$$ are in $$N$$.

As before, since both our forcing and our filter are $$\kappa$$-closed then $$\text{DC}_{<\kappa}$$ holds in $$N$$. Moreover $$W_\kappa$$ fails since $$|A|$$ and $$\kappa$$ are incomparable.

Now, regarding $$(\forall \lambda \in \text{Ord}) \text{AC}_\lambda$$, suppose that we have $$X:\lambda \rightarrow N\setminus \{\emptyset\}$$ in $$N$$. Let $$\dot{X}$$ be a symmetric name for $$X$$ and let $$p \in G$$ such that $$p$$ forces that $$\dot{X}$$ has the above properties.

Let $$E \in [\kappa]^{<\kappa}$$ be a support for $$\dot{X}$$. Pick some $$E'$$ disjoint from $$E$$ and such that $$|E'|^+ = \kappa$$. We will find a choice function with support $$E \cup E'$$.

First assume that $$s(p)\subseteq E\cup E'$$. For each $$\gamma<\lambda$$ let $$q\leq p$$ such that for some symmetric $$\dot y_\gamma$$ we have that $$q\Vdash\dot y_\gamma\in\dot X(\check\gamma)$$. Let $$F$$ be a support for $$\dot y_\gamma$$ and assume $$s(q) \subseteq F$$, now we can find some $$\pi\in\text{fix}(E)$$ such that $$\pi''F\subseteq E\cup E'$$ and such that $$\pi q$$ is compatible with $$p$$ (first we use a permutation on $$\kappa$$ that sends $$F$$ in $$E\cup E'$$ and then we flip all the eventual bits that would make $$p$$ and $$\pi q$$ incompatible).
Define $$\dot x_\gamma=\pi\dot y_\gamma$$ and let $$q'$$ extend both $$p$$ and $$\pi q$$ with $$s(q')\subseteq E\cup E'$$, then $$q' \le p$$ and $$q' \Vdash \dot x_\gamma\in\dot X(\check\gamma)$$.

So, wrapping up, starting with a condition $$p$$ with $$s(p)\subseteq E \cup E'$$ forcing that $$\dot{X}$$ has the wanted properties and some $$\gamma < \lambda$$, we have found a symmetric name $$\dot x_\gamma$$ with support $$E\cup E'$$ and a condition $$q' \le p$$ with $$s(q')\subseteq E \cup E'$$ forcing that $$\dot x_\gamma$$ is an element of $$\dot X(\check \gamma)$$.

For each $$\gamma<\lambda$$ now we can pick a maximal antichain (maximal wrt the functions $$q$$ with domain in $$E\cup E'$$) below $$p$$ of conditions as above, $$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$$