Title: Fixed Point vs. First-Order Logic on Finite Ordered Structures with Unary Relations 
Name: A. J. Kfoury and M. Wymann-Boeni, Boston University 
Date: August 1993


Abstract:

We prove that first order logic is strictly weaker than fixed point logic
over every infinite classes of finite ordered structures with additional
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.