Scholars@Duke

Successor-invariance in the finite

Publication ,  Conference
Rossman, B
Published in: Proceedings Symposium on Logic in Computer Science
January 1, 2003

A first-order sentence θ of vocabulary σ {S} is successor-invariant 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 non-first-order definable class of finite structures which is, however, defined by a successor-invariant first-order sentence. This strengthens a corresponding result for order-invariance in the finite, due to Y. Gurevich.

Duke Scholars

Benjamin Rossman
Author Benjamin Rossman Computer Science

Published In

Proceedings Symposium on Logic in Computer Science

ISSN

1043-6871

Publication Date

January 1, 2003

Start / End Page

148 / 157
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2003). Successor-invariance in the finite. In Proceedings Symposium on Logic in Computer Science (pp. 148–157).
Rossman, B. “Successor-invariance in the finite.” In Proceedings Symposium on Logic in Computer Science, 148–57, 2003.
Rossman B. Successor-invariance in the finite. In: Proceedings Symposium on Logic in Computer Science. 2003. p. 148–57.
Rossman, B. “Successor-invariance in the finite.” Proceedings Symposium on Logic in Computer Science, 2003, pp. 148–57.
Rossman B. Successor-invariance in the finite. Proceedings Symposium on Logic in Computer Science. 2003. p. 148–157.

Published In

Proceedings Symposium on Logic in Computer Science

ISSN

1043-6871

Publication Date

January 1, 2003

Start / End Page

148 / 157