The reverse mathematics of non-decreasing subsequences

DOI10.1007/S00153-017-0536-9MaRDI QIDQ2402955zbMATH OpenOpenAlexFDO

Authors Ludovic Patey

Publication date 15 September 2017

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.08833

zbMATH Keywords

reverse mathematicsRamsey's theoremnon-decreasing subsequence

Mathematics Subject Classification ID

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

Abstract: Every function over the natural numbers has an infinite subdomain on which the function is non-decreasing. Motivated by a question of Dzhafarov and Schweber, we study the reverse mathematics of variants of this statement. It turns out that this statement restricted to computably bounded functions is computationally weak and does not imply the existence of the halting set. On the other hand, we prove that it is not a consequence of Ramsey's theorem for pairs. This statement can therefore be seen as an arguably natural principle between the arithmetic comprehension axiom and stable Ramsey's theorem for pairs.

Recommendations

• Derived sequences and reverse mathematics
• On some new results for non-decreasing sequences
• A new application of non-increasing sequences
• The surprising mathematics of longest increasing subsequences
• Nondecreasing subsequences of t-sequences
• scientific article; zbMATH DE number 5204618
• (Near-)inverses of sequences
• Algebraic aspects of increasing subsequences
• Nonrepetitive sequences on arithmetic progressions
• Reverse mathematics and Ramsey properties of partial orderings

Cites work

• Algorithmic randomness and complexity.
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Cone avoiding closed sets
• Iterative forcing and hyperimmunity in reverse mathematics
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• On the strength of Ramsey's theorem for pairs
• Ramsey's theorem and cone avoidance
• Some Questions in Computable Mathematics
• Subsystems of second order arithmetic
• The atomic model theorem and type omitting
• Weihrauch degrees, omniscience principles and weak computability
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(2)

• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• Comparing the strength of diagonally nonrecursive functions in the absence of \(\Sigma_2^0\) induction

Describes a project that uses

Uses Software

• MathOverflow

This page was built for publication: The reverse mathematics of non-decreasing subsequences

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