Suppose I am given a subset of $2^\omega\times\omega^\omega$ of some bounded Borel rank. Can I get an analytic uniformization of this set?

  • $\begingroup$ Does analytic uniformization means that graph is an analytical set, or that the map is analytically measurable? $\endgroup$
    – SBF
    Jul 18, 2013 at 20:04
  • $\begingroup$ I think it means that the graph is an analytical set. $\endgroup$ Jul 19, 2013 at 6:39
  • 2
    $\begingroup$ A function with analytic graph is actually a Borel function. To see this, note that $f^{-1}(B)=\pi\big((X\times B)\cap\textrm{Graph} f\big)$, is analytic when $B$ is Borel. But for the same reason, $f^{-1}(B^C)$ is analytic. Since $f^{-1}(B)^C=f^{-1}(B^C)$, this shows that the preimage of a Borel set is both analytic and coanalytic, hence Borel. $\endgroup$ Jul 19, 2013 at 7:46

1 Answer 1


There is an arithmetical set $A\subseteq 2^{<\omega}\times \omega^{<\omega}$ so that for any $x\in 2^{\omega}$, $A(x)=\{\sigma\mid \exists n(x|n,\sigma)\in A\}$ is an $x$-recursive tree which has an infinite path but no infinite path hyperarithmetic in $x$.

Now let $B$ be an arithmetical set so that $(x,y)\in B$ if and only if $y$ is an infinite path through $A(x)$. $B$ has the following property:

(1). For any $x$, there is some $y$ so that $(x, y)\in B$;

(2) No analytic function uniformizing $B$. Suppose not, then there is a real $z$ and $\Sigma^1_1(z)$-function $f$ uniformizing $B$. Let $x\geq_h z$, then $f(x)\leq_h x\oplus z\leq_h x$, a contradiction.

  • $\begingroup$ I assume that the first formula should read $A\subseteq 2^{<\omega}\times\omega^{<\omega}$... Also, does the existence of $A$ follow from some theorem or should it be obvious (sorry, I am not very fluent in descriptive set theory let alone effective descriptive ST). $\endgroup$ Aug 27, 2013 at 15:01
  • $\begingroup$ You are right. I corrected the typo. The existence of $A$ follows from a well known fact that there is a $\Sigma^1_1$ set which does not contain a hyperarithmetic real. $\endgroup$
    – 喻 良
    Aug 27, 2013 at 22:37

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.