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_19: Abstract Define a (∀1 unary)-sentence to be a prenex first-order sentence of unary type (i.e., a type which only contains unary relation and function symbols and constant symbols) with only one (universal) quantifier. A successor structure is a structure 〈 B , S 〉 such that S is a function which is a permutation of the basis B with only one cycle. We exhibit a (∀1, unary)-sentence φ of type S , U 1 , …, U p such that if B is finite then 〈 B , S 〉 is a successor structure if 〈 B , S 〉 satisfies ∃ U 1 , …, ∃ U p ϕ . It implies that ⋃ NRAM( cn )=SPECTRA(∀1, unary), c ⩾1 where NRAM(cn) denotes the class of sets of positive integers accepted by a nondeterministic random access machine in time cn (where n is the input integer) and SPECTRA(∀1, unary) is the class of finite spectra of (∀1, unary)-sentences. Another consequence is that some graph properties (hamiltonicity, connectedness) can be characterised by sentences with unary function symbols and constant symbols and only one variable. This contrasts with the result (by Fagin and De Rougemont) that these two graph properties are not definable by monadic generalized spectra (without function symbols) even in the presence of an underlying successor relation.
This does not imply our hierarchy here: @math . Obviously every function can be translated into a relation in first-order logic. However, such translation requires at least one new variable for each function. It is not clear whether there is a translation in which the number of new variables introduced depends only on the arity of the functions, and not on the number of functions. At this point we should also remark that @math can be much more expressive than @math . Take, for example, @math . The class @math consists of only empty set and sets of the form @math , whereas the class @math contains PRIMES, the set of prime numbers @cite_19 .