Descriptive complexity of countable unions of Borel rectangles

We give, for each countable ordinal $\xi!\geq! 1$, an example of a ${\bf\Delta}^0_2$ countable union of Borel rectangles that cannot be decomposed into countably many ${\bf\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 ${\bf\Delta}^0_\xi$-measurable countable coloring.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00852718
Author Lecomte, Dominique, Zeleny, Miroslav
Maintainer CCSD
Last Updated May 10, 2026, 01:44 (UTC)
Created May 10, 2026, 01:44 (UTC)
Identifier hal-00852718
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Institut de Mathématiques de Jussieu (IMJ) ; Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
creator Lecomte, Dominique
date 2013-08-20T00:00:00
harvest_object_id fa2a13b4-d637-4ad8-98c8-fcd031af3180
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-03-12T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1308.4540
set_spec type:UNDEFINED