Effective refining of Borel coverings

Abstract:

Given a countable family $(\mathbf {\Gamma }_i)_{i\in I}$ of additive or multiplicative Baire classes ($\mathbf {\Gamma }_i=\mathbf {\Sigma }^0_{\xi _i}$ or $\mathbf {\Pi }^0_{\xi _i}$) we investigate the following complexity problem: Let $(A_i)_{i\in I}$ be a Borel covering of $\omega ^\omega$ and assume that there exists some covering $(B_i)_{i\in I}$ with $B_i\subset A_i$ and $B_i\in \mathbf {\Gamma }_i$ for all $i$; can one find such a family $(B_i)_{i\in I}$ in $\varDelta ^1_1(\alpha )$ where $\alpha \in \omega ^\omega$ is any reasonable code for the families $(A_i)_{i\in I}$ and $(\mathbf {\Gamma }_i)_{i\in I}$? The main result of the paper will give a full characterization of those families $(\mathbf {\Gamma }_i)_{i\in I}$ for which the answer is positive. For example we will show that this is the case if $I$ is finite or if all the Baire classes $\mathbf {\Gamma }_i$ are additive, but in the general case the answer depends on the distribution of the multiplicative Baire classes inside the family $(\mathbf {\Gamma }_i)_{i\in I}$.