{
  "id": "1910.02489",
  "version": "v1",
  "published": "2019-10-06T18:26:03.000Z",
  "updated": "2019-10-06T18:26:03.000Z",
  "title": "Open sets in computability theory and Reverse Mathematics",
  "authors": [
    "Dag Normann",
    "Sam Sanders"
  ],
  "comment": "32 pages",
  "categories": [
    "math.LO"
  ],
  "abstract": "In computational approaches to mathematics, open sets are generally studied indirectly via countable representations. For instance, an open set of real numbers with discontinuous characteristic function can be represented -or `coded'- by a sequence of open balls with rational center and radius. It is then a natural question whether the introduction of such codes changes the logical and computational properties of basic theorems pertaining to open sets. As we will see, sequential compactness seems unaffected by the use of codes, while (countable) open cover compactness is greatly impacted. Indeed, we identify numerous theorems for which the Main Question of Reverse Mathematics, namely which set existence axioms are necessary for a proving the theorem, does not have an (unique/unambiguous) answer when using the aforementioned characteristic functions in the stead of codes of open sets. In particular, we establish this for the Heine-Borel theorem (for countable covers) and the Heine, Urysohn, and Tietze theorems. We establish similar differences for the computational properties, in the sense of Kleene's S1-S9, of these theorems, namely a shift from `computable' to `not computable in any type two functional'. A finer study of representations of open sets leads to the new `$\\Delta$-functional' which has unique computational properties. Finally, we also study the computational properties of Baire category theorem, resulting in similar results that however require very different proofs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-10-06T18:26:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03B30",
      "03D65",
      "03F35"
    ],
    "keywords": [
      "open set",
      "reverse mathematics",
      "computability theory",
      "set existence axioms",
      "baire category theorem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}