{
  "id": "2203.05250",
  "version": "v2",
  "published": "2022-03-10T09:28:04.000Z",
  "updated": "2022-09-14T19:34:15.000Z",
  "title": "On the computational properties of basic mathematical notions",
  "authors": [
    "Dag Normann",
    "Sam Sanders"
  ],
  "comment": "44 pages, to appear in the Journal of Logic and Computation",
  "categories": [
    "math.LO",
    "cs.LO"
  ],
  "abstract": "We investigate the computational properties of basic mathematical notions pertaining to $\\mathbb{R}\\rightarrow \\mathbb{R}$-functions and subsets of $\\mathbb{R}$, like finiteness, countability, (absolute) continuity, bounded variation, suprema, and regularity. We work in higher-order computability theory based on Kleene's S1-S9 schemes. We show that the aforementioned italicised properties give rise to two huge and robust classes of computationally equivalent operations, the latter based on well-known theorems from the mainstream mathematics literature. As part of this endeavour, we develop an equivalent $\\lambda$-calculus formulation of S1-S9 that accommodates partial objects. We show that the latter are essential to our enterprise via the study of countably based and partial functionals of type $3$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-09-14T19:34:15.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D55",
      "03D75",
      "F.1.1"
    ],
    "keywords": [
      "basic mathematical notions",
      "computational properties",
      "higher-order computability theory",
      "kleenes s1-s9 schemes",
      "mainstream mathematics literature"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 44,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}