Partial Impredicativity in Reverse Mathematics

2011/06/29 by Towsner, Henry · 1 citation
#FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1106.6063

Abstract

In reverse mathematics, is is possible to have a curious situation where we know that an implication does not reverse, but appear to have no information on on how to weaken the assumption while preserving the conclusion. A main cause of this phenomenon is the proof of a Π¹₂ sentence from the theory \Pioo. Using methods based on the functional interpretation, we introduce a family of weakenings of \Pioo and use them to give new upper bounds for the Nash-Williams Theorem of wqo theory and Menger's Theorem for countable graphs.

Cited by

• Generalized Higman's Theorem and iterated ideals

Related

• Fraïssé's conjecture, partial impredicativity and well-ordering principles, part I
• Partial orders and immunity in reverse mathematics
• Well-Ordering Principles in Proof Theory and Reverse Mathematics
• On robust theorems due to Bolzano, Weierstrass, Cantor, and Jordan
• On the Use of Impredicative Reasoning to Construct a Class of Partial Models of ZF Within ZF [Withdrawn]