Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/16519

Title: A note on the variable hierarchy of first-order spectra
Authors: TAN, Tony
Issue Date: 2014
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.
URI: http://hdl.handle.net/1942/16519
Link to publication: http://arxiv.org/abs/1403.2225
Category: O
Type: Preprint
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A111.38 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.