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$ – Ilya Jul 18 '13 at 20:04
  • $\begingroup$ I think it means that the graph is an analytical set. $\endgroup$ – jonathanverner Jul 19 '13 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$ – Michael Greinecker Jul 19 '13 at 7:46

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$ – jonathanverner Aug 27 '13 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 '13 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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