The uniform content of partial and linear orders
The principle ADS asserts that every linear order on ω has an infinite ascending or descending sequence. This has been studied extensively in the reverse mathematics literature, beginning with the work of Hirschfeldt and Shore. We introduce the principle ADC, which asserts that linear order has an infinite ascending or descending chain. The two are easily seen to be equivalent over the base system RCA0 of second order arithmetic; they are even computably equivalent. However, we prove that ADC is strictly weaker than ADS under Weihrauch (uniform) reducibility. In fact, we show that even the principle SADS, which is the restriction of ADS to linear orders of type ω+ω∗, is not Weihrauch reducible to ADC. In this connection, we define a more natural stable form of ADS that we call General-SADS, which is the restriction of ADS to linear orders of type k+ω, ω+ω∗, or ω+k, where k is a finite number. We define GeneralSADC analogously. We prove that GeneralSADC is not Weihrauch reducible to SADS, and so in particular, each of SADS and SADC is strictly weaker under Weihrauch reducibility than its general version. Finally, we turn to the principle CAC, which asserts that every partial order on ω has an infinite chain or antichain. This has two previously studied stable variants, SCAC and WSCAC, which were introduced by Hirschfeldt and Jockusch, and by Jockusch, Kastermans, Lempp, Lerman, and Solomon, respectively, and which are known to be equivalent over RCA0. Here, we show that SCAC is strictly weaker than WSCAC under even computable reducibility.
