DISCLAIMER: All pointclasses considered here are boldface.

Most of the time, when doing descriptive set theory, we want the projective sets to "behave well;" for example, maybe we don't want there to be nonmeasurable projective sets, or projective well orderings of $\mathbb{R}$, etc. Generally, this means making some (fairly conservative) large cardinal assumption, or equivalent.

At the far opposite end of things is the axiom that all sets are constructible, $V=L$. This axiom implies that there is a projective - in fact, $\Delta^1_2$ - well-ordering of the reals, and so projective sets become bad very early in the hierarchy.

My question is about the state of affairs when $V=L$ holds. My motivation is simply that I don't feel I have a good grasp on basic concepts in descriptive set theory, and the following seemed like a good test problem to assign myself; but I have thought about it for a while without making progress, so I'm asking here:

Let $\oplus$ be one of the usual pairing operators on $\omega^\omega$. For the purposes of this question, we say that a pointclass $\Gamma\subseteq \mathcal{P}(\omega^\omega)$ has the uniformization property if whenever $A\in \Gamma$, there is some $B\in \Gamma$ such that:

  • $B\subseteq A$, and

  • Whenever $x\oplus y\in A$, there is a unique $z$ such that $x\oplus z\in B$.

That is, we view $A$ as coding a relation on $\omega^\omega\times \omega^\omega$, and $B$ is the graph of a function contained in $A$. (This is not usually how uniformization is presented, but it's equivalent for all intents and purposes.) My question is then:

Assume $V=L$. Let $D$ be the set of (boldface) $\Delta^1_2$ elements of $\omega^\omega$; does $D$ have the uniformization property?

Now, it seems clear to me that $D$ should not have the uniformization property. [EDIT: As Joel's answer below shows, this is completely wrong.] The counterexample should be just the $\Delta^1_2$ well-ordering $\prec$ given by the assumption that $V=L$: uniformizing $\prec$ requires us to choose, for each real $r$, a real $s$ such that $r\prec s$; and although $\prec$ is $\Delta^1_2$, the usual way of doing this - choosing the immediate $\prec$-successor of $r$ - is no longer $\Delta^1_2$.

However, I don't know how to show that $\prec$ - or any other $\Delta^1_2$ set - cannot be uniformized in $\Delta^1_2$. I suspect I'm just missing something fairly simple.

Note: it is known that the boldface pointclasses $\Pi^1_1$ and $\Sigma^1_2$ have the uniformization property, and assuming large cardinals, the uniformization property can be further propagated to every pointclass $\Pi^1_{2n+1}$, $\Sigma^1_{2n}$. On the other hand, the class $\Delta^1_1$ of Borel sets lacks the uniformization property, provably in $ZFC$.

  • $\begingroup$ Regarding your proposed counterexample, why isn't the immediate successor function in your context $\Delta^1_2$? After all, $s$ is the immediate successor of $r$ if and only if every (so $\Pi^1_2$) countable well-founded model of V=L containing both of them thinks it is, if and only if there is (so $\Sigma^1_2$) a countable well-founded model of V=L containing both of them that thinks it is. $\endgroup$ Aug 17, 2013 at 21:38
  • $\begingroup$ Basically, the situation is that any property that can be verified inside any or all countable $L_\alpha$ with the parameters will be $\Delta^1_2$, since one can say either that is is true in one of them (giving the $\Sigma^1_2$ form) or in all of them (giving the $\Pi^1_2$ form). $\endgroup$ Aug 17, 2013 at 22:43

2 Answers 2


Unless I am mistaken, it seems to me that $\Delta^1_2$ does have the uniformization property in $L$.

For any set $A$ in $\Delta^1_2$, let $B$ select the $L$-least witness on each slice. So $B$ unifomizes $A$, and the graph of $B$ appears to be $\Delta^1_2$, by the following reasoning:

  • $x\oplus z\in B$ if and only if it is in $A$, and for every well-founded countable model $M$ of $V=L$ containing $x$ and $z$, if $y$ is a real in $M$ preceding $z$, then $x\oplus y\notin A$.

  • $x\oplus z\in B$ if and only if it is in $A$, and there is a well-founded countable model $M$ of $V=L$ containing $x$ and $z$, if $y$ is a real in $M$ preceding $z$, then $x\oplus y\notin A$.

The point here is that the countable well-founded models are correct about the $L$-predecesors of the reals that they can see. So we can use any or all of them when verifying that $z$ is least such that some $\Delta^1_2$ property holds. Note that the "for every real $y$ in $M$" is merely a natural number quantifier, since $M$ is coded as a countable structure. So the first of these characterizations is $\Pi^1_2$ and the second is $\Sigma^1_2$, and so it is $\Delta^1_2$ overall.

  • $\begingroup$ Well, that certainly explains why I couldn't prove my claim. :) (I've changed the title of the question, just to avoid future confusion.) Thanks for the clear answer! $\endgroup$ Aug 18, 2013 at 13:21
  • $\begingroup$ I guess the same idea works for $\Delta^1_n$ for any $n$. $\endgroup$ Aug 18, 2013 at 13:34

Assuming $V=L$ then we have $AC$ and $CH$, so every set of reals is at most $\aleph_1$ Suslin. So we can find scales for them and uniformize them.In particular every $\Delta^1_2$ set of reals can be uniformized. As Joel said in the comment above this works for all $\Delta^1_n$ under $V=L$.

  • $\begingroup$ Under $V=L$, Uniformization fails for any $\bf\Pi^1_n$ and $\varPi^1_n$ with $n\ge 2$, but rather surprisingly every lightface nonempty $\varPi^1_n$ set contains a $\varPi^1_n$ singleton by an old result of Harvey Friedman $\endgroup$ Jul 9, 2016 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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