(EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE

DOI10.1017/JSL.2022.92arXiv2107.02531OpenAlexW3182110633MaRDI QIDQ6203557FDOQ6203557

Authors: Marta Fiori-Carones, Alberto Marcone, Paul Shafer, Giovanni Soldà 

Publication date: 5 April 2024

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: We analyze the axiomatic strength of the following theorem due to Rival and Sands 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 $mathsfISigm{a}_2^0+mathsfADS$ over $mathsf{RCA}_0$. For each fixed $kgeq3$, the Rival-Sands theorem for infinite partial orders of width $leq!k$ is equivalent to $mathsfADS$ over $mathsf{RCA}_0$. The Rival-Sands theorem for infinite partial orders that are decomposable into the union of two chains is equivalent to $mathsfSADS$ over $mathsf{RCA}_0$. Here $mathsf{RCA}_0$ denotes the recursive comprehension axiomatic system, $mathsfISigm{a}_2^0$ denotes the $Sigm{a}_2^0$ induction scheme, $mathsfADS$ denotes the ascending/descending sequence principle, and $mathsfSADS$ 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 $mathsfISigm{a}_2^0+mathsfADS$, by $mathsfADS$, and by $mathsfSADS$. 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$.

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

zbMATH Keywords

partial ordersRamsey theorycomputability theoryrecursion theoryreverse mathematicssecond-order arithmetic

Mathematics Subject Classification ID

Partial orders, general (06A06) Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Second- and higher-order arithmetic and fragments (03F35)

Cites Work

• Subsystems of second order arithmetic
• An Effective Version of Dilworth's Theorem
• Title not available (Why is that?)
• Reverse mathematics, well-quasi-orders, and Noetherian spaces
• Reverse mathematics and initial intervals
• Title not available (Why is that?)
• A Theorem on Hypersimple Sets
• The maximal linear extension theorem in second order arithmetic
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• On the strength of Ramsey's theorem for pairs
• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
• Separating principles below Ramsey's theorem for pairs
• On the strength of Ramsey's theorem
• Title not available (Why is that?)
• On the strength of König's duality theorem for infinite bipartite graphs
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• On the uniform computational content of Ramsey's theorem
• Title not available (Why is that?)
• The inductive strength of Ramsey's theorem for pairs
• Proof mining and combinatorics. Program extraction for Ramsey's theorem for pairs
• On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
• On the Adjacency of Vertices to the Vertices of an Infinite Subgraph
• Cone avoiding closed sets
• The strength of Ramsey's theorem for pairs and arbitrarily many colors
• Partial orders and immunity in reverse mathematics
• An inside/outside Ramsey theorem and recursion theory

This page was built for publication: (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE

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