{
  "id": "1909.01697",
  "version": "v1",
  "published": "2019-09-04T11:16:40.000Z",
  "updated": "2019-09-04T11:16:40.000Z",
  "title": "Efficient elimination of Skolem functions in first-order logic without equality",
  "authors": [
    "Ján Komara"
  ],
  "comment": "20 pages",
  "categories": [
    "math.LO",
    "cs.LO"
  ],
  "abstract": "We prove that elimination of a single Skolem function in pure logic increases the length of cut-free proofs only linearly. The result is shown for a variant of sequent calculus with Henkin constants instead of free variables.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-09-04T11:16:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03F03",
      "03F20",
      "F.4.1"
    ],
    "keywords": [
      "efficient elimination",
      "first-order logic",
      "single skolem function",
      "pure logic increases",
      "henkin constants"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}