Logic Seminar

Please note that the time is PST

Given sets X,Y and P⊆X×Y with projX(P)=X, a uniformization of P is a function f:X→Y such that (x,f(x))∈P for all x∈X. If now E is an equivalence relation on X, we say that P is E-invariant if x1Ex2⟹Px1=Px2, where Px={y:(x,y)∈P} is the x-section of P. In this case, an E-invariant uniformization is a uniformization f such that x1Ex2⟹f(x1)=f(x2).

Consider now the situation where X,Y are Polish spaces and P is a Borel subset of X×Y. In this case, standard results in descriptive set theory provide conditions which imply the existence of Borel uniformizations. These fall mainly into two categories: "small section" and "large section" uniformization results.

Suppose now that E is a Borel equivalence relation on X, P is E-invariant, and P has "small" or "large" sections. In this talk, we address the following question: When does there exist a Borel E-invariant uniformization of P?

We show that for a fixed E, every such P admits a Borel E-invariant uniformization iff E is smooth. Moreover, we compute the minimal definable complexity of counterexamples when E is not smooth. Our counterexamples use category, measure, and Ramsey-theoretic methods.

We also consider "local" dichotomies for such pairs (E,P). We give two new proofs of a dichotomy of Miller in the case where P has countable sections, the first using Miller's (G0,H0) dichotomy and Lecomte's ℵ0-dimensional G0 dichotomy, and the second using a new ℵ0-dimensional analogue of the (G0,H0) dichotomy. We also prove anti-dichotomy results for the "large section" case. We discuss the "Kσ section" case, which is still open.

This is joint work with Alexander Kechris.