{
  "id": "1410.3649",
  "version": "v1",
  "published": "2014-10-14T11:20:29.000Z",
  "updated": "2014-10-14T11:20:29.000Z",
  "title": "Categorical characterizations of the natural numbers require primitive recursion",
  "authors": [
    "Leszek Aleksander Kołodziejczyk",
    "Keita Yokoyama"
  ],
  "comment": "17 pages",
  "categories": [
    "math.LO"
  ],
  "abstract": "Simpson and the second author asked whether there exists a characterization of the natural numbers by a second-order sentence which is provably categorical in the theory RCA$^*_0$. We answer in the negative, showing that for any characterization of the natural numbers which is provably true in WKL$^*_0$, the categoricity theorem implies $\\Sigma^0_1$ induction. On the other hand, we show that RCA$^*_0$ does make it possible to characterize the natural numbers categorically by means of a set of second-order sentences. We also show that a certain $\\Pi^1_2$-conservative extension of RCA$^*_0$ admits a provably categorical single-sentence characterization of the naturals, but each such characterization has to be inconsistent with RCA$^*_0$+supexp.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-10-14T11:20:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03B30",
      "03F35",
      "03B15",
      "03H15",
      "03C62"
    ],
    "keywords": [
      "natural numbers",
      "categorical characterizations",
      "primitive recursion",
      "second-order sentence",
      "categoricity theorem implies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1410.3649A"
    }
  }
}