6
$\begingroup$

Let $A(X, Y)$ be an arithmetical formula with (only) second-order variables $X, Y\subset \mathbb{N}$.

Assuming $(\forall X\subset \mathbb{N})(\exists Y\subset\mathbb{N})A(X, Y)$, there is a choice function $Z$ such that $(\forall X\subset \mathbb{N})A(X, Z(X))$.

Is there always a measurable such $Z$?

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ Probably you know this, but the keyword is: uniformization. You are asking whether every arithmetic subset of the plane with all slices nonempty is uniformized by a measurable function. There are many theorems in descriptive set theory about the complexity of uniformizing functions in terms of the complexity of the set in the plane. $\endgroup$
    – Joel David Hamkins
    Commented Jul 22 at 14:35
  • 2
    $\begingroup$ It seems to me that the result mentioned in this answer: mathoverflow.net/a/199598/1946 would provide an arithmetic relation $A(x,y)$ with no hyperarithmetic selector. Namely, $A(x,y)$ holds when $y$ is a branch through the tree $T_x$. $\endgroup$
    – Joel David Hamkins
    Commented Jul 22 at 15:43
  • 1
    $\begingroup$ Jankov/von Neumman comes close but the $\sigma$-algebra involved is too big as far as the desired conclusion goes; see also mathoverflow.net/questions/176672/…. Of course, assuming large cardinals we get a positive answer (e.g. projective uniformization + all projective sets are measurable for galactic overkill). $\endgroup$
    – Noah Schweber
    Commented Jul 22 at 19:08
  • 1
    $\begingroup$ Noah's latter example is the same argument (and same user, but different post) as in my link above. $\endgroup$
    – Joel David Hamkins
    Commented Jul 22 at 19:25
  • 1
    $\begingroup$ I think the following is a potential counterexample: let $A(X,Y)\equiv$ "Either $X\not\ge_T0'$ and $Y=\emptyset$ or $X\ge_T\emptyset'$ and $Y'=X$." This is arithmetic (since everything can be expressed in terms of initial segments of $X$ and $Y$), and a selector would have to provide "uniform jump inversion" above $0'$. There are various results saying (at least under a further assumption of degree-invariance) that no such function can be tame in one sense or other; however, I don't offhand know whether nonmeasurability specifically is known to be implied by this (so this is just a comment). $\endgroup$
    – Noah Schweber
    Commented Jul 22 at 19:59

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .