Puneet Varma (Editor)

Spectrum of a sentence

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

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

    • ∃ z , o   ∀ a , b , c   ∃ d , e

    a + z = a = z + a   ∧   a ⋅ z = z = z ⋅ a   ∧   a + d = z ∧   a + b = b + a   ∧   a ⋅ ( b + c ) = a ⋅ b + a ⋅ c   ∧   ( a + b ) + c = a + ( b + c ) ∧   a ⋅ o = a = o ⋅ a   ∧   a ⋅ e = o   ∧   ( a ⋅ b ) ⋅ c = a ⋅ ( b ⋅ c )

    is { p n ∣ p  prime , n ∈ 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 ∃ S , T   ∀ x   { x ∈ S ⟺ x ∉ T ∧   f ( f ( x ) ) = x ∧   x ∈ S ⟺ f ( x ) ∈ T } 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 NEXP.

    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.

    References

    Spectrum of a sentence Wikipedia
    (Text) CC BY-SA