David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Bulletin of Symbolic Logic 18 (4):505-553 (2012)
In 1952, Heinrich Scholz published a question in The Journal of Symbolic Logic asking for a characterization of spectra, i.e., sets of natural numbers that are the cardinalities of finite models of first order sentences. Günter Asser in turn asked whether the complement of a spectrum is always a spectrum. These innocent questions turned out to be seminal for the development of finite model theory and descriptive complexity. In this paper we survey developments over the last 50-odd years pertaining to the spectrum problem. Our presentation follows conceptual developments rather than the chronological order. Originally a number theoretic problem, it has been approached by means of recursion theory, resource bounded complexity theory, classification by complexity of the defining sentences, and finally by means of structural graph theory. Although Scholz' question was answered in various ways, Asser's question remains open
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
M. Krynicki & K. Zdanowski (2005). Theories of Arithmetics in Finite Models. Journal of Symbolic Logic 70 (1):1-28.
William G. Lycan (1973). Inverted Spectrum. Ratio 15 (July):315-9.
E. Fischer & J. A. Makowsky (2004). On Spectra of Sentences of Monadic Second Order Logic with Counting. Journal of Symbolic Logic 69 (3):617-640.
J. Landes, J. B. Paris & A. Vencovská (2011). A Survey of Some Recent Results on Spectrum Exchangeability in Polyadic Inductive Logic. Synthese 181 (1):19 - 47.
O. Finkel & J. P. Ressayre (1996). Stretchings. Journal of Symbolic Logic 61 (2):563-585.
Heinrich Herre, Michał Krynicki, Alexandr Pinus & Jouko Väänänen (1991). The Härtig Quantifier: A Survey. Journal of Symbolic Logic 56 (4):1153-1183.
Oscar Horta (2011). Betterness, Spectrum Cases and the Challenge to Transitivity in Axiology. Diacritica 25:125-137.
David J. Cole (1990). Functionalism and Inverted Spectra. Synthese 82 (2):207-22.
Joanna Golinska-Pilarek & Konrad Zdanowski (2003). Spectra of Formulae with Henkin Quantifiers. In A. Rojszczak, J. Cachro & G. Kurczewski (eds.), Philosophical Dimensions of Logic and Science. Kluwer Academic Publishers
Saharon Shelah & Simon Thomas (1997). The Cofinality Spectrum of the Infinite Symmetric Group. Journal of Symbolic Logic 62 (3):902-916.
Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic 3 (1):53-69.
I. C. Jarvie & Sandra Pralong (eds.) (1999/2003). Popper's Open Society After Fifty Years: The Continuing Relevance of Karl Popper. Routledge.
Jeff Speaks (2011). Spectrum Inversion Without a Difference in Representation is Impossible. Philosophical Studies 156 (3):339-361.
John Campbell (2003). Philosophy of Mind. In Peter Clark & Katherine Hawley (eds.), Philosophy of Science Today. Oxford University Press 131.
Marcin Mostowski & Jakub Szymanik (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. Bulletin of Symbolic Logic 13:281--282.
Added to index2012-11-14
Total downloads4 ( #383,052 of 1,699,575 )
Recent downloads (6 months)1 ( #362,609 of 1,699,575 )
How can I increase my downloads?