Math @ Duke

Publications [#348704] of Benjamin Rossman
Papers Published
 Rossman, B, Successorinvariance in the finite,
Proceedings Symposium on Logic in Computer Science
(January, 2003),
pp. 148157
(last updated on 2022/05/21)
Abstract: A firstorder sentence θ of vocabulary σ {S} is successorinvariant in the finite if for every finite σstructure M and successor relations S1 and S2 on M, (M, S1) = θ ⇔ (M, S2) = θ. In this paper I give an example of a nonfirstorder definable class of finite structures which is, however, defined by a successorinvariant firstorder sentence. This strengthens a corresponding result for orderinvariance in the finite, due to Y. Gurevich.


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

