Previous: First-order arithmetic

Next: Dedekind

Up: Supplementary Text Topics

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.

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 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 collapsed into the single number n+1, which is the element labelled c, and n is labelled b.

 

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




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.


Previous: First-order arithmetic

Next: Dedekind

Up: Supplementary Text Topics

Stan Burris
Fri Jan 31 13:13:26 EST 1997