Conservation Strength of The Infinite Pigeonhole Principle for Trees

Abstract

Let ${\mathsf{TT}}^1$ be the combinatorial principle stating that every finite coloring of the infinite full binary tree has a homogeneous isomorphic subtree. Let ${\mathsf{RT}}_2^2$ and ${\mathsf{WKL}}_0$ denote respectively the principles of Ramsey's theorem for pairs and weak König's lemma. It is proved that ${\mathsf{TT}}^1+{\mathsf{RT}}_2^2+{\mathsf{WKL}}_0$ is ${\Pi }_3^0$-conservative over the base system ${\mathsf{RCA}}_0$. Thus over ${\mathsf{RCA}}_0$, ${\mathsf{TT}}^1$ and Ramsey's theorem for pairs prove the same ${\Pi }_3^0$-sentences.

20 pages