An independence of the MIN principle from the PHP principle

2024/06/21 by Narusevych, Mykyta · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2406.14930

Abstract

The minimization principle \textsfMIN(\triangleleft) studied in bounded arithmetic says that a strict linear ordering \triangleleft on any finite interval [0,…,n) has the minimal element. We shall prove that bounded arithmetic theory \textsfT¹₂(\triangleleft) augmented by instances of the pigeonhole principle for all Δ^b₁(\triangleleft) formulas does not prove \textsfMIN(\triangleleft).

Cited by

• The Proof Analysis Problem

Related

• Minimal element theorems revisited
• Models of Bounded Arithmetic and variants of Pigeonhole Principle
• Bounds on Successive Minima of Orders in Number Fields and Scrollar Invariants of Curves
• A one-line proof of a minimax theorem (for a notion of curvature on finite graphs)
• A strong min-max property for level sets of Phase Transitions