# Degree of unsolvability of finding a open approximation to a Borel set, given its Borel code

It is well known that every Borel set has the property of Baire. That is, for every Borel set $B$, there is an open set $U$ and a sequence of dense open sets $D_n$ such that for every $x\in \cap_n D_n$, $x\in B \iff x \in U$.

Also well known: every Borel set can be represented by a Borel code, a well-founded tree whose leaves encode open sets and whose inner nodes designate how to combine them (intersect, union, complement).

Taking a computability-theoretic view, it looks like starting from a Borel code $X$ of height $\alpha$, it will take about $\alpha$-many jumps of $X$ to compute open codes for such sets $U$ and $\{D_n\}_{n\in\omega}$.

Do you know of a reference where this (or the analogous fact, if I missed any detail) is already proved?

Similarly, is there any paper which has already analyzed the reverse math strength of the statement Every Borel set has the Property of Baire''?

For example, let $\alpha$ be a recursive ordinal and $B=\{g\mid g\mbox{ is a }0^{(\alpha)}\mbox{-generic real}\}$. Then $B$ is a hyperarithmetic set and so has a recursive Borel code $X$.
But no real in $B$ is recursive in $0^{(\alpha)}$ and so any open approximation must not be recursive in $0^{(\alpha)}$.
• Liang Yu, thank you for the nice example. It is short and pleasing, but different from what I am looking for in two ways. First, the fact I wish to cite would give the exact degree of unsolvability for each $\alpha$, while this example leaves a few jumps' gap. (The gap can be closed by coding $0^{(\alpha)}$ into the $U$.) Second, I'm looking for a reference, not a proof sketch. When I need to cite folklore, I will generally write up a proof for the sake of the literature's completeness. However, I prefer to hope that someone wrote it already! – Linda Brown Westrick Apr 5 '15 at 0:35