Descriptive complexity of countable unions of Borel rectangles

Abstract

We give, for each countable ordinal xi > 0, an example of a Delta(0)(2) countable union of Borel rectangles that cannot be decomposed into countably many Pi(0)(xi) 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 Delta(0)(xi)-measurable countable coloring.

Keywords

• Borel chromatic number
• Borel class
• Coloring
• Rectangle