Fixed Point vs. First-Order Logic on Finite Ordered Structures with Unary Relations
Assaf J. Kfoury, M. Wymann-Boeni · 1993
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. 1 Introduction In this paper we are concerned with a questions about finite structures for a signature \\Sigma = f; R 1 ; : : : ; R l g, where has to be realized as a total order and the predicate symbols R j are all unary. Partly supported by NSF grant CCR-9113196. ...