This fall we are shorthanded, so we are running logic seminar only every other week. It meets 2:30-3:30 on Thursdays in Kemeny 120.
|Invariance and noninvariance in the lattice of $\Pi^0_1$ classes, part 1|
|Invariance and noninvariance in the lattice of $\Pi^0_1$ classes, part 2|
|In Kemeny 201
An open problem in reverse mathematics and infinitary combinatorics
The complete binary tree T, viewed as a partial ordering, satisfies the following partition property for any finite k: If the nodes of T are colored in k-many colors, then there is a monochromatic subordering isomorphic to T. Chubb, Hirst, and McNicholl call this principle TT^1_k. We will use TT^1 to refer to the principle: TT^1_k holds for all finite k. Chubb, Hirst, and McNicholl showed that, over the usual base theory RCA_0, I\Sigma^0_2 ---> TT^1---> B\Sigma^0_2, and posed the question: What is the precise proof-theoretic strength of TT^1? Corduan, Groszek, and Mileti showed that the right hand arrow above cannot be reversed: B\Sigma^0_2 does not imply TT^1. This separates TT^1 from Ramsey's Theorem for 1-tuples (the pigeonhole principle), which Hirst has shown is equivalent to B\Sigma_0^2. This is in contrast to the situation for triples and above, where the standard Ramsey's Theorem and the binary tree version are equivalent. The precise proof-theoretic strength of TT^1 remains unknown.