Some Remarks on Real Numbers Induced by First-Order Spectra

Notre Dame Journal of Formal Logic 57 (3):355-368 (2016)
  Copy   BIBTEX

Abstract

The spectrum of a first-order sentence is the set of natural numbers occurring as the cardinalities of finite models of the sentence. In a recent survey, Durand et al. introduce a new class of real numbers, the spectral reals, induced by spectra and pose two open problems associated to this class. In the present note, we answer these open problems as well as other open problems from an earlier, unpublished version of the survey. Specifically, we prove that every algebraic real is spectral, every automatic real is spectral, the subword density of a spectral real is either 0 or 1, and both may occur, and every right-computable real number between 0 and 1 occurs as the subword entropy of a spectral real. In addition, Durand et al. note that the set of spectral reals is not closed under addition or multiplication. We extend this result by showing that the class of spectral reals is not closed under any computable operation satisfying some mild conditions.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,783

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.
Relative Randomness and Real Closed Fields.Alexander Raichev - 2005 - Journal of Symbolic Logic 70 (1):319 - 330.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
WHAT IS. . . a Halting Probability?Cristian S. Calude - 2010 - Notices of the AMS 57:236-237.
Order‐free Recursion on the Real Numbers.Vasco Brattka - 1997 - Mathematical Logic Quarterly 43 (2):216-234.
H‐monotonically computable real numbers.Xizhong Zheng, Robert Rettinger & George Barmpalias - 2005 - Mathematical Logic Quarterly 51 (2):157-170.
Schnorr trivial reals: a construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
A C.E. Real That Cannot Be SW-Computed by Any Ω Number.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (2):197-209.

Analytics

Added to PP
2016-03-25

Downloads
14 (#988,032)

6 months
3 (#969,763)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

The Arithmetical Hierarchy of Real Numbers.Xizhong Zheng & Klaus Weihrauch - 2001 - Mathematical Logic Quarterly 47 (1):51-66.
On the Computational Complexity of Algorithms.J. Hartmanis & R. E. Stearns - 1967 - Journal of Symbolic Logic 32 (1):120-121.

Add more references