\Delta^1_1 Effectivization in Borel Combinatorics

arXiv2105.04063MaRDI QIDQ6367223FDOQ6367223

Authors: Riley Thornton 

Publication date: 9 May 2021

Abstract: We develop a flexible method for showing that Borel witnesses to some combinatorial property of $Delt{a}_1^1$ objects yield $Delt{a}_1^1$ witnesses. We use a modification the Gandy--Harrington forcing method of proving dichotomies, and we can recover the complexity consequences of many known dichotomies with short and simple proofs. Using our methods, we give a simplified proof that smooth $Delt{a}_1^1$ equivalence relations are $Delt{a}_1^1$-reducible to equality; we prove effective versions of the Lusin--Novikov and Feldman--Moore theorems; we prove new effectivization results related to dichotomy theorems due to Hjorth and Miller (originally proven using ``forceless, ineffective, and powerless" methods); and we prove a new upper bound on the complexity of the set of Schreier graphs for $mathbb{Z}^2$ actions. We also prove an equivariant version of the $G_0$ dichotomy that implies some of these new results and a dichotomy for graphs induced by Borel actions of $mathbb{Z}^2$.

Mathematics Subject Classification ID

Descriptive set theory (03E15)

This page was built for publication: $\Delta^1_1$ Effectivization in Borel Combinatorics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367223)