We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, originating in the work of W.V. Quine. We show that the satisfiability problem for this fragment has non-elementary complexity, thus refuting an earlier published claim by W.C. Purdy that it is in NExpTime. More precisely, we consider FLm, the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all m ≥ 1. We show that, for m ≥ 2, this sub-fragment forces m/2-tuply exponentially large models, and that its satisfiability problem is m/2-NExpTime-hard. We further establish that, for m ≥ 3, any satisfiable FLm-formula has a model of at most (m-2)-tuply exponential size, whence the satisfiability (= finite satisfiability) problem for this fragment is in (m-2)-NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for FLm for all m ≤4.
|Number of pages||29|
|Journal||The Journal of Symbolic Logic|
|Early online date||6 Jun 2019|
|Publication status||Published - 16 Sep 2019|
- first-order logic
- fluted fragment