What are some kinds of models where DC holds?

Question

There are a lot of ways to build a model where DC fails. However, all of them that I'm aware of involve adding at least a messy set of reals (or rather, taking a forcing extension and then passing to an intermediate structure where some prescribed set becomes messy). It occurred to me recently that I don't know how to kill DC by only changing the reals; and after playing around with it for a couple days, I still don't see how to do it.

I suspect I'm missing some very obvious ideas, but I haven't been able to find it on my own. And it nags at me a bit that I don't even know these basic facts about breaking DC, hence my asking here.

Specifically, there are a few ways to phrase the question. The simplest one is:

Q1. Does ZF+$V=L(\mathbb{R})$ imply DC?

EDIT: I didn't quite ask the question I intended here. Although I'm very pleased to have a (negative) answer to the above question, the one I had in mind when I wrote this was:

Q1'. If $M\models$ ZFC, does $L(\mathbb{R})^M\models$ DC?

(I am very very tired right now, and I managed to convince myself that every model of ZF+$V=L(\mathbb{R})$ is the $L(\mathbb{R})$ of some ZFC-model, which is of course completely bonkers.) The negative answer Jing Zhang gives is the $L(\mathbb{R})$ of a very non-choicey model.

At the more ambitious end, we have:

Q2. Suppose $M\models$ ZFC and $G$ is a set of reals which is generic over $M$. Is DC necessarily true in $HOD^{M[G]}(M\cup G)$?

I do mean "$M\cup G$" instead of "$M\cup G\cup \{G\}$" - I want to include only the individual reals in $G$. Also, note that $HOD(X)$ makes sense even when $X$ is a transitive class.

Even Q1 seems implausible; Q2 seems downright ridiculous. But I can't cook up a counterexample at the moment.

In general, I'm interested in learning when a substructure of a forcing extension can be easily seen to have DC:

Q3. What are some properties of symmetric submodel constructions which "quickly" imply DC?

Answer 1

Here's an attempt to get a negative answer for Q2 (a standard example; see Asaf's comment below). Let $M$ be $L$, and consider the derived model at $\aleph_{\omega}$. For any set $A$ of ordinals, the Levy collapse $\mathrm{Levy}(\omega, A)$ is the partial order of containment on the set of finite partial functions $p \colon A \times \omega \to \bigcup A$ with $p(\alpha, i) \in \alpha$ for all $(\alpha, i)$ in the domain of $p$. Let $H$ be an $L$-generic filter for $\mathrm{Levy}(\omega, \aleph_{\omega})$, and let $G$ (which we would normally call $\mathbb{R}^{*}$) be $$\bigcup_{\gamma < \aleph_{\omega}} (\mathbb{R} \cap V[H \cap \mathrm{Levy}(\omega, \gamma)]).$$ Since $\mathrm{Levy}(\omega, \aleph_{\omega})$ is homogeneous, $\mathrm{HOD}^{L[H]} = L$. We want to see that $\aleph_{\omega}^{L} = \omega_{1}^{L(G)}$, as this will show that $\mathrm{DC}_{\mathbb{R}}$ fails in $L(G)$, so $\mathrm{DC}$ does as well. As forcing with $\mathrm{Levy}(\omega, \gamma)$ makes all ordinals less than $\gamma$ countable, $\aleph_{\omega}^{L} \leq \omega_{1}^{L(G)}$, so we want to see that there is no surjection from $\omega$ onto $\aleph_{\omega}^{L}$ in $L(G)$. Perhaps the easiest way to see this is to note that $L(G)$ is an inner model of $\mathrm{HOD}^{L[H]}_{G}$. Every real in $\mathrm{HOD}^{L[H]}_{G}$ is (by the definition of $\mathrm{HOD}^{L[H]}_{G}$) ordinal definable in $L[H]$ from a finite $g \subseteq G$, and any such $g$ is an element of $V[H \cap \mathrm{Levy}(\omega, \gamma)]$ for some $\gamma < \aleph_{\omega}^{L}$. Fix such a $\gamma$. By the homogeneity of $\mathrm{Levy}(\omega, \aleph_{\omega} \setminus \gamma)$ (and the fact that $\mathrm{Levy}(\omega, \aleph_{\omega})$ is isomorphic to $\mathrm{Levy}(\omega, \gamma) \times \mathrm{Levy}(\omega, \aleph_{\omega} \setminus \gamma)$), every real which is ordinal definable from $g$ in $L[H]$ must already be in $V[H \cap \mathrm{Levy}(\omega, \gamma)]$, in which $\aleph_{\omega}^{L}$ is uncountable.

For the last question in the comments, suppose that $X \in L(X)$ and that $L(X) \models \mathrm{DC}_{X}$. Suppose that $T$ is a tree of height $\omega$ without terminal nodes. There exists an ordinal $\gamma$ such that each element of $T \cup \{T\}$ is ordinal definable in $L_{\gamma}(X)$ from a finite subset of $X$. Fixing a list $\langle \phi_{i} : i < \omega \rangle$ of the first-order formulae, let $Y$ be the set of $(i, a, b) \in \omega \times X^{<\omega} \times \gamma^{<\omega}$ such that $\{ x \in L_{\gamma}(X) : L_{\gamma}(X) \models \phi_{i}(x,a,b)\}$ is an element of $T$. Let $T'$ be the tree order on $Y$ induced by $T$. An infinite branch through $T'$ then induces one for $T$.

It suffices then to show that for any set $X$, and any ordinal $\delta$, $\mathrm{DC}_{X}$ implies $\mathrm{DC}_{X \times \gamma}$. Fix a tree $T$ on $X \times \gamma$ without terminal nodes, and remove from $T$ each successor node $(\bar{x}^{\frown}\langle x_{n} \rangle, \bar{\alpha}^{\frown}\langle \alpha_{n} \rangle)$ for which there is a $\beta < \alpha$ with $(\bar{x}^{\frown}\langle x_{n} \rangle, \bar{\alpha}^{\frown}\langle \beta \rangle)$ in $T$. Call this tree $T'$, and let $T''$ be the tree formed from $T'$ be removing the second coordinate from each node. Then $T''$ has no terminal nodes, and an infinite branch through $T''$ induces infinite branches through $T'$ and $T$.

Answer 2

I believe the answer to Q1' is yes; here's a sketch of a proof. First notice that we can code elements of $L(\mathbb R)$ by ordinals and reals. That's because (except for the reals and their elements, which are thrown in to start the construction of $L(\mathbb R)$ and are easily coded), an element of $L(\mathbb R)$, say in $L_{\alpha+1}(\mathbb R)$, looks like $\{x\in L_\alpha:(L_\alpha,\in)\models\phi(x,\vec p)\}$ for some formula $\phi$ (codable by a natural number) and some parameters $\vec p$ from $L_\alpha$ (codable thanks to induction hypothesis). Since finitely many ordinals can (without AC) be coded as one ordinal and since finitely many reals can (without AC) be coded as one real, we have a set-theoretically definable surjection $F:\text{ORD}\times\mathbb R\to L(\mathbb R)$. Note that this coding scheme is absolute between $V$ and $L(\mathbb R)$.

So DC in $L(\mathbb R)$ reduces to the special case where the choices are to be made, not from an arbitrary set, but from $\lambda\times\mathbb R$ for some ordinal $\lambda$. Working in $V$ where AC holds, we can get a sequence $\langle(\alpha_n,r_n):n\in\omega\rangle$ as required by DC, and we can do this in such a way that each of the ordinals $\alpha_n$ is as small as possible given all the earlier choices --- at each step, you just pick the smallest possible ordinal to serve as $\alpha_n$ and then, for this $\alpha_n$, pick some arbitrary appropriate $r_n$.

This sequence, though produced in $V$, is in fact in $L(\mathbb R)$. The point is that the $\omega$-sequence of reals $\langle r_n\rangle$ can be coded as a single real, so we can give it to an inhabitant of $\langle(\alpha_n,r_n):n\in\omega\rangle$. Using that real, the inhabitant of $L(\mathbb R)$ can produce the sequence $\langle(\alpha_n,r_n):n\in\omega\rangle$, by always using the smallest possible $\alpha_n$ along with the real $r_n$ that we supplied, and this sequence is as required by DC.

Note that I didn't need AC in $V$; DC in $V$ suffices. So (unless I've made a mistake) $\text{DC}^{L(\mathbb R)}$ is a theorem of ZF+DC.

Answer 3

Here's a negative answer to Q1 (it looks like the comment addressing this was flawed):

It is consistent with ZF that there is an infinite Borel (in fact, $F_{\sigma\delta}$) set $B$ with no greatest element which is Dedekind-finite. Now every Borel set is coded by a real, so it is consistent with ZF + $V=L(\mathbb{R})$ that there is such a Borel set. But now consider the relation $<$ restricted to $B$: DC fails for this relation, since otherwise we could embed $\omega$ into $B$, contradicting the Dedekind-finiteness of $B$.

---

Why we can assume $B$ has no greatest element: let $B_0=B$, and $B_{i+1}=B_i$ minus $B_i$'s greatest element, if it exists, and $B_i$ otherwise. This sequence has to stabilize at a finite stage, since otherwise we get an embedding of $\omega$ into $B$; but the resulting $B_i$ is still Borel (in fact, $F_{\sigma\delta}$), infinite, and Dedekind-finite, so we can WLOG assume that this was the original $B$ we picked.

Answer 4

I cannot answer either formulation of Q1, although it did pop through my mind just yesterday. Funny.

For the second question, I cannot give you an accurate answer, but I believe that the answer is negative. To see why, consider Feferman's model, where we add countably many Cohen reals, then remember each of them separately, but not the set (and certainly not the real which codes their sequence), this model is—to my best understanding—a model of the form that you ask for (and maybe even satisfying $V=L(\Bbb R)$, although I'm not clear about that). Nevertheless, the model does not satisfy $\sf DC$.

For the last question, here are two "easy" ways to get $\sf DC_\kappa$ when taking symmetric extensions. Suppose that $(\Bbb P,\scr G,F)$ is a symmetric system. Then either one of the two conditions imply that the symmetric model is closed under $\kappa$-sequences:

1. $\Bbb P$ is $\kappa^+$-c.c., and $\scr F$ is $\kappa^+$-complete.
2. $\Bbb P$ is $\kappa^+$-closed and $\scr F$ is $\kappa^+$-complete.

To see why, note that either these conditions imply that if $\dot f$ is a name for a $\kappa$-sequence of elements in the symmetric extensions, then one can use the chain condition or the closure of $\Bbb P$ to generate a sequence of names for each value of $\dot f$, and the completeness of $\scr F$ allows us to generate a uniform support for the sequence.

You can find the proof under the second condition in my paper:

Karagila, Asaf, Embedding orders into the cardinals with $\mathsf {DC}_{\kappa} $, Fundam. Math. 226, No. 2, 143-156 (2014). ZBL1341.03068.

The proof of the first condition does not appear in print, as far as I know, but it is very similar to the first one.