The uniform content of partial and linear orders (Q2400498): Difference between revisions

The authors use Weihrauch and computable reducibility to separate combinatorial principles related to \(\text{ADS}\) (ascending/descending sequence), \(\text{CAC}\) (chain/antichain), and their stable versions. The separated principles are provably equivalent in \(\text{RCA}_0\), so the results illustrate how reducibility results can refine the usual reverse mathematical hierarchy. For example, the new principle \(\text{ADC}\) is introduced and shown to be equivalent to \(\text{ADS}\) over \(\text{RCA}_0\). However, \(\text{ADC}\) is strictly weaker than \(\text{ADS}\) under Weihrauch reducibility, denoted \(\text{ADC} <_W \text{ADS}\). Similar results for stable versions include \(\text{SADS} <_W \text{General-SADS} <_W \text{ADS}\), \(\text{SADC} <_W \text{General-SADC} <_W \text{ADC}\), \(\text{SADC} <_W \text{SADS}\), \(\text{General-SADC} <_W \text{General-SADS}\), and \(\text{ADC} <_W \text{ADS}\). For computable reducibility, \(\text{WSCAC} <_W \text{SCAC}\). Versions of these principles appear in work of \textit{D. R. Hirschfeldt} and \textit{R. A. Shore} [J. Symb. Log. 72, No. 1, 171--206 (2007; Zbl 1118.03055)], \textit{D. R. Hirschfeldt} and \textit{C. G. Jockusch jun.} [J. Math. Log. 16, No. 1, Article ID 1650002, 59 p. (2016; Zbl 1373.03068)], \textit{C. G. Jockusch jun.} et al. [J. Symb. Log. 74, No. 2, 693--711 (2009; Zbl 1171.03034)], and in Chapter 9 of \textit{D. R. Hirschfeldt}'s book [Slicing the truth. On the computable and reverse mathematics of combinatorial principles. Hackensack, NJ: World Scientific (2014; Zbl 1304.03001)].