Models of Bounded Arithmetic and variants of Pigeonhole Principle

2022/08/31 by Mykyta Narusevych, Narusevych, Mykyta · 1 citation
Computer Science · #Computability, Logic, AI Algorithms

paper · pdf · doi:10.48550/arxiv.2208.14713

Abstract

We give elementary proof that theory T¹₂(R) augmented by the weak pigeonhole principle for all Δ^b₁(R)-definable relations does not prove the bijective pigeonhole principle for R. This can be derived from known more general results but our proof yields a model of T¹₂(R) in which ontoPHPⁿ⁺¹_n(R) fails for some nonstandard element n while PHP^m+1_m holds for all Δ^b₁(R)-definable relations and all m ≤ n^1-ε, where ε> 0 is a fixed standard rational parameter. This can be seen as a step towards solving an open question posed by M. Ajtai.

Cited by

• The Proof Analysis Problem

Related

• Pigeons do not jump high
• The reverse mathematics of the pigeonhole hierarchy
• Finite Combinatorics and Fragments of Arithmetic
• The weakness of the pigeonhole principle under hyperarithmetical\n reductions
• On some Σ^B₀-formulae generalizing counting principles over V⁰