On the Variable Hierarchy of First-Order Spectra
Journal
ACM Transactions on Computational Logic
Journal Volume
16
Journal Issue
2
Date Issued
2015
Author(s)
Kopczynski, Eryk
TONY TAN
Abstract
The 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.
Subjects
Bounded number of variables; First-order spectra; Nondeterministic exponential time
SDGs
Other Subjects
Logic programming; Binary relation; Bounded number of variables; Cardinalities; Exponential time; Finite model; First order; First order logic; Natural number; Formal logic
Type
journal article