{
  "id": "2011.03386",
  "version": "v1",
  "published": "2020-11-06T14:34:15.000Z",
  "updated": "2020-11-06T14:34:15.000Z",
  "title": "Computing sets from all infinite subsets",
  "authors": [
    "Noam Greenberg",
    "Matthew Harrison-Trainor",
    "Ludovic Patey",
    "Dan Turetsky"
  ],
  "comment": "30 pages",
  "categories": [
    "math.LO"
  ],
  "abstract": "A set is introreducible if it can be computed by every infinite subset of itself. Such a set can be thought of as coding information very robustly. We investigate introreducible sets and related notions. Our two main results are that the collection of introreducible sets is $\\Pi^1_1$-complete, so that there is no simple characterization of the introreducible sets; and that every introenumerable set has an introreducible subset.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-11-06T14:34:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "infinite subset",
      "computing sets",
      "introreducible sets",
      "main results",
      "simple characterization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}