Successor-invariant first-order logic on finite structures


Journal Article

We consider successor-invariant first-order logic (FO + succ) inv, consisting of sentences Φ involving an "auxiliary" binary relation S such that (Θ, S1) |= Φ ⇔ (Θ, S2) |= Φ for all finite structures Θ and successor relations S1, S2 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]. © 2007, Association for Symbolic Logic.

Full Text

Duke Authors

Cited Authors

  • Rossman, B

Published Date

  • June 1, 2007

Published In

Volume / Issue

  • 72 / 2

Start / End Page

  • 601 - 618

International Standard Serial Number (ISSN)

  • 0022-4812

Digital Object Identifier (DOI)

  • 10.2178/jsl/1185803625

Citation Source

  • Scopus