Fixed Point vs. First-Order Logic on Finite Ordered Structures with Unary Relations
Data(s) |
12/09/2011
12/09/2011
11/08/1993
|
---|---|
Resumo |
We prove that first order logic is strictly weaker than fixed point logic over every infinite classes of finite ordered structures with unary relations: Over these classes there is always an inductive unary relation which cannot be defined by a first-order formula, even when every inductive sentence (i.e., closed formula) can be expressed in first-order over this particular class. Our proof first establishes a property valid for every unary relation definable by first-order logic over these classes which is peculiar to classes of ordered structures with unary relations. In a second step we show that this property itself can be expressed in fixed point logic and can be used to construct a non-elementary unary relation. NSF (CCR-9113196), Swiss National Science Foundation |
Identificador |
Kfoury, A.J.; Wymann-Boeni, M.. "Fixed Point vs. First-Order Logic on Finite Ordered Structures with Unary Relations", Technical Report BUCS-1993-008, Computer Science Department, Boston University, June 1993. [Available from: http://hdl.handle.net/2144/1471] |
Idioma(s) |
en_US |
Publicador |
Boston University Computer Science Department |
Relação |
BUCS Technical Reports;BUCS-TR-1993-008 |
Tipo |
Technical Report |