On the variable hierarchy of first-order spectra

2014/03/10 by Kopczynski, Eryk, Tan, Tony
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1403.2225

Abstract

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.

Related

• Regular graphs and the spectra of two-variable logic with counting
• Order-Invariance in the Two-Variable Fragment of First-Order Logic
• From algebra to logic: there and back again -- the story of a hierarchy
• k variables are needed to define k-Clique in first-order logic
• Spectrum of FO logic with quantifier depth 4 is finite