Spectrum of a sentence

In mathematical logic, the spectrum of a sentence is the set of natural numbers occurring as the size of a finite model in which a given sentence is true.

Definition

Let ψ be a sentence in first-order logic. The spectrum of ψ is the set of natural numbers n such that there is a finite model for ψ with n elements.

If the vocabulary for ψ consists of relational symbols, then ψ can be regarded as a sentence in existential second-order logic (ESOL) quantified over the relations, over the empty vocabulary. A generalised spectrum is the set of models of a general ESOL sentence.

Examples

• The spectrum of the first-order logic formula

$\exists z,o ~ \forall a,b,c ~ \exists d,e$

$a+z=a=z+a ~ \land~ a\cdot z=z=z\cdot a ~ \land~ a+d=z$

$\land~ a+b=b+a ~ \land~ a\cdot(b+c)=a\cdot b+a\cdot c ~ \land~(a+b)+c=a+(b+c)$

$\land~ a\cdot o=a=o\cdot a ~ \land~ a\cdot e=o ~\land~ (a\cdot b)\cdot c=a\cdot (b\cdot c)$

is $\{p^{n}\mid p \text{ prime}, n\in\mathbb{N}\}$, the set of power of a prime number. Indeed, with $z$ for $0$ and $o$ for $1$, this sentence describes the set of fields; the cardinal of a finite field is the power of a prime number.

• The spectrum of the monadic second-order logic formula $\exists S, T ~ \forall x ~ \left\{x\in S\iff x\not\in T \land~ f(f(x))=x \land~ x\in S\iff f(x)\in T\right\}$ is the set of even numbers. Indeed, $f$ is a bijection between $S$ and $T$, and $S$ and $T$ are a partition of the universe. Hence the cardinal of the universe is even.
• The set of finite and co-finite set is the set of spectra of first-order logic with the successor relation.
• The set of ultimately periodic sets is the set of spectra of monadic second-order logic with a unary function. It is also the set of spectra of monadic second-order logic with the successor function.

Properties

Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine. The theorem was proven by Ronald Fagin in 1974 (strictly, in 1973 in his doctoral thesis).

As a corollary we have a result of Jones and Selman, that a set is a spectrum if and only if it is in the complexity class NE (complexity).

The set of spectra of a theory is closed by union, intersection, addition, multiplication. In full generality, it is not known if the set of spectra of a theory is closed by complementation, it is the so-called Asser's Problem.

See also

• Spectrum of a theory

References

• Fagin, Ronald (1974). "Generalized First-Order Spectra and Polynomial-Time Recognizable Sets". In Karp, Richard M. Complexity of Computation (PDF). Proc. Syp. App. Math. SIAM-AMS Proceedings 7. pp. 27–41. Zbl 0303.68035.
• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 978-3-540-00428-8. Zbl 1133.03001.
• Immerman, Neil (1999). Descriptive Complexity. Graduate Texts in Computer Science. New York: Springer-Verlag. pp. 113–119. ISBN 0-387-98600-6. Zbl 0918.68031.
• Jones, Neil D.; Selman, Alan L. (1974). "Turing machines and the spectra of first-order formulas". J. Symb. Log. 39: 139–150. doi:10.2307/2272354. Zbl 0288.02021.
• Durand, Arnaud; Jones, Neil; Markowsky, Johann; More, Malika (2012). "Fifty Years of the Spectrum Problem: Survey and New Results". Bulletin of Symbolic Logic 18 (4): 505––553.

External links