Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If ZFC (Zermelo-Fraenkel set theory with the Axiom of Choice) is consistent, does it remain consistent when the following statement is added to it as a new axiom?

"There exists a denumerably infinite and ordinal definable set of real numbers, not all of whose elements are ordinal definable"

If the answer to the above question is negative, then it must be provable in ZFC that every denumerably infinite and ordinal definable set of real numbers is hereditarily ordinal definable. This is because every real number can be regarded as a set of finite ordinal numbers and every finite ordinal number is ordinal definable. Garabed Gulbenkian

share|improve this question
    
If you adjoin a Cohen real to L, in the resulting model are the set of L-Cohen reals countable? I am not sure, but if so then I think Joel David Hamkin's answer here mathoverflow.net/questions/10413/… gives an example showing the consistency of your statement –  Justin Palumbo Mar 10 '10 at 0:19
1  
@Justin: If r is Cohen over L then so is r+s for every constructible real s. Since the constructible reals are uncountable in L[r], there are uncountably many Cohen reals in L[r]. –  François G. Dorais Mar 10 '10 at 15:28
    
I wonder if the question I am asking is actually an open problem, although I would be surprised if it were since so much is now known about ordinal definability. Perhaps the following statement-which yields a negative answer to my question-would be considered of some interest and even be well known, if it were provable in ZFC. Is it? "If S is any ordinal definable set of real numbers which contains at least one real number among its elements that is not ordinal definable, then S is uncountable." –  Garabed Gulbenkian Mar 18 '10 at 20:44
6  
+1. This is a fascinating, outstanding question. –  Joel David Hamkins Mar 22 '10 at 22:38
2  
Ali Enayat posted this on FOM: cs.nyu.edu/pipermail/fom/2010-July/014944.html –  Kaveh Jul 24 '10 at 22:51

2 Answers 2

The original problem solves in the positive: there is a model of ZFC in which there exists a countable OD (well, even lightface $\Pi^1_2$, which is the best possible) set of reals $X$ containing no OD elements. The model (by the way, as conjectured by Ali Enayat at http://cs.nyu.edu/pipermail/fom/2010-July/014944.html) is a $\mathbf P^{<\omega}$-generic extension of $L$, where $\mathbf P$ is Jensen's minimal $\Pi^1_2$ real singleton forcing and $\mathbf P^{<\omega}$ is the finite-support product of $\omega$ copies of $\mathbf P$.

A few details. Jensen's forcing is defined in $L$ so that $\mathbf P =\bigcup_{\xi<\omega_1} \mathbf P_\xi$, where each $\mathbf P_\xi$ is a ctble set of perfect trees in $2^{<\omega}$, generic over the outcome $\mathbf P_{<\xi}=\bigcup_{\eta<\xi}\mathbf P_\eta$ of all earlier steps in such a way that any $\mathbf P_{<\xi}$-name $c$ for a real ($c$ belongs to a minimal countable transitive model of a fragment of ZFC, containing $\mathbf P_{<\xi}$), which $\mathbf P_{<\xi}$ forces to be different from the generic real itself, is pushed by $\mathbf P_{\xi}$ (the next layer) not to belong to any $[T]$ where $T$ is a tree in $\mathbf P_{\xi}$. The effect is that the generic real itself is the only $\mathbf P$-generic real in the extension, while examination of the complexity shows that it is a $\Pi^1_2$ singleton.

Now let $\mathbf P^{<\omega}$ be the finite-support product of $\omega$ copies of $\mathbf P$. It adds a ctble sequence of $\mathbf P$-generic reals $x_n$. A version of the argument above shows that still the reals $x_n$ are the only $\mathbf P$-generic reals in the extension and the set $\{x_n:n<\omega\}$ is $\Pi^1_2$. Finally the routine technique of finite-support-product extensions ensures that $x_n$ are not OD in the extension.

Addendum. For detailed proofs of the above claims, see this manuscript.

Jindra Zapletal informed me that he got a model where a $\mathsf E_0$-equivalence class $X=[x]_{E_0}$ of a certain Silver generic real is OD and contains no OD elements, but in that model $X$ does not seem to be analytically definable, let alone $\Pi^1_2$. The model involves a combination of several forcing notions and some modern ideas in descriptive set theory recently presented in Canonical Ramsey Theory on Polish Spaces. Thus whether a $\mathsf E_0$-class of a non-OD real can be $\Pi^1_2$ is probably still open.

Kanovei's addendum. With thanks to Ali for the 1401.3901 link above, I continue on Aug 21 with a simpler (?) model for a definable $\mathsf E_0$-class in $2^\omega$ with no definable elements. One may ask a similar Q wrt any reasonable Borel equivalence relation $\mathsf E$, of course, but with little chance to answer it immediately.

Fix a recursive enumeration $\{s_k:k\in\omega\}$ of all dyadic strings in $2^{<\omega}$, such that $s_0=\Lambda$ (the empty string).

Let $T$ be the tree of all dyadic strings of the form $\langle{k,0^m}\rangle$ and $\langle{k,0^m,1}\rangle$, where $k,m\in\omega$, plus the empty string $\Lambda$. Consider a ramified iterated ctble-support forcing extension $M$ of the constructible universe $L$ by a system of reals $x_t$, $t\in T$, such that $x_\Lambda$ is Silver over $L$ (Sacks will not work!!) and each $x_t$ is Sacks over $\{x_s:s\subset t\}$. Then in $M$, the reals $x_{\langle{k}\rangle}$ are the only minimal $L$-degrees over $x_\Lambda$ while the reals $x_{\langle{k,0^m}\rangle}$ and $x_{\langle{k,0^m,1}\rangle}$ (and the pairs $\langle{x_{\langle{k,0^{m'}}\rangle},x_{\langle{k,0^m,1}\rangle}}\rangle$, $m'>m$) are the only $L$-degrees over $x_{\langle{k}\rangle}$ incomparable to all $x_{\langle{\ell\rangle}}$, $\ell\ne k$.

Let, in $M$, $y_k=x_\Lambda+s_k$, where $+$ is the dyadic addition, that is $y_k(n)=x_\Lambda(n)$ whenever $s_k(n)=0$ and $y_k(n)=1-x_\Lambda(n)$ whenever $s_k(n)=1$. Then $y_0=x_\Lambda$ and $\{y_k:k\in\omega\}$ is the whole $\mathsf E_0$-class of $x_\Lambda$.

Now consider the submodel $N$ of $M$ generated by the reals

$x_\Lambda$

all reals $x_{\langle{k}\rangle}$, $k\in\omega$

all reals $x_{\langle{k,0^m}\rangle}$, $k\in\omega$

all reals $x_{\langle{k,0^m,1}\rangle}$, $k\in\omega$ and $y_k(m)=1$

Then in $N$, each subtree $T_k$ = all $L$-degrees of reals

$x_{\langle{k}\rangle}$,

$x_{\langle{k,0^m}\rangle}$,

$x_{\langle{k,0^m,1}\rangle}$, $y_k(m)=1$

codes $y_k$ by means of degrees of constructibility, while the whole forest codes the set $\{y_k:k\in\omega\}$ = the $\mathsf E_0$-degree of $x_\Lambda$, making the latter set analytically definable (lightface $\Sigma^1_7$, say) in $N$.

It takes some work to check finally that $x_\Lambda$ itself is not definable in $N$. This is based on the fact that the Silver forcing responsible for $x_\Lambda$ is invariant wrt the group $P=\prod_mP_m$, where $P_m$ is the $0-1$ flip at $m$th digit, in such a way that each Silver condition is invariant under $\prod_{m>n}P_m$ for a suitable $n$.

To conclude, this gives a model with an analytically definable $\mathsf E_0$-class (most likely not $\Pi^1_2$-definable), with no OD elements.

Further Kanovei's addendum of Aug 23. It looks like a clone of Jensen's forcing on the base of Silver's (or $\mathsf E_0$-large Sacks) forcing instead of the simple Sacks one leads to a lightface $\Pi^1_2$ generic $\mathsf E_0$-class with no OD elements. The advantage of Silver's forcing here is that it seems to produce a Jensen-type forcing closed under the 0-1 flip at any digit, so that the corresponding extension contains a $\mathsf E_0$-class of generic reals instead of a generic singleton. I am working on details, hopefully it pans out.

Further Kanovei's addendum of Aug 25. Yes it works, so there is a generic extension $L[x]$ of $L$ by a real in which the $\mathsf E_0$-class $[x]_{\mathsf E_0}$ is a lightface $\Pi^1_2$ (countable) set with no OD elements. I'll send it to Axriv in a few days.

share|improve this answer
    
Could you be so kind as to sketch the arguments? –  Joel David Hamkins Aug 15 at 7:24
    
Edited. I hope to sent a note to Arxiv in a few days –  Vladimir Kanovei Aug 15 at 9:10
    
@Vladimir, I added a link to your paper. –  Ali Enayat Aug 21 at 2:04

(I am replacing prior nonsense with a completely different suggestion. I am also turning this into CW so details can be added by somebody with time (which, sadly, most likely won't be me). Comments prior to Feb. 9, 2011, refer to said prior nonsense.)


Start with $V=L$ and force to add a Mathias real $s$. Let $W$ be the resulting extension. Let $A$ be the set of reals $r$ that are Mathias generic over $L$ and such that $L[r]=W$. I strongly suspect that a real $r$ is in $A$ iff it differs from $s$ finitely often, and so $A$ is countable, ordinal definable, and lacks any ordinal definable members.

(I have briefly discussed this idea with other set theorists, but we did not elaborate any details.)


From Andreas Blass: The following began as a comment, but Andres suggested adding it to his answer, for improved visibility. As it stands, with ordinary Mathias forcing, this won't work, because if $r\subset\omega$ is a Mathias real then so is the result of shifting it to the right (or left) by 1, and it still generates the same model. Instead of a simple shift, you could apply any strictly monotone function from $L$. But suppose you did Mathias forcing with respect to the constructibly-first non-principal ultrafilter on $\omega$ in $L$. That would avoid this problem. (Note that Joel David Hamkins's comment also depends on the fact that Prikry forcing is with respect to an ultrafilter in the ground model.)

share|improve this answer
1  
Andres, homogeneous forcing doesn't necessarily preserve OD. (Although you are likely thinking of the fact that it doesn't enlarge OD.) So I don't see why X should be OD-definable after the collapse. Indeed, it cannot be, since the same extension could have arisen by absorbing additional Cohen forcing into the collapse forcing. –  Joel David Hamkins Jun 6 '10 at 18:18
1  
About the Laver theorem: the history is that Laver proved this theorem, and Woodin later observed a similar fact independently. But this theorem doesn't give you OD preservation. It is possible to have models of V=HOD whose HOD's drop in further extensions by homogeneous forcing. –  Joel David Hamkins Jun 6 '10 at 18:22
    
To explain, for homogeneous forcing what you have is $HOD^{V[G]}\subset HOD^V$, rather than equality. If your model is $V[c][G]$, where $c$ is the Cohen real and $G$ is the collapse forcing, then we can reconstitute it as $V[c][G]=V[c'][G']$, where $c'=c\oplus d$ is built from an additional Cohen real $d$ added by $G$, and the $g'$ is the corresponding quotient forcing, which is still collapse forcing. Any proposed definition of $X$ cannot distinguish between the reals of $V[c]$ and those of $V[c']$. So $X$ is not ordinal definable in $V[c][G]$. –  Joel David Hamkins Jun 6 '10 at 18:33
    
Is the problem then that this $V_{\delta+1}$ isn't OD in the extension? If it were you could define the ground model, and thus the levels of the cumulative hierarchy of the ground model, and thus the ground model OD sets. Is that right? –  Justin Palumbo Jun 6 '10 at 18:41
    
You can see that $HOD^{V[G]}$ can differ from $HOD^V$ by first adding a Cohen real $c$, then coding it into the continuum function of $V[c][H]$, and then collapsing cardinals to $V[c][H][g]$. The combined forcing $H+g$ is equivalent to collapsing forcing, as is the whole forcing $c+H+g$, so HOD of the final model is contained in $V$. Thus, $c$ went from definable in $V[c][H]$ to nondefinable in $V[c][H][g]$, even though it was homogeneous forcing. –  Joel David Hamkins Jun 6 '10 at 18:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.