What are some kinds of models where DC holds?

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?

• For Q1, how about start with a model where countable choice fails. Then you could cook up a relation on the natural numbers where DC fails. But this predicate is an element of $\mathbb{R}$ so it lives in $L(\mathbb{R})$ so DC fails there too? – Jing Zhang May 12 '17 at 15:41
• The answer to 1 is no (I see a comment just appeared indicating the same). There is a famous paper by Alekos Kechris showing that $\mathsf{ZF}+\mathsf{AD}+V=L(\mathbb R)$ implies $\mathsf{DC}$. – Andrés E. Caicedo May 12 '17 at 15:43
• @JingZhang I goofed when asking this question - see my edit. But thank you very much for that example! – Noah Schweber May 12 '17 at 15:52
• The answer to Q1' is yes. The point is that the assumption ensures $\mathsf{DC}_{\mathbb R}$ in $L(\mathbb R)$, and this suffices to ensure $\mathsf{DC}$. I imagine Yiannis Moschovakis's descriptive set theory book may have details. – Andrés E. Caicedo May 12 '17 at 15:57
• @JingZhang I'm confused about "a relation on the natural numbers where DC fails." Isn't DC for relations on the natural numbers (or on any well-ordered set) provable in ZF, just by taking the first (w.r.t. the well-ordering) appropriate element at each step? – Andreas Blass Jun 27 '17 at 16:03

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$.

• The model you described is due to John Truss. In that model every uncountable set of reals has a perfect subset, and countable unions of countable sets of reals are countable again. – Asaf Karagila Jun 27 '17 at 3:22
• Serves me right for trying to think for myself. So what goes wrong in the argument? – Paul Larson Jun 27 '17 at 3:50
• What? What's wrong about it? – Asaf Karagila Jun 27 '17 at 3:52
• Oops. I misread your comment. – Paul Larson Jun 27 '17 at 3:58
• You can also consider the Feferman--Levy model, where you only take the collapsing functions of the cardinals below your limit cardinal. Surprisingly, both models are very different. In the Feferman--Levy model there is an intermediate cardinal between the naturals and the reals, which are themselves a countable union of countable sets. So... Yeah, odd stuff in both models. – Asaf Karagila Jun 27 '17 at 4:08

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.

• Yes, I believe this is what Andres' comment was outlining. – Noah Schweber Jun 27 '17 at 16:38

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.

• Are you thinking about Cohen's first model? Because it is not of the format $L(\Bbb R)$... – Asaf Karagila Jun 27 '17 at 18:47
• @AsafKaragila My point is that if $V$ contains a Borel set which it thinks is infinite Dedekind-finite, then so does $L(\mathbb{R})^V$. So we look at $L(\mathbb{R})$ of the Cohen model. – Noah Schweber Jun 27 '17 at 19:15
• What worries me is that Feferman's model without ultrafilters on $\omega$ has the same sets of ordinals and therefore the same reals as the Cohen model. And I'm not entirely sure that DC fails there. – Asaf Karagila Jun 27 '17 at 19:16
• @AsafKaragila Well, is there any flaw in the argument that infinitude and Dedekind-finitude of the Borel set coded by $r$ transfers from $V$ to $L(\mathbb{R})^V$, whenever $V\models ZF$? Because that's all I need here, and it seems solid ... – Noah Schweber Jun 27 '17 at 19:29
• Well, you might be right. I'll have to look at this again tomorrow morning. I don't have a mind set for careful details right now... :) – Asaf Karagila Jun 27 '17 at 19:31

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.