                                              Notes prepared by
                                                 Stanley Burris
                                                   July 3, 2001

Spectrum of a sentence

In 1952 Scholz asked about the possibilities for the set of sizes of the finite models of a first-order sentence.

DEFINITION 1 Given a first-order sentence φ define the spectrum of φ to be the set {|A| : A ⊧ φ, A finite}.

Let us look at some examples of spectra.

EXAMPLE 2 The set of powers of primes is a spectrum: take the statement defining fields.

EXAMPLE 3 The set of even numbers is a spectrum: take the statement ∀x(x ≉ f(x) ∧ x ≈ f(f(x))).

An interesting set of models is obtained by using a modification of Dedekind’s approach to the natural numbers, namely let our language be {+, ×, ≤,′ , 2, b, c} and let φ_{0} be the conjunction of the statements:

• ∀x x ≤ x ∀x∀y x ≤ y ∧ y ≤ x ⟹ x ≈ y ∀x∀y∀z x ≤ y ∧ y ≤ z ⟹ x ≤ z [≤ is a linear ordering]

• ∀x 2 ≤ x ∧ x ≤ c [2 is the smallest element, c the largest element]

• x < c ⟹ x < x′ [′ is strictly increasing on the elements less than c]

• c′ ≈ c ∧ b < c ∧ b′ ≈ c

• ∀x∀y y ≤ x ∨ x′ ≤ y [there are no elements between x and x′]

• ∀x x + 2 ≈ x′′ • ∀x∀y x + y′ ≈ (x + y)′

• ∀x∀y x × 2 ≈ x + x

• ∀x∀y x × y′ ≈ (x × y) + x

One can see that for each natural number n > 1 there is one model (up to isomorphism) of size n, and it looks like the numbers greater than 1 with the usual ordering ≤ and operations +, ×,′, with the numbers ≥ n + 1 collapsed into the single number n+1, which is the element labelled c, and n is labelled b.

EXAMPLE 4 The set of composite numbers is a spectrum: take φ_{0} ∧ ψ where ψ is ∃x∃y (x < b ∧ y < b ∧ x × y ≈ b).

EXAMPLE 5 The set of prime numbers is a spectrum: take φ_{0} ∧ ¬ψ, ψ as in example 4

One can easily show that the union or intersection of two spectra is again a spectrum (make the languages of φ and ψ disjoint and consider φ ∨ ψ and φ ∧ ψ). In 1956 Asser looked at the question of whether the complement of a spectrum is again a spectrum — the problem is still open. A fascinating result was proved by Jones and Selman in 1974 when they showed that a subset of N is a spectrum iff it can be accepted by some nondeterministic Turing machine in time 2^{O(n)}. From this it follows that if NP is closed under complements, i.e., NP = co-NP, then spectra are also closed under complements. Consequently to show that spectra are not closed under complements is at least as difficult as showing NP ≠ co-NP, and hence P ≠ NP.

Exercises

Problem 1 Show that the union or intersection of two spectra is again a spectrum.

Problem 2 Show that {n^{2} : n ∈ N} is a spectrum.

Problem 3 Show that {n^{2} + 1 : n ∈ N} is a spectrum.

Problem 4 Show that {2^{n} + 1 : n ∈ N} is a spectrum.

Problem 5 Show for a fixed n that {p^{n} : p a prime} is a spectrum.

Problem 6 ⋆ Show that {F_{n} : n ∈ N, F_{n}=n^{th} Fermat prime} is a spectrum.

Problem 7 ⋆ Show that {2^{x}3^{y}5^{z}7^{w} : x^{w} + y^{w} = z^{w}} is a spectrum.

References

[1] G. Asser, Das Repräsentenproblem in Prädikatenkalkül der ersten Stufe mit Identität. Z. f. Math. Logik u. Grundlagen d. Math. 1 (1956), 252–263.

[2] N.D. Jones and A.L. Selman, Turing machines and the spectra of first-order formulas. J. Symbolic Logic 39 (1974), 139-150.

[3] H. Scholz, Ein ungelöstes Problem in der symbolischen Logik. J. Symbolic Logic 17 (1952), 160.