Epsilon-logic is more expressive than first-order logic over finite structures
- 1 December 2000
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 65 (4) , 1749-1757
- https://doi.org/10.2307/2695073
Abstract
There are properties of finite structures that are expressible with the use of Hilbert's ∈-operator in a manner that does not depend on the actual interpretation for ∈-terms. but not expressible in plain first-order. This observation strengthens a corresponding result of Gurevich, concerning the invariant use of an auxiliary ordering in first-order logic over finite structures. The present result also implies that certain non-deterministic choice constructs, which have been considered in database theory, properly enhance the expressive power of first-order logic even as far as deterministic queries are concerned, thereby answering a question raised by Abiteboul and Vianu.Keywords
This publication has 5 references indexed in Scilit:
- Descriptive ComplexityPublished by Springer Nature ,1999
- Expressive power of unary countersPublished by Springer Nature ,1997
- Logical Hierarchies in PTIMEInformation and Computation, 1996
- An optimal lower bound on the number of variables for graph identificationCombinatorica, 1992
- Non-determinism in logic-based languagesAnnals of Mathematics and Artificial Intelligence, 1991