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 I∑02 + ADS over RCA0. For each fixed k > 3, the Rival Sands theorem for infinite partial orders of width ≤ k is equivalent to ADS over RCA0. The Rival Sands theorem for infinite partial orders that are decomposable into the union of two chains is equivalent to SADS over RCA0. Here RCA0 denotes the recursive comprehension axiomatic system, I∑02 denotes the ∑02 induction scheme, ADS denotes the ascending/descending sequence principle, and SADS denotes the stable ascending/descending sequence principle. To 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 I∑02 + ADS, by ADS, and by 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 RCA0.

(Extra)ordinary equivalences with the ascending/descending sequence principle

Marcone Alberto;
2022-01-01

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 I∑02 + ADS over RCA0. For each fixed k > 3, the Rival Sands theorem for infinite partial orders of width ≤ k is equivalent to ADS over RCA0. The Rival Sands theorem for infinite partial orders that are decomposable into the union of two chains is equivalent to SADS over RCA0. Here RCA0 denotes the recursive comprehension axiomatic system, I∑02 denotes the ∑02 induction scheme, ADS denotes the ascending/descending sequence principle, and SADS denotes the stable ascending/descending sequence principle. To 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 I∑02 + ADS, by ADS, and by 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 RCA0.
File in questo prodotto:
File Dimensione Formato  
RSpo JSL.pdf

accesso aperto

Descrizione: versione finale
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 530.82 kB
Formato Adobe PDF
530.82 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1239918
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact