There is no bound on Borel classes of graphs in the Luzin–Novikov theorem
Volume 576 / 2022
Abstract
We show that for every ordinal there is a closed set F^* \subset 2^\omega \times \omega^\omega such that for every x \in 2^\omega the section \{y\in \omega^\omega;\, (x,y) \in F^*\} is a two-point set and F^* cannot be covered by countably many graphs B(n) \subset 2^\omega \times \omega^\omega of functions of the variable x \in 2^\omega such that each B(n) is in the additive Borel class \boldsymbol{\Sigma}^0_\alpha. This rules out the possibility to have a quantitative version of the Luzin–Novikov theorem. The construction is a modification of the method of Harrington, who invented it to show that there exists a countable \Pi^0_1 set in \omega^\omega containing a nonarithmetic singleton. By another application of the same method we get closed sets excluding a quantitative version of the Saint Raymond theorem on Borel sets with \sigma-compact sections.