The reverse mathematics of non-decreasing subsequences

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


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.



    Upload a copy of this work     Papers currently archived: 92,347

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

The Dirac delta function in two settings of Reverse Mathematics.Sam Sanders & Keita Yokoyama - 2012 - Archive for Mathematical Logic 51 (1-2):99-121.
Dominating the Erdős–Moser theorem in reverse mathematics.Ludovic Patey - 2017 - Annals of Pure and Applied Logic 168 (6):1172-1209.
Questioning Constructive Reverse Mathematics.I. Loeb - 2012 - Constructivist Foundations 7 (2):131-140.
Degrees bounding principles and universal instances in reverse mathematics.Ludovic Patey - 2015 - Annals of Pure and Applied Logic 166 (11):1165-1185.
Reverse-engineering Reverse Mathematics.Sam Sanders - 2013 - Annals of Pure and Applied Logic 164 (5):528-541.
Open questions in reverse mathematics.Antonio Montalbán - 2011 - Bulletin of Symbolic Logic 17 (3):431-454.
Reverse Mathematics and Grundy colorings of graphs.James H. Schmerl - 2010 - Mathematical Logic Quarterly 56 (5):541-548.
Reverse mathematics: the playground of logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
Reverse mathematics of separably closed sets.Jeffry L. Hirst - 2006 - Archive for Mathematical Logic 45 (1):1-2.
Reverse mathematics of prime factorization of ordinals.Jeffry L. Hirst - 1999 - Archive for Mathematical Logic 38 (3):195-201.
Reverse Mathematics and Ordinal Multiplication.Jeffry L. Hirst - 1998 - Mathematical Logic Quarterly 44 (4):459-464.


Added to PP

10 (#1,199,473)

6 months
6 (#530,399)

Historical graph of downloads
How can I increase my downloads?