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.
@cite_7: 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.
@cite_11: In 1952, Heinrich Scholz published a question in The Journal of Symbolic Logic asking for a characterization of spectra, i.e., sets of natural numbers that are the cardinalities of finite models of first order sentences. Gunter Asser in turn asked whether the complement of a spectrum is always a spectrum. These innocent questions turned out to be seminal for the development of finite model theory and descriptive complexity. In this paper we survey developments over the last 50-odd years pertaining to the spectrum problem. Our presentation follows conceptual developments rather than the chronological order. Originally a number theoretic problem, it has been approached by means of recursion theory, resource bounded complexity theory, classification by complexity of the defining sentences, and finally by means of structural graph theory. Although Scholz' question was answered in various ways, Asser's question remains open.
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 .