Epsilon-logic is more expressive than first-order logic over finite structures
Epsilon-logic is more expressive than first-order logic over finite structures
复制标题
Epsilon 逻辑在有限结构上比一阶逻辑更具表现力
DOI：
10.2307/2695073
复制
发表时间：
2000
影响因子：
0.6
通讯作者：
M. Otto
中科院分区：
文献类型：
--
作者：
M. Otto
摘要有限结构的某些性质可以使用Hilbert ∈-算子以不依赖于∈-项的实际解释的方式来表达。但不能用简单的一阶表示。这一观察加强了古列维奇的相应结果，关于一阶逻辑在有限结构上辅助序的不变使用。目前的结果还意味着，某些非确定性的选择结构，这已被认为是在数据库理论，适当地提高了一阶逻辑的表达能力，即使就确定性查询而言，从而回答了Abiteboul和Vianu提出的问题。
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.