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 | Corporate Authors: | Kopczýnski, Eryk | 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. | Keywords: | spectra; first-order; bounded variables | Document URI: | http://hdl.handle.net/1942/16519 | Link to publication/dataset: | http://arxiv.org/abs/1403.2225 | Category: | O | Type: | Preprint |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
spec-k-v-sub.pdf | Non Peer-reviewed author version | 111.38 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.