Comparing the sizes of uncountable sets of reals under AD Working in ZF+AD, let $$\theta_0(X)=\min\{\alpha\in ON: \not\exists f: X\rightarrow \alpha\mbox{ surjective and OD}\}$$ be the least ordinal onto which $X$ does not surject in an OD way, for $X\subseteq \mathbb{R}$ uncountable and OD. Clearly if $X$ has an OD perfect subset, then $\theta_0(X)=\theta_0$ (the first term in the Solovay sequence); howevr, this need not occur, as Andreas Blass' answer to Ordinal-definable witnesses to the perfect set property? shows (consider the set of non-OD reals).
My question is: is it consistent with ZF+AD that there is an uncountable OD set of reals $X$ with $\theta_0(X)<\theta_0$? If so, what can we say about the possible values of the $\theta_0$-map? 

My motivation is, ultimately, the question Cardinal characteristics without choice; I'm especially interested in cardinal characteristics which have natural "$\kappa$-versions" for arbitrary $\kappa$ (e.g. the idea of the dominating number makes sense on $\kappa^\kappa$, not just $\omega^\omega$), and the possibility of comparing such cardinal characteristics by looking at the Solovay-type sequences their "large" sets induce; but that's jumping the gun by a substantial amount. I mention this here only in case this motivation is helpful re: finding references, etc.
 A: The following is due to John Steel - who is not on mathoverflow - following a suggestion (see Ordinal-definable witnesses to the perfect set property?) of Vladimir Kanovei; since none of this is my work, and indeed I don't currently understand the crucial theorem used, I've made this community wiki. 
I will leave this up for a while before accepting it, for two reasons: first, this uses enough inner model theory that I am not comfortable claiming correctness, and I want to see if the inner model theorists around here agree with the argument below. Second, it leaves open the question of whether the opposite answer is consistent, and I would love information on that, too.

Extremely surprisingly, at least to me, the answer to the question is consistently yes! We can indeed have "small $\theta_0$". This raises the question of what the possible values of $\theta_0(X)$ are, but I think that's a job for a later question.
CLAIM. Assume $AD^++V=L(\mathcal{P}(\mathbb{R}))$. Then the set $X$ of reals which are Cohen over HOD satisfies $\theta_0(X)=\omega_1$.
To prove this claim, we use the following theorem (John says it follows from http://www.math.uci.edu/~ntrang/AD+reflection.pdf, but I don't immediately see how):
Theorem. Assume $AD^++V=L(\mathcal{P}(\mathbb{R}))$. Then there are  definable maps $A$ and $W$ from reals such that


*

*$A(x)=\mathbb{P}_x$ is a forcing notion,

*$W(x)=W_x$ is a $\mathbb{P}_x$-name for a symmetric submodel of the generic extension of $HOD[x]$ by $\mathbb{P}_x$, and

*for every real $x$, $V=W_x^G$ for some $\mathbb{P}_x$-generic $G$.

OK, let's take that for granted for a moment; so what?
Well, let $f:\mathbb{R}\rightarrow ON$ be OD via $\varphi$ and ordinal parameters $\overline{\gamma}$. Then we have $$\mbox{$f(x)=\alpha$ $\quad$ iff $\quad$ $HOD[x]\models$"$\Vdash_{\mathbb{P}_x}$"$W_x\models \varphi(x, \overline{\gamma}, \alpha)."$"}$$ But then the set of possible values for $f(x)$, for $x$ Cohen over $HOD$, is countable in $HOD$! 
Why? Well, if $f(x)=\alpha$ for $x\in X$, then this was forced by some $p\prec x$. But there are only countably many Cohen conditions, so we're done.

Now, I believe that this generalizes to the following (this is not in John's email, so perhaps there is a subtlety of Cohen-ness I'm missing):
SECOND CLAIM: Assume $$\mbox{$AD^++V=L(\mathcal{P}(\mathbb{R}))+$"There are uncountably many $\mathbb{Q}$-generic reals over $HOD$"}$$ (for $\mathbb{Q}$ some forcing notion). Then the set $Y_\mathbb{Q}$ of reals which are $\mathbb{Q}$-generic over $HOD$ has $\theta_0(Y_\mathbb{Q})\le \vert\mathbb{Q}\vert^+$.
Based on this, I suspect it is in fact consistent with $AD^++V=L(\mathcal{P}(\mathbb{R}))$ that - for each $\omega<\kappa<\Theta$ - there is an OD set $Z_\kappa$ such that $\theta_0(Z_\kappa)=\kappa$. But I am galactically far from proving anything like this! Heck, I don't even understand everything I've written above. :P
The crucial point - even assuming everything above is correct - is establishing the lower bound. In the case of the original $X$, the lower bound was trivial: any uncountable OD set $A$ surjects onto $\omega$ in an OD way, since we can (OD-ly) find a sequence $I_n$ ($n\in\omega$) of disjoint rational intervals such that $I_n\cap A\not=\emptyset$ for all $n$. But this breaks down above $\omega$, so I'm completely lost!
