Conservation Strength of The Infinite Pigeonhole Principle for Trees

2021/10/12 by Chong, Chitat, Wang, Wei, Yang, Yue · 2 citations
#03D80 #03F35 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #Primary 03B30 #Secondary 05D10

paper · doi:10.48550/arxiv.2110.06026

Abstract

Let TT¹ be the combinatorial principle stating that every finite coloring of the infinite full binary tree has a homogeneous isomorphic subtree. Let RT²₂ and WKL₀ denote respectively the principles of Ramsey's theorem for pairs and weak König's lemma. It is proved that TT¹+RT²₂+WKL₀ is Π⁰₃-conservative over the base system RCA₀. Thus over RCA₀, TT¹ and Ramsey's theorem for pairs prove the same Π⁰₃-sentences.

Cited by

• Π⁰₄ conservation of a Carlson-Simpson lemma for 1-variable words
• Finite Combinatorics and Fragments of Arithmetic

Related

• The Strength of Ramsey's Theorem For Pairs over trees: I. Weak König's Lemma
• The strength of Ramsey's theorem for pairs and arbitrarily many colors
• Conservation of Ramsey's theorem for pairs and well-foundedness
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• The reverse mathematics of the pigeonhole hierarchy