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


Abstract in English

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 $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 our knowledge, the

Download