Math @ Duke

Publications [#348699] of Benjamin Rossman
Papers Published
 Rossman, B, Successorinvariant firstorder logic on finite structures,
Journal of Symbolic Logic, vol. 72 no. 2
(June, 2007),
pp. 601618 [doi]
(last updated on 2023/06/07)
Abstract: We consider successorinvariant firstorder 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 successorinvariant sentence Φ has a welldefined 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 firstorder logic without a successor relation. This extends similar results for orderinvariant logic [8] and epsiloninvariant logic [10]. © 2007, Association for Symbolic Logic.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

