Functional Projection and Complexity Reduction
Vera Fischer, Yurii Khomskii, Yipu Li, Julia Millhouse

Abstract:
Törnquist (arXiv:1310.3250) proved that if there exists a Σ^1_2 maximal almost disjoint (MAD) family, then there exists a Π^1_1 MAD family. Since then, several other "complexity reduction" proofs have been found for other combinatorial objects, such as maximal independent families or ultrafilters. All of these proofs have relied on Π^1_1-uniformization, so they did not easily lift to higher projective levels. In this paper, we introduce a principle weaker than Uniformization which we call "Functional Projection", and show that this principle is sufficient for most complexity reduction proofs. On the other hand, we prove that in L[U], the canonical inner model for a measurable cardinal, Functional Projection holds for Π^1_2 relations. As an immediate corollary, we obtain that in L[U] there are Π^1_2 witnesses for many combinatorial families.