Milliken's tree theorem and computability theory

Abstract: Milliken's tree theorem is a powerful combinatorial result that generalized Ramsey's theorem and many other familiar partition results. I will present recent work on the effective and proof-theoretic strength of this theorem, which was originally motivated by a question of Dobrinen. The main result is a complete characterization of Milliken's tree theorem in terms of reverse mathematics and the usual computability-theoretic hierarchies, along with several applications to other combinatorial problems. Key to this is a new inductive proof of Milliken's tree theorem, employing an effective version of the Halpern-Lauchli theorem. This is joint work with Angles d'Auriac, Cholak, Monin, and Patey.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic