Partial impredicativity in reverse mathematics

DOI10.2178/JSL.7802070MaRDI QIDQ5300073zbMATH OpenOpenAlexFDO

Authors Henry Towsner

Publication date 24 June 2013

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.6063, https://projecteuclid.org/euclid.jsl/1368627060

zbMATH Keywords

ATRHoward-Bachman ordinalimpredicativityMenger's theoremNash-Williams theoremproof-theoretic ordinalquasi-orderingreverse mathematicstransfinite induction

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35)

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 $P{i}_2^1$ 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.

Recommendations

• Proof-theoretic investigations on Kruskal's theorem
• Ordinal inequalities, transfinite induction, and reverse mathematics
• scientific article; zbMATH DE number 3924748
• Reverse Mathematics and Ordinal Multiplication
• Well-Ordering Principles in Proof Theory and Reverse Mathematics
• scientific article; zbMATH DE number 2236636
• Comparing DNR and WWKL
• Weak and strong versions of effective transfinite recursion
• Nonstandard Arithmetic and Reverse Mathematics
• What is effective transfinite recursion in reverse mathematics?

Cites work

• An effective proof that open sets are Ramsey
• Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen
• Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\)
• On the strength of Ramsey's theorem for pairs
• Proof-theoretic investigations on Kruskal's theorem
• Subsystems of second order arithmetic

Cited in

(11)

• The computational strength of matchings in countable graphs
• The reverse mathematics of wqos and bqos
• Finding paths through narrow and wide trees
• Degrees bounding principles and universal instances in reverse mathematics
• Bishop-Style Constructive Reverse Mathematics
• HOW STRONG ARE SINGLE FIXED POINTS OF NORMAL FUNCTIONS?
• Comparing DNR and WWKL
• Well ordering principles for iterated \(\Pi^1_1\)-comprehension
• Searching problems above arithmetical transfinite recursion
• Fraïssé's conjecture, partial impredicativity and well-ordering principles. I
• On some subtheories of strong dependent choice

This page was built for publication: Partial impredicativity in reverse mathematics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300073)