Finite Combinatorics and Fragments of Arithmetic

2025/06/22 by Wang, Wei
#03C20 #03F30 #03H15 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2506.17943

Abstract

In fragments of first order arithmetic, definable maps on finite domains could behave very differently from finite maps. Here combinatorial properties of Σ_n+1-definable maps on finite domains are compared in the absence of BΣ_n+1. It is shown that GPHP(Σ_n+1) (the Σ_n+1-instance of Kaye's General Pigeonhole Principle) lies strictly between CARD(Σ_n+1) and WPHP(Σ_n+1) (Weak Pigeonhole Principle for Σ_n+1-maps), and also that FRT(Σ_n+1) (Finite Ramsey's Theorem for Σ_n+1-maps) does not imply WPHP(Σ_n+1).

Citations

• Conservation of Ramsey's theorem for pairs and well-foundedness
• Conservation Strength of The Infinite Pigeonhole Principle for Trees
• Where Pigeonhole Principles meet König Lemmas

Related

• Arithmetic, First-Order Logic, and Counting Quantifiers
• Finite Sets and Counting
• Finite field models in additive combinatorics
• A Context for Paris-Harrington Combinatorial Principle
• Models of Bounded Arithmetic and variants of Pigeonhole Principle