Descriptive complexity of countable unions of Borel rectangles

Abstract

We give, for each countable ordinal $\xi \ge 1$, an example of a ${\mathbf{\Delta }}_2^0$ countable union of Borel rectangles that cannot be decomposed into countably many ${\mathbf{\Pi }}_{\xi }^0$ rectangles. In fact, we provide a graph of a partial injection with disjoint domain and range, which is a difference of two closed sets, and which has no ${\mathbf{\Delta }}_{\xi }^0$-measurable countable coloring.