Kopczynski, ErykErykKopczynskiTONY TAN2020-05-042020-05-04201515293785https://scholars.lib.ntu.edu.tw/handle/123456789/490116https://www.scopus.com/inward/record.uri?eid=2-s2.0-84927551306&doi=10.1145%2f2733376&partnerID=40&md5=b06999bd0303257ff3d6f8b0752b1bb5The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this article, we study the hierarchy of first-order spectra based on the number of variables. It has been conjectured that it collapses to three variables. 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.Bounded number of variables; First-order spectra; Nondeterministic exponential time[SDGs]SDG16Logic programming; Binary relation; Bounded number of variables; Cardinalities; Exponential time; Finite model; First order; First order logic; Natural number; Formal logicjournal article10.1145/27333762-s2.0-84927551306https://doi.org/10.1145/2733376