Non-analytically measurable set in $\Delta^1_2$

Question

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.

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.)