** Next:**
Dedekind

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

Let us look at some examples of spectra.

An interesting set of models is obtained by using a modification of Dedekind's approach to the natural numbers, namely let our language be and let be the conjunction of the statements:

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
. 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

**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.

** Next:**
Dedekind

Fri Jan 31 13:13:26 EST 1997