Logic Seminar

Damir DzhafarovUniversity of Connecticut
The uniform content of partial and linear orders

Tuesday, September 13, 2016 - 2:55pm
Malott 206

The principle ADS asserts that every linear order on omega 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. I will discuss recent joint work with Astor, Solomon, and Suggs looking at these principles under Weihrauch (uniform) reducibility. For instance, we introduce the principle ADC, which asserts that every such linear order has an infinite ascending or descending chain. This is easily seen to be equivalent to ADS over RCA_0 (even computably equivalent) but we show that ADC is strictly weaker than ADS under Weihrauch 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 General-SADC analogously. We prove that General-SADC 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.