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

Question

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.

Answer 1

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.

Answer 2

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$