Paper Info
Title
Successor-invariant first-order logic on finite structures
Abstract
We consider successor-invariant first-order logic (FO + succ)(inv), consisting of sentences Phi involving an "auxiliary" binary relation S such that (U, S-1) satisfies Phi double left right arrow (D (U, S-2) satisfies Phi for all finite structures U and successor relations S-1, S-2 on U. A successor-invariant sentence Phi has a well-defined semantics on finite structures U with no given successor relation: one simply evaluates Phi on (U. 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].
Year
DOI
Venue
2007
10.2178/jsl/1185803625
JOURNAL OF SYMBOLIC LOGIC
DocType
Volume
Issue
Journal
72
2
ISSN
Citations 
PageRank 
0022-4812
5
0.43
References 
Authors
4
1
Name
Order
Citations
PageRank
Benjamin Rossman129820.00