Functional Projection and Complexity Reduction

Abstract

Törnquist (arXiv:1310.3250) proved that if there exists a ${\mathbf{\Sigma }}_2^1$ maximal almost disjoint (MAD) family, then there exists a ${\mathbf{\Pi }}_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 ${\mathbf{\Pi }}_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 ${\mathbf{\Pi }}_2^1$ relations. As an immediate corollary, we obtain that in $L[U]$ there are ${\mathbf{\Pi }}_2^1$ witnesses for many combinatorial families.

arXiv commentThe new version concerns only minor linguistic changes, and updates of author's affiliation