Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T09:42:37.301Z Has data issue: false hasContentIssue false

Epsilon-logic is more expressive than first-order logic over finite structures

Published online by Cambridge University Press:  12 March 2014

Martin Otto*
Affiliation:
Department of Computer Science, University of Wales, Swansea, Swansea SA2 8PP, UK, E-mail:m.otto@swan.ac.uk

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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable