Epsilon-logic is more expressive than first-order logic over finite structures (Q2710605)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Epsilon-logic is more expressive than first-order logic over finite structures |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Epsilon-logic is more expressive than first-order logic over finite structures |
scientific article |
Statements
Epsilon-logic is more expressive than first-order logic over finite structures (English)
0 references
24 April 2001
0 references
invariant sentences
0 references
Hilbert's \(\varepsilon\)-operator
0 references
finite structures
0 references
choice
0 references
database
0 references
0.8736102
0 references
0 references
0.85395443
0 references
0.85206825
0 references
0 references
0.8359037
0 references
0 references
The author considers the extension \(\text{FO}[\varepsilon]\) of first-order logic by means of Hilbert's \(\varepsilon\)-operator. Let \(\text{FO}[\varepsilon]_{\text{inv}}\) denote the set of \(\text{FO}[\varepsilon]\)-formulas whose semantics does not depend on the actual interpretation of the choice operator on finite structures. The author shows that there is a property of finite structures which is not \(\text{FO}\)- but \(\text{FO}[\varepsilon]_{\text{inv}}\)-definable. At the same time he shows that a similar result applies to some choice constructs considered in database theory.
0 references
