The reverse mathematics of non-decreasing subsequences

Archive for Mathematical Logic 56 (5-6):491-506 (2017)
  Copy   BIBTEX

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.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 103,401

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
The Thin Set Theorem for Pairs Implies DNR.Brian Rice - 2015 - Notre Dame Journal of Formal Logic 56 (4):595-601.
Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
The polarized Ramsey’s theorem.Damir D. Dzhafarov & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (2):141-157.
Regressive versions of Hindman’s theorem.Lorenzo Carlucci & Leonardo Mainardi - 2024 - Archive for Mathematical Logic 63 (3):447-472.
On the Indecomposability of $\omega^{n}$.Jared R. Corduan & François G. Dorais - 2012 - Notre Dame Journal of Formal Logic 53 (3):373-395.

Analytics

Added to PP
2017-08-04

Downloads
25 (#921,682)

6 months
7 (#469,699)

Historical graph of downloads
How can I increase my downloads?