Eryk Kopczynski ; Tony Tan - A note on first-order spectra with binary relations

lmcs:3751 - Logical Methods in Computer Science, April 25, 2018, Volume 14, Issue 2 - https://doi.org/10.23638/LMCS-14(2:4)2018
A note on first-order spectra with binary relationsArticle

Authors: Eryk Kopczynski ; Tony Tan

    The spectrum of a first-order sentence is the set of the cardinalities of its finite models. In this paper, we consider the spectra of sentences over binary relations that use at least three variables. We show that for every such sentence $\Phi$, there is a sentence $\Phi'$ that uses the same number of variables, but only one symmetric binary relation, such that its spectrum is linearly proportional to the spectrum of $\Phi$. Moreover, the models of $\Phi'$ are all bipartite graphs. As a corollary, we obtain that to settle Asser's conjecture, i.e., whether the class of spectra is closed under complement, it is sufficient to consider only sentences using only three variables whose models are restricted to undirected bipartite graphs.


    Volume: Volume 14, Issue 2
    Published on: April 25, 2018
    Accepted on: March 13, 2018
    Submitted on: June 30, 2017
    Keywords: Computer Science - Logic in Computer Science,F.4.1,F.1.3

    Consultation statistics

    This page has been seen 1151 times.
    This article's PDF has been downloaded 286 times.