Some remarks on real numbers induced by first-order spectra

Sune Jakobsen; Jakob Grue Simonsen

doi:10.1215/00294527-3489987

Some remarks on real numbers induced by first-order spectra

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 (i) every algebraic real is spectral, (ii) every automatic real is spectral, (iii) the subword density of a spectral real is either 0 or 1, and both may occur, and (iv) 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.

Originalsprog	Engelsk
Tidsskrift	Notre Dame Journal of Formal Logic
Vol/bind	57
Udgave nummer	3
Sider (fra-til)	355-368
Antal sider	14
ISSN	0029-4527
DOI	https://doi.org/10.1215/00294527-3489987
Status	Udgivet - 2016

Adgang til dokumentet

10.1215/00294527-3489987

00294527-3489987.pdfForlagets udgivne version, 354 KB

Citationsformater

@article{677e400db0ec44c792cd1611626879ac,

title = "Some remarks on real numbers induced by first-order spectra",

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 (i) every algebraic real is spectral, (ii) every automatic real is spectral, (iii) the subword density of a spectral real is either 0 or 1, and both may occur, and (iv) 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.",

keywords = "Computability theory, Computational complexity, First-order logic, Spectral reals",

author = "Sune Jakobsen and Simonsen, {Jakob Grue}",

year = "2016",

doi = "10.1215/00294527-3489987",

language = "English",

volume = "57",

pages = "355--368",

journal = "Notre Dame Journal of Formal Logic",

issn = "0029-4527",

publisher = "Duke University Press",

number = "3",

}

TY - JOUR

T1 - Some remarks on real numbers induced by first-order spectra

AU - Jakobsen, Sune

AU - Simonsen, Jakob Grue

PY - 2016

Y1 - 2016

N2 - 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 (i) every algebraic real is spectral, (ii) every automatic real is spectral, (iii) the subword density of a spectral real is either 0 or 1, and both may occur, and (iv) 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.

AB - 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 (i) every algebraic real is spectral, (ii) every automatic real is spectral, (iii) the subword density of a spectral real is either 0 or 1, and both may occur, and (iv) 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.

KW - Computability theory

KW - Computational complexity

KW - First-order logic

KW - Spectral reals

U2 - 10.1215/00294527-3489987

DO - 10.1215/00294527-3489987

M3 - Journal article

AN - SCOPUS:84978818229

SN - 0029-4527

VL - 57

SP - 355

EP - 368

JO - Notre Dame Journal of Formal Logic

JF - Notre Dame Journal of Formal Logic

IS - 3

ER -

Some remarks on real numbers induced by first-order spectra

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater