I'm wondering if there is some reference you may know that gives an explicit set which is not analytically-measurable (i.e., not in the sigma-algebra generated by $\Sigma^1_1$), but which is in $\Delta^1_2$? I can prove that such a set exists but just wondering if there's a (fairly) concrete example.

  • 1
    $\begingroup$ Are you sure you wrote the question correctly? There is some awkward double negation in there, and that question seems different from what is mentioned in the title of the question. $\endgroup$
    – Wojowu
    Jun 18 at 20:33
  • $\begingroup$ @Wojowu Sorry, corrected! $\endgroup$
    – John Levy
    Jun 18 at 21:42
  • $\begingroup$ Not a genuine example but a conditional one: If $V=L$ then there is a $\Delta^1_2$ well-ordering of the reals with order-type $\omega_1$. Such a well-ordering, as a subset of $\mathbb R^2$, is not Lebesgue measurable and therefore not in the $\sigma$-algebra generated by analytic sets. $\endgroup$ Jun 18 at 22:22

1 Answer 1


You write:

I can prove that such a set exists but just wondering if there's a (fairly) concrete example.

The following might just be the proof you allude to, but I think it is fairly concrete:

A set $X$ is analytically-measurable iff it has a code of a particular form - namely, say that a $\sigma\Sigma^1_1$-code is a labelled tree $T$ such that

  • $T$ is a well-founded subtree of $\omega^{<\omega}$,

  • each terminal node of $T$ is labelled with either a $\Sigma^1_1$ or $\Pi^1_1$ set, and

  • each non-terminal node is labelled with either $\bigwedge$ or $\bigvee$.

There is a natural way to evaluate a $\sigma\Sigma^1_1$-code $T$, that is, a function $\mathsf{eval}$ from $\sigma\Sigma^1_1$-codes to analytically-measurable sets; crucially, the set of $\sigma\Sigma^1_1$-codes and the relation "$x\in\mathsf{eval}(T)$" are each $\Delta^1_2$ (indeed much better than that). This lets us directly diagonalize; fixing some (relatively-)low-complexity bijection $b$ between $\sigma\Sigma^1_1$-codes and reals, the set $$\mathscr{D}=\{x:x\not\in \mathsf{eval}(b(x))\}$$ is $\Delta^1_2$ and not analytically-measurable.

(Note that the above assumes a small amount of choice, specifically in assuming that all analytically measurable sets actually have $\sigma\Sigma^1_1$-codes; this issue is analogous to the need for choice to make the various notions of "Borel" coincide. See here for more on this.)


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.