(Extra)Ordinary Equivalences with the Ascending/Descending Sequence Principle

Journal of Symbolic Logic 89 (1):262-307 (2024)
  Copy   BIBTEX

Abstract

We analyze the axiomatic strength of the following theorem due to Rival and Sands [28] in the style of reverse mathematics. Every infinite partial order P of finite width contains an infinite chain C such that every element of P is either comparable with no element of C or with infinitely many elements of C. Our main results are the following. The Rival–Sands theorem for infinite partial orders of arbitrary finite width is equivalent to $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$ over $\mathsf {RCA}_0$. For each fixed $k \geq 3$, the Rival–Sands theorem for infinite partial orders of width $\leq \!k$ is equivalent to $\mathsf {ADS}$ over $\mathsf {RCA}_0$. The Rival–Sands theorem for infinite partial orders that are decomposable into the union of two chains is equivalent to $\mathsf {SADS}$ over $\mathsf {RCA}_0$. Here $\mathsf {RCA}_0$ denotes the recursive comprehension axiomatic system, $\mathsf {I}\Sigma ^0_{2}$ denotes the $\Sigma ^0_2$ induction scheme, $\mathsf {ADS}$ denotes the ascending/descending sequence principle, and $\mathsf {SADS}$ denotes the stable ascending/descending sequence principle. To the best of our knowledge, these versions of the Rival–Sands theorem for partial orders are the first examples of theorems from the general mathematics literature whose strength is exactly characterized by $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$, by $\mathsf {ADS}$, and by $\mathsf {SADS}$. Furthermore, we give a new purely combinatorial result by extending the Rival–Sands theorem to infinite partial orders that do not have infinite antichains, and we show that this extension is equivalent to arithmetical comprehension over $\mathsf {RCA}_0$.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,322

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

Reexamination of the Conditions and Proofs for Impossibility of Infinite Chain.Asgar Dirbaz & Mahmud Seidi - 2014 - Journal of Philosophical Theological Research 15 (60):7-20.
Constructing sequences one step at a time.Henry Towsner - 2020 - Journal of Mathematical Logic 20 (3):2050017.
Non-well-foundedness of well-orderable power sets.T. E. Forster & J. K. Truss - 2003 - Journal of Symbolic Logic 68 (3):879-884.
Non-well-foundedness of well-orderable power sets.T. E. Forster & J. K. Truss - 2003 - Journal of Symbolic Logic 68 (3):879-884.
Exploiting Equivalences in Connection Calculi.Stefan Bruning - 1995 - Logic Journal of the IGPL 3 (6):857-886.
Beyond Mind III: Further Steps to a Metatranspersonal Philosophy and Psychology.Elias Capriles - 2010 - International Journal of Transpersonal Studies 29 (1):1.
Beyond Mind III: Further Steps to a Metatranspersonal Philosophy and Psychology.Elías Capriles - 2009 - International Journal of Transpersonal Studies 28 (2):1-145.
What are the core ideas behind the Precautionary Principle?Erik Persson - 2016 - Science of the Total Environment 557:134–141.
Non‐circular, non‐well‐founded set universes.Athanassios Tzouvaras - 1993 - Mathematical Logic Quarterly 39 (1):454-460.

Analytics

Added to PP
2023-01-05

Downloads
18 (#803,961)

6 months
16 (#147,730)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations