The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we study the hierarchy of first-order spectra based on the number of variables. It has been conjectured that it collapses to three variable. We show the opposite: it forms an infinite hierarchy. However, despite the fact that more variables can express more spectra, we show that to establish whether the class of first-order spectra is closed under complement, it is sufficient to consider sentences using only three variables and binary relations.
First, we remark that our result @math , for each integer @math complements previous known result that @math @cite_11 , which can be proved as follows. First, a model of first-order sentence with only one variable remains a model after cloning elements, thus @math only includes the empty set, and sets of form @math . In another paper we show that the class of spectra of two-variable logic with counting quantifiers is exactly the class of semilinear sets, and closed under complement @cite_7 . Using the same methods, one can show that @math is the class of finite and cofinite sets, thus separating @math from @math . On the other hand, three variables are enough to simulate an arbitrary Turing machine, so it is not difficult to construct a set in @math which is not even semilinear, say, e.g., @math , hence, separating @math from @math .
@cite_7 @cite_11
2125449161 2007053458
The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we show that when restricted to using only two variables, but allowing counting quantifiers, the spectra of first-order logic sentences are semilinear and hence, closed under complement. At the heart of our proof are semilinear characterisations for the existence of regular and biregular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices. Our proof also provides a simple characterisation of models of two-variable logic with counting -- that is, up to renaming and extending the relation names, they are simply a collection of regular and biregular graphs. The spectrum of a first-order sentence is the set of cardinalities of its finite models. We refine the well-known equality between the class of spectra and the class of sets (of positive integers) accepted by nondeterministic Turing machines in polynomial time. Let @math denote the class of spectra of sentences with d universal quantifiers. For any integer @math and each set of positive integers, A, we obtain: [ A NTIME (n^d ) A Sp (d ) A NTIME (n^d ( n)^2 ). ] Further the first implication holds even if we use multidimensional nondeterministic Turing machines. These results hold similarly for generalized spectra. As a consequence, we obtain a simplified proof of a hierarchy result of P. Pudlak about (generalized) spectra. We also prove that the set of primes is the spectrum of a certain sentence with only one variable.