A note on the variable hierarchy of first-order spectra

Abstract

The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this note we study the hierarchy of first-order spectra based on the number of variables. We show that it forms an infinite hierarchy. However, despite the fact that more variables can express more spectra, we also show that to show whether the first-order spectra are closed under complement, it is sufficient to consider sentences using only three variables and binary relations.