Ramsey’s Theorem on trees and weak Koenig’s Lemma
Date/Time:24 Oct 2019 17:00
Venue: S17 #06-11
Speaker: Yang Yue, National University of Singapore
Ramsey’s Theorem on trees and weak Koenig’s Lemma
Ramsey’s Theorem for Pairs has been studied intensively in reverse mathematics. One of the major breakthroughs is Liu Lu’s 2012 result showing RT-2-2 does not imply WKL-0. Liu’s result not only answered an important question in reverse mathematics, the technique that he used turns out to have wider applications, for example, in Monin and Patey’s separation of SRT-2-2 and RT-2-2.
In this talk, we generalize Liu’s result to tree. Let TT-2-k denote the combinatorial principle stating that every k-coloring of pairs of compatible nodes on the full binary tree has a homogeneous solution, i.e. an infinite perfect tree in which all pairs of compatible nodes have the same color. We show that over the base system RCA-0, TT-2-k doe not imply weak Koenig’s lemma.
This is joint work with Chong Chitat, Li Wei and Liu Lu.
Add to calendar: 
