Spectra with only unary function symbols

DOI10.1007/BFB0028015MaRDI QIDQ4218932zbMATH OpenFDO

Authors Arnaud Durand, Ronald Fagin, Bernd Loescher

Publication date 15 November 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0028015

zbMATH Keywords

Ehrenfeucht-Fraïssé methodeventually periodic setsfinite model theoryspectrum problemunary functions

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Properties of classes of models (03C52)

Review text

The authors show that the spectra of first-order sentences over the vocabulary of one unary function symbol are precisely the eventually periodic sets (the spectrum of a sentence \(\varphi\) is the set of cardinalities of finite models of \(\varphi)\). Thus, the class of these spectra is closed under complements (the so-called spectrum problem asks whether the class of spectra of arbitrary first-order sentences is closed under complements). The proof uses the Ehrenfeucht-Fraïssé method and a number-theoretic argument. For the entire collection see [Zbl 0891.00021].

Recommendations

• First-order spectra with one binary predicate
• scientific article; zbMATH DE number 2079026
• First-order spectra with one variable
• scientific article; zbMATH DE number 4019038
• scientific article; zbMATH DE number 2121574

Cited in

(13)

• First-order spectra with one binary predicate
• The Specker-Blatter theorem does not hold for quaternary relations
• One unary function says less than two in existential second order logic
• scientific article; zbMATH DE number 4019038 (Why is no real title available?)
• The ultra-weak Ash conjecture and some particular cases
• scientific article; zbMATH DE number 3926889 (Why is no real title available?)
• scientific article; zbMATH DE number 2079026 (Why is no real title available?)
• A note on first-order spectra with binary relations
• scientific article; zbMATH DE number 2113458 (Why is no real title available?)
• scientific article; zbMATH DE number 2121574 (Why is no real title available?)
• Spectra and satisfiability for logics with successor and a unary function
• Regular graphs and the spectra of two-variable logic with counting
• First-order spectra with one variable

This page was built for publication: Spectra with only unary function symbols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218932)