{
  "id": "1605.06164",
  "version": "v1",
  "published": "2016-05-19T22:15:31.000Z",
  "updated": "2016-05-19T22:15:31.000Z",
  "title": "The uniform content of partial and linear orders",
  "authors": [
    "Eric P. Astor",
    "Damir D. Dzhafarov",
    "Reed Solomon",
    "Jacob Suggs"
  ],
  "categories": [
    "math.LO"
  ],
  "abstract": "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. 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 $RCA_0$ 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 $\\omega + \\omega^*$, is not Weihrauch reducible to $ADC$. In this connection, we define a more natural stable form of $ADS$ that we call $General\\text-SADS$, which is the restriction of $ADS$ to linear orders of type $k + \\omega$, $\\omega + \\omega^*$, or $\\omega + 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 $\\omega$ 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 $RCA_0$. Here, we show that $SCAC$ is strictly weaker than $WSCAC$ under even computable reducibility.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-05-19T22:15:31.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear order",
      "uniform content",
      "strictly weaker",
      "second order arithmetic",
      "reverse mathematics literature"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}