Successor-invariant first-order logic on finite structures
Benjamin Rossman · Journal of Symbolic Logic · 2007
Abstract We consider successor-invariant first-order logic (FO + succ) inv , consisting of sentences Φ involving an “auxiliary” binary relation S such that ( , S 1 ) ⊨ Φ ⇔ ( , S 2 ) ⊨ Φ for all finite structures and successor relations S 1 , S 2 on . A successor-invariant sentence Φ has a well-defined semantics on finite structures with no given successor relation: one simply evaluates Φ on ( , S ) for an arbitrary choice of successor relation S . In this article, we prove that (FO + succ) inv is more expressive on finite structures than first-order logic without a successor relation. This extends similar results for order-invariant logic [8] and epsilon-invariant logic [10].